### What the fold

Functional programming fanbois love to explain the concepts like func composition and partial application using higher order funcs like `map`

`filter`

and `reduce`

, these make writing functional code quite easier but are not really exclusive to FP cause even our boi python has a nifty `functools`

with these functions that run over an iterable, while map and filer return an iterable, reduce returns a single element in the type of the iterable. PL notes on these funcs

1

reduce(lambda x, y: x+y, [1,2,3,4,5]) # Returns 15

This is a higher order function because `reduce`

takes a function as an argument & this function essentially runs across the iterable kinda like a for loop thro every element

```
f(f(f(f(1,2),3),4),5)
((((1+2)+3)+4)+5) = 15
```

This is essentially what **Fold** does, It literally folds the iterable with the function, With reduce this function get applied left to right so its analogous to `foldl`

there is another typa fold `foldr`

which we can write as

1

reduce(lambda x, y: y + x, [5,4,3,2,1])

### Universality of Fold

Fold is somewhat special among the higher-order functions, first of all we can easily implement map and filter using just fold. In fold we really need an explicit description of the order of operations whereas map & filter care just about the order of the list.

Universality property of fold states that **if your recursion conforms to a certain form it can be transformed into fold** according to some formal rules. And conversely, every fold can be transformed into a recursion of that kind

### Folding Left vs Right

There are two types of folds: `foldl`

and `foldr`

. In `foldl`

as we discussed we move from left to right whereas with `foldr`

we move right to left & in the opposite direction

1
2

foldl : 1->2->3->4->5
foldr : 2<-3<-4<-5<-1

Together they kinda form this cycle so its kind of a satisfying fold ngl

Since addition is an associative and commutative operation it gives the same result with left and right fold, so let’s use subtraction like a bunch of sad people

1

Seq(1,2,3,4,5).foldLeft(0)(_ - _)

This would process from left to right with this paranthesis and return -15

```
(((((0 - 1) - 2) - 3) - 4) - 5)
((((- 3 - 3) - 4) - 5)
((-10)-5)
- 15
```

same operation but using foldright

1

Seq(1,2,3,4,5).foldRight(0)(_ - _)

```
(1 - (2 - (3 - (4 - (5 - 0)))))
(1-(2-(3-(-1))))
(1-(2-(4)))
(1-(-2))
3
```

These function needs not act on a list necessarily, we can design fold-like functions on other algebraic data types and structures, like various sorts of trees. One writes a function which recursively replaces the constructors of the datatype with provided functions, and any constant values of the type with provided values. Such a function is generally referred to as a catamorphism.

### Writing Foldl using Foldr

This can be written based on a very simple property. Take the func below, here f and g are functions running an arbitrary operation #

```
f(t) = t # 10
g(t) = (t # 20) # 10
```

Now we can write this as

```
g(t) = f(t # 20)
```

since the execution needs to be in a different direction it makes sense deferring the execution of the function until it gets to the very last element of the List in the other direction

The coolest implementation of this in in Haskell

1
2

myfoldl f z xs = foldr step_f id xs z
where step_f x g a = g (f a x)

We can also write this in scala

1
2

def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)

Scala implementation: https://github.com/fpinscala/fpinscala/blob/first-edition/answerkey/datastructures/13.answer.scala

### Links

- https://stackoverflow.com/questions/17136794/foldleft-using-foldright-in-scala#17137030
- https://stackoverflow.com/questions/6172004/writing-foldl-using-foldr
- http://www.cs.nott.ac.uk/~pszgmh/fold.pdf
- https://wiki.haskell.org/Foldl_as_foldr

A lot of cool concepts involving category theory can be unpacked here, which I know very little/ nothing about so I just skeeted that whole dimension for this blog but I hope one day I learn more about it, some links about that for future me