What does it mean by Folding or Reducing a data structure?
Folding or Reducing is the notion of creating a summary value from a list of values contained inside a certain structure. The structure can be as simple as list of values or a complex structure. The way one will want to reduce the structure is something that will depend on the end goal or the structure of data. Folding or Reducing generalizes this notion which are also known as Catamorphisms.
Deriving a fold function in Haskell
I will be providing the code examples in Haskell but they should be generic enough to understand the concept. Lets say we have the following list of values
and we want to know the sum of all these values. In the imperative world we would start with a loop of some kind which will iterate over the values and add them
1 2 3 4 5
now say we also need to compute the product of all values in the list, we can do something like following
1 2 3 4 5
Similary we may need to find the maximum or minimum of the values. And we are only considering a simple list, it can a tree or anything else. But the notion of generating a summary value from a structure remains the same.
We programmers are lazy and don’t like to write too much boilerplate code. So it would be cool if we could generalize this notion of reducing structures.
What do we need for that, we need a stuructre of some kind, we need a binary operation of some kind (i.e
*) which takes two values and generate a single value.
And we also need an initial value to start with which is
1 above, if we look carefully we will see the initial value is related to the operation. It’s a unit value for the
operation like if you add
0 to something, it doesn’t change, same for
1 and multiplication.
Lets define the
fold function in Haskell,
1 2 3 4 5 6 7 8 9 10
In the type signature of
b are type variables so they can be of any types. The definition above is the called
there’s also another fold called
foldl, their implementation differs on the recursive case but details about that can be put off for
Usage of the fold function
1 2 3 4 5
I am not going to go any further in this blog post but a lot can be done using fold.
But before finishing lets have a look at how a simple call to
fold is evaluated under the hood,
by writing out all the recursive calls
1 2 3 4 5 6 7 8
Most languages has some kind of
fold function now. Hope you understood how folds works generally.
So go ahead and read up on how to reduce an
array or a similar data structure in your favorite language and start using it.