====== Folds ======

  * inspired by [[https://wiki.haskell.org/Fold|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:
    * <code Haskell>
main :: IO ()
main = print (foldr (+) 0 [3::Integer, 5, 7])
</code>
  * 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:<code Haskell>
-- 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)
</code>
  * __immediately returns__ if f does not demand the rest of the recursion
  * can deal with __infinite lists__
  * example:<code Haskell>
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
</code>
    * executes with result:<code>
5000000050000000
</code>
    * executes in approximately __**15 seconds**__ on Intel(R) Core(TM) i5-8400 @ 2.80GHz
    * executes with allocating approximately 8 GByte heap sapce:
      * {{:codesnippets:heapconsumptionfoldr.png?400|Heap consumption}}
  * example, list here is infinite:<code Haskell>
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
</code>
    * executes with result:<code>
5000000050000000
</code>
    * 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:<code Haskell>
-- 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
</code>
  * __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:<code Haskell>
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
</code>
    * executes with result:<code>
5000000050000000
</code>
    * executes within approximately __**2 seconds**__ on Intel(R) Core(TM) i5-8400 @ 2.80GHz
    * executes almost without allocating heap space:
      * {{:codesnippets:heapconsumptionfoldl.png?100|Heap space when using foldl to sum large list of Integers}}
  * example, using infinite list:<code Haskell>
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
</code>
    * will not stop executing, unless memory error stops execution
    * executes allocating heap space, endlessly:
      * {{:codesnippets:heapconsumptionfoldloninfitelist.png?400|Heap space when using foldl to sum infinite list of Integers}}
  * example, using ''sumIfNot __100__'':<code Haskell>
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
</code>
    * executes with result:<code>
5000000050000000
</code>
    * 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:<code Haskell>
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
</code>
  * example:<code Haskell>
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
</code>
    * executes with result:<code>
5000000050000000
</code>
    * 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:<code Haskell>
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
</code>
    * will not stop executing
    * executes with small allocation of heap space
  * example, using ''sumIfNot __100__'':<code Haskell>
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
</code>
    * executes with result:<code>
5000000050000000
</code>
    * 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:<code Haskell>
main :: IO ()
main = 
    do
        print s
        print $ f1 s

s = ['a'..'z']

f1 :: String -> String
f1 s = foldr (:) [] s
</code>
    * executes with following output:<code>
"abcdefghijklmnopqrstuvwxyz"
"abcdefghijklmnopqrstuvwxyz"
</code>
  * example, using foldl:<code Haskell>
main :: IO ()
main = 
    do
        print s
        print $ f1 s

s = ['a'..'z']

f1 :: String -> String
f1 s = foldl (flip (:)) [] s
</code>
    * executes with following output:<code>
"abcdefghijklmnopqrstuvwxyz"
"zyxwvutsrqponmlkjihgfedcba"
</code>
    * 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':<code Haskell>
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
</code>
    * executes with following output:<code>
"abcdefghijklmnopqrstuvwxyz"
"zyxwvutsrqponmlkjihgfedcba"
</code>
    * NOTE: Parameter order of function (:) needed to be flipped as well as for foldl.
  * example, with __not__ commutative operation (''-''):<code Haskell>
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
</code>
    * executes with following output:<code>
[31,7]
[31,7,3]
24
27
-24
27
-24
27
</code>

====== Keeping order and beeing fast? ======

  * use case
    * finite lists
    * large lists
    * order of operations to be kept as is foldr
  * example, using foldr:<code Haskell>
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
</code>
    * executes, with output:<code>
18
21
-50000000
</code>
    * executes within approximately __**15 seconds**__ on Intel(R) Core(TM) i5-8400 @ 2.80GHz
    * executes using large heap space
      * {{:codesnippets:heapconsumptionfoldronnoncommutativeop.png?200|}}
  * example, using ''foldl'' and ''reverse'':<code Haskell>
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)
</code>
    * executes, with output:<code>
18
21
-50000000
</code>
    * executes within approximately __**15 seconds**__ on Intel(R) Core(TM) i5-8400 @ 2.80GHz
    * executes using large heap space
      * {{:codesnippets:heapconsumptionfoldlfronnoncommutativeop.png?200|}}
      * regardless of whether ''L.foldl' '' or ''foldl'' is used
      * regardless of whether alternative ''reverse'' functions are implemented
        * e.g.:<code Haskell>
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
</code>
        * or<code Haskell>
reverse' :: [a] -> [a]
reverse' l = foldl (flip (:)) [] l
</code>
        * or<code Haskell>
reverse' :: [a] -> [a]
reverse' l = L.foldl' (flip (:)) [] l
</code>

====== 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''


===== ✎ =====
~~DISCUSSION~~