When you start with functional programming you will probably meet
filter which are
pretty useful functions.
map is used to transform by applying a function over a structure.
allows you to give a predicate (a function that returns a boolean). Let's see an example written in
(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
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
((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)))
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.
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
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
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.