# Why you should know fold

- concepts
- functional
- clojure
- haskell

When you start with functional programming you will probably meet `map`

and `filter`

which are
pretty useful functions. `map`

is used to transform by applying a function over a structure. `filter`

allows you to give a predicate (a function that returns a boolean). Let's see an example written in
clojure:

```
(map #(* 2 %) (filter odd? (range 10))
; => (2 4 6 8 10)
```

## Writing map and filter in terms of fold.

A good exercise would be write both in terms of `fold`

. Before that, `fold`

is also know as `inject`

,
`reduce`

, `accumulator`

and maybe other names that I'm not aware of.

```
(reduce + '(1 2 3))
; => 6
```

This is the most trivial example. It could be represented as `(+ (+ 1 2) 3)`

, in this case we are
accumulating the sums of each element in the list.

```
(defn map [f coll]
(reverse (reduce (fn [xs x]
(cons (f x) xs)) '() coll)))
```

We defined a `map`

function over collection using reduce. We apply `f`

to each element in the collection
and concatenate it into the accumulated list. We needed to use `reverse`

because the reduce reads
from left to write, and `cons`

created a linked list in reverse order, where the last element add
is the `head`

.

```
((f a3) ((f a2) ((f a1))))
```

Writing filter is pretty simple:

```
(defn my-filter [f coll]
(reverse (reduce (fn [xs x]
(if (f x)
(cons x xs)
xs)) '() coll)))
```

Similar to `map`

, the difference is that we check if the element returns true from predicate function,
if so it adds to the accumulated list, otherwise ignore it, and return the current accumulated list.

## Foldable type

Haskell has a Foldable type class which defines how a data structure can be folded. In the previous example, I showed the list data structure, which is the most common one.

In functional programming, fold (or reduce) is a family of higher order functions that process a data structure in some order and build a return value. - Haskell Wiki

And it has the following type class:

```
class Foldable a where
foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
```

Be calm, I'll not dig deep into it here, because there a lot in just those 3 lines. Let's look at
the interesting parts. It says that a foldable type needs to define `foldMap`

and `foldr`

.

So lets consider the scenario that we have a `Tree`

data structure, we could have operations to
map over it or filter for specific nodes. If we implement `Tree`

as foldable, we can have those functions!

I'm oversimplfying things here. But my point here is that `map`

and `filter`

are not functions
applicable only to lists, we can have different data types that can be folded to produce a value.

I hope that I was clear enough, I'm still digesting all these concepts and would like to share with you.