Folds

inspired by Haskell wiki - Fold
fold functions are used to fold lists
- folding means combining list elements
fold functions take at least the following parameters:
- a function that combines two elements of the list
- the list of elements to be combined
all examples
- compile
- warning free with
  - compiler: GHC 8.10.4 using -Wall

example:

main :: IO ()
main = print (foldr (+) 0 [3::Integer, 5, 7])

in Prelude, there is two fold functions available
- foldr
- foldl
- both have advantages and disadvantages in different cases

foldr	foldl
right fold	left fold
can deal with infinite lists	can only deal with finite lists
(lazy)	(strict)
needs more heap space	needs more stack space
	can lead to stack overflows
	efficiently compiled as a loop
slower	fast
initial value is used when one reaches the end of the list	initial value combined with the first element of the list
immediately returns if f does not demand the rest of the recursion	immediately calls itself with new parameters until it reaches the end of the list
order is kept	order is reverse
type: `Foldable t ⇒ (a → b → b) → b → t a → b`	type: `Foldable t ⇒ (b → a → b) → b → t a → b`
Note the order in underlined function.

there is further variants
- foldl' :: Foldable t ⇒ (b → a → b) → b → t a → b
- foldl1 :: (a → a → a) → [a] → a
- foldl1' :: (a → a → a) → [a] → a
- foldr1 :: (a → a → a) → [a] → a

