HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Scanl expressed as fold

Submitted by: @import:stackexchange-codereview··
0
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.

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.