patternMinor
Scanl expressed as fold
Viewed 0 times
expressedfoldscanl
Problem
Inspired by the learn you a haskell exercise to express map with fold I wrote an implementation of scanl by means of a fold.
I have the idea that in terms of performance it kinda is up to par with standard scanl but I am wondering whether I could improve anything both in terms of performance, idiomacy, style, etc. I am a Haskell novice with modest functional programming (Scala, some Clojure) background.
scanl2 :: (b -> a -> b) -> b -> [a] -> [b]
scanl2 f z xs = reverse $ foldl (\a x -> (f (head a) x): a) [z] xs
I have the idea that in terms of performance it kinda is up to par with standard scanl but I am wondering whether I could improve anything both in terms of performance, idiomacy, style, etc. I am a Haskell novice with modest functional programming (Scala, some Clojure) background.
Solution
Using
reverse is generally a bad idea for performance — especially since Haskell lists can be infinite! Observe:*Main> let triangularNumbers = scanl (+) 0 [1, 2 ..]
*Main> let triangularNumbers2 = scanl2 (+) 0 [1, 2 ..]
*Main> take 5 triangularNumbers
[0,1,3,6,10]
*Main> take 5 triangularNumbers2 -- hangs forever
Context
StackExchange Code Review Q#145874, answer score: 4
Revisions (0)
No revisions yet.