variants with single quote (“'”) as postfix	variants with one (“1”) as postfix
`foldl'` , `foldl1'`	`foldl1`, `foldl1'` , `foldr1`
stricter variant	no initial value as parameter
forces the evaluation of the initial parameter before making the recursive call	initial value is last and first element of the list, respectively

foldr

right fold
(lazy)
initial value is used when one reaches the end of the list

definition:

-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

immediately returns if f does not demand the rest of the recursion
can deal with infinite lists

example:

main :: IO ()
main = print f1
 
f1 :: Integer
f1 = foldr (sumIfNot 100000000) 0 [0..100000000]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

executes with result:
```
5000000050000000
```
executes in approximately 15 seconds on Intel(R) Core(TM) i5-8400 @ 2.80GHz
executes with allocating approximately 8 GByte heap sapce:

example, list here is infinite:

main :: IO ()
main = print f1
 
f1 :: Integer
f1 = foldr (sumIfNot 100000000) 0 [0..]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

executes with result:
```
5000000050000000
```
executes in approximately 15 seconds on Intel(R) Core(TM) i5-8400 @ 2.80GHz
using simmilar heapsapce as above

foldl

left fold
(fast)
initial value combined with the first element of the list
recursively combining the results of combining all but the last element with the last one

definition:

-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result
-- of combining the old initial value with the first element.
foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

immediately calls itself with new parameters until it reaches the end of the list
can only deal with finite lists
efficiently compiled as a loop
can lead to stack overflows

example:

main :: IO ()
main = print f1
 
f1 :: Integer
f1 = foldl (sumIfNot 100000000) 0 [0..100000000]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

executes with result:
```
5000000050000000
```
executes within approximately 2 seconds on Intel(R) Core(TM) i5-8400 @ 2.80GHz
executes almost without allocating heap space:

example, using infinite list:

main :: IO ()
main = print f1
 
f1 :: Integer
f1 = foldl (sumIfNot 100000000) 0 [0..]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

will not stop executing, unless memory error stops execution
executes allocating heap space, endlessly:

example, using sumIfNot 100:

main :: IO ()
main = print f1
 
f1 :: Integer
f1 = foldl (sumIfNot 100) 0 [0..100000000]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

executes with result:
```
5000000050000000
```
NOTE: The function sumIfNot does not stop the recursion!

foldl'

left fold
same as foldl, but forces the evaluation of the initial parameter before making the recursive call (stricter variant)
can be imported from library Data.List

implementation:

foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
   where f' x k z = k $! f z x

example:

import qualified Data.List as L
 
main :: IO ()
main = print f1
 
f1 :: Integer
f1 = L.foldl' (sumIfNot 100000000) 0 [0..100000000]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

executes with result:
```
5000000050000000
```
executes within approximately 3 seconds on Intel(R) Core(TM) i5-8400 @ 2.80GHz
executes with small allocation of heap space

example, using infinite list:

import qualified Data.List as L
 
main :: IO ()
main = print f1
 
f1 :: Integer
f1 = L.foldl' (sumIfNot 100000000) 0 [0..]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

will not stop executing
executes with small allocation of heap space

example, using sumIfNot 100:

import qualified Data.List as L
 
main :: IO ()
main = print f1
 
f1 :: Integer
f1 = L.foldl' (sumIfNot 100) 0 [0..100000000]
 
sumIfNot :: Integer -> Integer -> Integer -> Integer
sumIfNot nUntil nA nB 
    | nA == nUntil = nA
    | otherwise    = nA + nB

executes with result:
```
5000000050000000
```
NOTE: The function sumIfNot does not stop the recursion!
executes within approximately 3 seconds on Intel(R) Core(TM) i5-8400 @ 2.80GHz
executes with small allocation of heap space

Order of execution

The implications regarding order of execution:

example, using foldr:

main :: IO ()
main = 
    do
        print s
        print $ f1 s
 
s = ['a'..'z']
 
f1 :: String -> String
f1 s = foldr (:) [] s

executes with following output:

"abcdefghijklmnopqrstuvwxyz"
"abcdefghijklmnopqrstuvwxyz"

example, using foldl:

main :: IO ()
main = 
    do
        print s
        print $ f1 s
 
s = ['a'..'z']
 
f1 :: String -> String
f1 s = foldl (flip (:)) [] s

executes with following output:

"abcdefghijklmnopqrstuvwxyz"
"zyxwvutsrqponmlkjihgfedcba"

NOTE: Parameter order of function (:) needed to be flipped to [a] → b → [a] from b → [a] → [a], and would not compile because of type mismatch.

example, using foldl':

import qualified Data.List as L
 
main :: IO ()
main = 
    do
        print s
        print $ f1 s
 
s = ['a'..'z']
 
f1 :: String -> String
f1 s = L.foldl' (flip (:)) [] s

executes with following output:

"abcdefghijklmnopqrstuvwxyz"
"zyxwvutsrqponmlkjihgfedcba"

NOTE: Parameter order of function (:) needed to be flipped as well as for foldl.

example, with not commutative operation (-):

import qualified Data.List as L
 
main :: IO ()
main = 
    do
        print lnNumbers1
        print lnNumbers2
        print $ f1 lnNumbers1
        print $ f1 lnNumbers2
        print $ f2 lnNumbers1
        print $ f2 lnNumbers2
        print $ f3 lnNumbers1
        print $ f3 lnNumbers2
 
lnNumbers1 = [31,7]
lnNumbers2 = [31,7,3]
 
f1 :: [Integer] -> Integer
f1 ln = foldr (-) 0 ln
 
f2 :: [Integer] -> Integer
f2 ln = foldl (flip (-)) 0 ln
 
f3 :: [Integer] -> Integer
f3 ln = L.foldl' (flip (-)) 0 ln

executes with following output:
```
[31,7]
[31,7,3]
24
27
-24
27
-24
27
```

Keeping order and beeing fast?

use case
- finite lists
- large lists
- order of operations to be kept as is foldr

example, using foldr:

main :: IO ()
main = 
    do
        print $ f1 lnNumbers1
        print $ f1 lnNumbers2
        print $ f1 lnNumbers3
 
lnNumbers1 = [31,13]
lnNumbers2 = [31,13,3]
lnNumbers3 = [1..100000000]
 
f1 :: [Integer] -> Integer
f1 ln = foldr (-) 0 ln

executes, with output:
```
18
21
-50000000
```
executes within approximately 15 seconds on Intel(R) Core(TM) i5-8400 @ 2.80GHz
executes using large heap space

example, using foldl and reverse:

import qualified Data.List as L
 
main :: IO ()
main = 
    do
        print $ f2 lnNumbers1
        print $ f2 lnNumbers2
        print $ f2 lnNumbers3
 
lnNumbers1 = [31,13]
lnNumbers2 = [31,13,3]
lnNumbers3 = [1..100000000]
 
f2 :: [Integer] -> Integer
f2 ln = foldlFlpRvrs (-) 0 ln
 
foldlFlpRvrs :: (a -> b -> b) -> b -> [a] -> b
foldlFlpRvrs f initial l = L.foldl' (flip f) initial (reverse l)

executes, with output:
```
18
21
-50000000
```
executes within approximately 15 seconds on Intel(R) Core(TM) i5-8400 @ 2.80GHz

executes using large heap space

regardless of whether L.foldl' or foldl is used

regardless of whether alternative reverse functions are implemented

e.g.:

reverse' :: [a] -> [a]
reverse' (x:rlx) = reverse'' [x] rlx
    where
        reverse'' :: [a] -> [a] -> [a]
        reverse'' lxReverse [] = lxReverse
        reverse'' lxReverse (x:rlx) = reverse'' (x : lxReverse) rlx

or

reverse' :: [a] -> [a]
reverse' l = foldl (flip (:)) [] l

or

reverse' :: [a] -> [a]
reverse' l = L.foldl' (flip (:)) [] l

Conclusion and selection

if the order of computation can be reverse, and if for finite lists → use foldl, but….
- if the initial value is the first and the last respectively, and there is at least one element in the list use foldl1
- if the initial value needs to be evaluated first → use foldl' , but…
  - if the initial value also is the first and the last respectively use foldl1'
if the order should be kept or if for infinite lists → use foldr, but…
- if the initial value is the first and the last respectively use foldr1

✎

You could leave a comment if you were logged in.

HaskSheet

Table of Contents

Folds

foldr

foldl

foldl'

Order of execution

Keeping order and beeing fast?

Conclusion and selection

✎