Could you trace how this Haskell foldl lambda function works?

Question

myReverse :: [a] -> [a] myReverse = foldl (\ax -> x:a) [] foldl is (a -> b -> a) -> a -> [b] -> a 

The lambda function is obviously in parentheses. Where foldl get its initial value? And what in this case [b] ?

Answer 1

We can evaluate, say, myReverse [1,2,3] . We need a foldl definition

 foldl fz [] = z foldl fz (x:xs) = foldl f (fzx) xs 

So we have

 myReverse [1,2,3,4] -- definition of myReverse = foldl (\ax -> x:a) [] [1,2,3] -- definition of foldl (x:xs case) = foldl (\ax -> x:a) ((\ax -> x:a) [] 1) [2,3] -- beta reduction [1] = foldl (\ax -> x:a) [1] [2,3] -- definition of foldl = foldl (\ax -> x:a) ((\ax -> x:a) [1] 2) [3] -- beta reduction = foldl (\ax -> x:a) [2,1] [3] -- definition of foldl = foldl (\ax -> x:a) ((\ax -> x:a) [2,1] 3) [] -- beta reduction = foldl (\ax -> x:a) [3,2,1] [] -- definition of foldl ([] case) = [3,2,1] 

with an important warning in [1] and for each stage of beta recovery, that this beta reduction actually occurs only when something checks the result. As foldl progresses foldl repeating f applications grow like thunks, so we really get (if f = \ax -> x:a ):

 foldl f [] [1,2,3] foldl f (f [] 1) [2,3] foldl f ((f 2 (f [] 1))) [3] foldl f (((f 3 ((f 2 (f [] 1)))))) [] (((f 3 ((f 2 (f [] 1)))))) 

That's why we have a foldl' , which is strict in its battery and prevents it from building up.

The initial value is [] . [b] in this case matches a in foldl , which is [a] in myReverse .

Answer 2

 myReverse :: [a] -> [a] myReverse = foldl (\ax -> x:a) [] 

can be equivalently rewritten as

 myReverse :: [a] -> [a] myReverse xs = foldl (\ax -> x:a) [] xs 

Therefore, the bending function is lambda \ax -> x:a , the starting value is [] , and the list for bending is xs .