FOLDR - Lists - Haskell

Learn

Haskell - Lists - Foldr

Learn
Haskell - Lists - Foldr
foldr This is how the right fold is implemented: foldr :: (a -> b -> b) -> b -> [a] -> b foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) -- = x `f` foldr f z xs The right fold, `foldr`, associates to the right. That is: `foldr (+) 0 [1, 2, 3] -- is equivalent to 1 + (2 + (3 + 0))` The reason is that `foldr` is evaluated like this (look at the inductive step of `foldr`): `foldr (+) 0 [1, 2, 3] -- foldr (+) 0 [1,2,3] (+) 1 (foldr (+) 0 [2, 3]) -- 1 + foldr (+) 0 [2,3] (+) 1 ((+) 2 (foldr (+) 0 [3])) -- 1 + (2 + foldr (+) 0 [3]) (+) 1 ((+) 2 ((+) 3 (foldr (+) 0 []))) -- 1 + (2 + (3 + foldr (+) 0 [])) (+) 1 ((+) 2 ((+) 3 0)) -- 1 + (2 + (3 + 0 ))` The last line is equivalent to `1 + (2 + (3 + 0))`, because `((+) 3 0)` is the same as `(3 + 0)`.

foldr

This is how the right fold is implemented:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)              -- = x `f` foldr f z xs

The right fold, foldr, associates to the right. That is:

foldr (+) 0 [1, 2, 3]      -- is equivalent to 1 + (2 + (3 + 0))

The reason is that foldr is evaluated like this (look at the inductive step of foldr):

foldr (+) 0 [1, 2, 3]                        --          foldr (+) 0  [1,2,3]
(+) 1 (foldr (+) 0 [2, 3])                   -- 1 +        foldr (+) 0  [2,3]
(+) 1 ((+) 2 (foldr (+) 0 [3]))              -- 1 + (2 +     foldr (+) 0  [3])
(+) 1 ((+) 2 ((+) 3 (foldr (+) 0 [])))       -- 1 + (2 + (3 +  foldr (+) 0 []))
(+) 1 ((+) 2 ((+) 3 0))                      -- 1 + (2 + (3 +            0   ))

The last line is equivalent to 1 + (2 + (3 + 0)), because ((+) 3 0) is the same as (3 + 0).

Read Article
https://develop.horje.com/learn/1434/reference