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.