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 parenthesis 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