Merge pull request #155 from drewolson/scanr-lazy

garyb · web-flow · commit 6629e0c05f2e · 2019-02-09T21:09:37.000Z
Add scanrLazy for lazy lists
diff --git a/src/Data/List/Lazy.purs b/src/Data/List/Lazy.purs
@@ -89,6 +89,7 @@ module Data.List.Lazy
 
   , foldM
   , foldrLazy
+  , scanrLazy
 
   , module Exports
   ) where
@@ -755,3 +756,13 @@ foldrLazy op z = go
     go xs = case step xs of
       Cons x xs' -> Z.defer \_ -> x `op` go xs'
       Nil -> z
+
+-- | Perform a right scan lazily
+scanrLazy :: forall a b. (a -> b -> b) -> b -> List a -> List b
+scanrLazy f acc xs = List (go <$> unwrap xs)
+  where
+    go :: Step a -> Step b
+    go Nil = Nil
+    go (Cons x xs') =
+      let acc' = f x acc
+       in Cons acc' $ scanrLazy f acc' xs'
diff --git a/test/Test/Data/List/Lazy.purs b/test/Test/Data/List/Lazy.purs
@@ -6,7 +6,7 @@ import Control.Lazy (defer)
 import Data.FoldableWithIndex (foldMapWithIndex, foldlWithIndex, foldrWithIndex)
 import Data.FunctorWithIndex (mapWithIndex)
 import Data.Lazy as Z
-import Data.List.Lazy (List, Pattern(..), alterAt, catMaybes, concat, concatMap, cons, delete, deleteAt, deleteBy, drop, dropWhile, elemIndex, elemLastIndex, filter, filterM, findIndex, findLastIndex, foldM, foldMap, foldl, foldr, foldrLazy, fromFoldable, group, groupBy, head, init, insert, insertAt, insertBy, intersect, intersectBy, iterate, last, length, mapMaybe, modifyAt, nil, nub, nubBy, null, partition, range, repeat, replicate, replicateM, reverse, singleton, slice, snoc, span, stripPrefix, tail, take, takeWhile, transpose, uncons, union, unionBy, unzip, updateAt, zip, zipWith, zipWithA, (!!), (..), (:), (\\))
+import Data.List.Lazy (List, Pattern(..), alterAt, catMaybes, concat, concatMap, cons, delete, deleteAt, deleteBy, drop, dropWhile, elemIndex, elemLastIndex, filter, filterM, findIndex, findLastIndex, foldM, foldMap, foldl, foldr, foldrLazy, fromFoldable, group, groupBy, head, init, insert, insertAt, insertBy, intersect, intersectBy, iterate, last, length, mapMaybe, modifyAt, nil, nub, nubBy, null, partition, range, repeat, replicate, replicateM, reverse, scanrLazy, singleton, slice, snoc, span, stripPrefix, tail, take, takeWhile, transpose, uncons, union, unionBy, unzip, updateAt, zip, zipWith, zipWithA, (!!), (..), (:), (\\))
 import Data.List.Lazy.NonEmpty as NEL
 import Data.Maybe (Maybe(..), isNothing, fromJust)
 import Data.Monoid.Additive (Additive(..))
@@ -394,6 +394,11 @@ testListLazy = do
              infs' = foldrLazy cons nil infs
           in take 1000 infs == take 1000 infs'
 
+  log "scanrLazy should work ok on infinite lists"
+  assert let infs = iterate (_ + 1) 1
+             infs' = scanrLazy (\i _ -> i) 0 infs
+          in take 1000 infs == take 1000 infs'
+
   log "can find the first 10 primes using lazy lists"
   let eratos :: List Int -> List Int
       eratos xs = defer \_ ->
