Home > Back-end >  Understanding the reduction process of a foldl
Understanding the reduction process of a foldl

Time:12-03

Since I am new in "innermost, outermost" I have problem with understanding the leftmost outermost style.

I would like to understand the reduction processes for the list [5,2,1]

foldl :: ( b -> a -> b ) -> b -> [ a ] -> b
foldl _ e [] = e
foldl f e (x:xs) = foldl f (f e x) xs

foldl (\acc x -> acc    [negate x]) [] [5,2,1]

CodePudding user response:

You can inline the definition to get a better understanding of what is going on.

foldl (\acc x -> acc    [negate x]) [] [5,2,1]
-- using foldl f e (x:xs) = foldl f (f e x) xs
-- with f = (\acc x -> acc    [negate x])
--      e = []
--      x = 5
--      xs = [2,1]
-- replace line 1 with foldl f (f e x) xs
foldl f (f [] 5) [2,1]
foldl f (f (f [] 5) 2) [1]
foldl f (f (f (f [] 5) 2) 1) []
-- using foldl _ e [] = e
f (f (f [] 5) 2) 1
-- in infix style (f [] 5 == [] `f` 5)
(([] `f` 5) `f` 2) `f` 1

In general

foldl ( ) 0 [a, b, c] == ((0   a)   b)   c

foldr ( ) 0 [a, b, c] == a   (b   (c   0))
  • Related