linear-base 0.5.0 → 0.6.0

raw patch · 4 files changed

+78/−12 lines, 4 files

Files

CHANGELOG.md +8/−0
linear-base.cabal +1/−1
src/Data/List/Linear.hs +46/−10
test/Test/Data/List.hs +23/−1

CHANGELOG.md view

@@ -1,5 +1,13 @@ # Change Log +## [v0.6.0](https://github.com/tweag/linear-base/tree/v0.6.0) (2025-11-18)++[Full Changelog](https://github.com/tweag/linear-base/compare/v0.5.0...v0.6.0)++### Headline changes++- Make List.zipWith as lazy as expected [\#492](https://github.com/tweag/linear-base/pull/492) ([aspiwack](https://github.com/aspiwack))+ ## [v0.5.0](https://github.com/tweag/linear-base/tree/v0.5.0) (2025-04-07)  [Full Changelog](https://github.com/tweag/linear-base/compare/v0.4.0...v0.5.0)

linear-base.cabal view

@@ -1,6 +1,6 @@ cabal-version:      3.0 name:               linear-base-version:            0.5.0+version:            0.6.0 license:            MIT license-file:       LICENSE copyright:          (c) Tweag Holding and affiliates

src/Data/List/Linear.hs view

@@ -1,4 +1,4 @@-{-# LANGUAGE LambdaCase #-}+{-# LANGUAGE BangPatterns #-} {-# LANGUAGE LinearTypes #-} {-# LANGUAGE ScopedTypeVariables #-} {-# LANGUAGE NoImplicitPrelude #-}@@ -80,6 +80,7 @@     zip3,     zipWith,     zipWith',+    zipFold,     zipWith3,     unzip,     unzip3,@@ -354,18 +355,53 @@ zip3 = zipWith3 (,,)  zipWith :: (Consumable a, Consumable b) => (a %1 -> b %1 -> c) -> [a] %1 -> [b] %1 -> [c]-zipWith f xs ys =-  zipWith' f xs ys & \(ret, leftovers) ->-    leftovers `lseq` ret+zipWith f =+  zipFold (\a b cs -> f a b : cs) [] consume2 consume2+  where+    consume2 :: forall x y z. (Consumable x, Consumable y) => x %1 -> y %1 -> [z]+    consume2 x y = x `lseq` y `lseq` []  -- | Same as 'zipWith', but returns the leftovers instead of consuming them.+-- Because the leftovers are returned at toplevel, @zipWith'@ is pretty strict:+-- forcing the first cons cell of the returned list forces all the recursive+-- calls. zipWith' :: (a %1 -> b %1 -> c) -> [a] %1 -> [b] %1 -> ([c], Maybe (Either (NonEmpty a) (NonEmpty b)))-zipWith' _ [] [] = ([], Nothing)-zipWith' _ (a : as) [] = ([], Just (Left (a :| as)))-zipWith' _ [] (b : bs) = ([], Just (Right (b :| bs)))-zipWith' f (a : as) (b : bs) =-  case zipWith' f as bs of-    (cs, rest) -> (f a b : cs, rest)+zipWith' f =+  zipFold+    (\a b !(cs, rest) -> ((f a b : cs), rest))+    ([], Nothing)+    (\a as -> ([], Just (Left (a :| as))))+    (\b bs -> ([], Just (Right (b :| bs))))++-- | A function which combines zipping and 'foldr'. It's more general than all+-- the zip-family functions ('zip', 'zip'', 'zipWith', 'zipWith'').+--+-- If @k < n@, then+--+-- * @'zipFold' cons nil lefta leftb [a₁, a₂, …, aₙ] [b₁, b₂, …, bₖ] = cons a₁ b₁ (cons a₂ b₂ (… (cons aₖ bₖ (lefta aₖ₊₁ [aₖ₊₂, …, aₙ]))))@+-- * @'zipFold' cons nil lefta leftb [a₁, a₂, …, aₖ] [b₁, b₂, …, bₙ] = cons a₁ b₁ (cons a₂ b₂ (… (cons aₖ bₖ (leftb bₖ₊₁ [bₖ₊₂, …, bₙ]))))@+-- * @'zipFold' cons nil lefta leftb [a₁, a₂, …, aₖ] [b₁, b₂, …, bₖ] = cons a₁ b₁ (cons a₂ b₂ (… (cons aₖ bₖ nil)))@+zipFold ::+  forall r a b.+  -- | Combines elements at the same index+  (a %1 -> b %1 -> r %1 -> r) ->+  -- | Starting value if both lists have the same length+  r ->+  -- | Starting value if the first list is longer+  (a %1 -> [a] %1 -> r) ->+  -- | Starting value if the second list is longer+  (b %1 -> [b] %1 -> r) ->+  [a] %1 ->+  [b] %1 ->+  r+zipFold cons nil lefta leftb =+  go+  where+    go :: [a] %1 -> [b] %1 -> r+    go [] [] = nil+    go (a : as) [] = lefta a as+    go [] (b : bs) = leftb b bs+    go (a : as) (b : bs) = cons a b (go as bs)  zipWith3 :: forall a b c d. (Consumable a, Consumable b, Consumable c) => (a %1 -> b %1 -> c %1 -> d) -> [a] %1 -> [b] %1 -> [c] %1 -> [d] zipWith3 _ [] ys zs = (ys, zs) `lseq` []

test/Test/Data/List.hs view

@@ -4,6 +4,7 @@ module Test.Data.List (listTests) where  import qualified Data.List.Linear as List+import qualified Data.Num.Linear as Num import Hedgehog import qualified Hedgehog.Gen as Gen import qualified Hedgehog.Range as Range@@ -17,7 +18,9 @@   testGroup     "List tests"     [ testPropertyNamed "take n ++ drop n = id" "take_drop" take_drop,-      testPropertyNamed "length . take n = const n" "take_length" take_length+      testPropertyNamed "length . take n = const n" "take_length" take_length,+      testPropertyNamed "zipWith is lazy" "zipWith_lazy" zipWith_lazy,+      testPropertyNamed "zipWith3 is lazy" "zipWith3_lazy" zipWith3_lazy     ]  take_drop :: Property@@ -41,3 +44,22 @@     False -> do       annotate "Prelude.length xs < n"       Prelude.length (List.take n xs) === Prelude.length xs++zipWith_lazy :: Property+zipWith_lazy = property $ do+  lgth <- forAll $ Gen.word (Range.linear 0 50)+  _ <- eval $ Prelude.head (xs lgth)+  Prelude.return ()+  where+    xs :: Word -> [Word]+    xs lgth = List.zipWith (Num.+) (0 : error "bottom") [0 .. lgth]++zipWith3_lazy :: Property+zipWith3_lazy = property $ do+  lgth1 <- forAll $ Gen.word (Range.linear 0 50)+  lgth2 <- forAll $ Gen.word (Range.linear 0 50)+  _ <- eval $ Prelude.head (xs lgth1 lgth2)+  Prelude.return ()+  where+    xs :: Word -> Word -> [Word]+    xs lgth1 lgth2 = List.zipWith3 (\x y z -> x Num.+ y Num.+ z) (0 : error "bottom") [0 .. lgth1] [0 .. lgth2]