Map and Filter on Lists

This is the level of attention to details and of understanding of subtleties that is required for a decent Functional Programming (and this is why it takes 10,000 hours to master).

There is a deep connection captured by the fact that map, filter and concat could be expressed directly in the list-comprehension notation, which goes back to the Set Theory.

These are generalizations of fundamental, if not universal notions (of the mind of an observer).

The fact that the List type is at the core of Functional Programming and has a special treatment (syntactic sugars, built-in special names of the Constructors) is not a coincidence.

It is (an instance of) Functor and Maybe and Monoid and Monad, and a list of ordered pairs (so-called aList) is a universal lookup-table.

One, it seems, like the old-timers, should program with Lists. The discipline will pay back in clarity, brevity, deeper understanding of the problem domain and better, simpler models.

Lists

Most of the time our intuitions about a List as of something long, and it escapes our attention that it could be either empty or just a singleton.

This particular aspect is what the Maybe type captures.

Another fundamental aspect is that once a single value becomes an element of a list it could be only accessed within a list, through the List ADT’s interface.

This corresponds to the mathematical notion of a Functor, which maps mathematical structures, without tearing them apart.

This is not just a metaphor, partially applied map yields a function from a List to a List, so it literally “maps a function” f: a -> b into that function of the type [b] -> [b].

> :type map (+1)
map (+1) :: Num b => [b] -> [b]

Identity and associativity “laws” has to be preserved by any implementation of fmap.

In pseudo-haskell notation:

map id      = id
map (g . f) = map g . map f

This, in turn, is connected with the fact that (++) is associative

(xs ++ ys) ++ zs = xs ++ (ys ++ zs)

which captures the universal fact that one can “put together” pieces of the same structure taken apart in any order.

(h . g) . f = h . (g . f)

is the same notion of putting functions together (as pieces of the same pipeline).

Just as heads and tails of lists must match, domains and codomains have to match too.

Associative property is just a generalization of a universal pattern about linear structures. Addition could be seen as “linear”.

Map

So, this is a generalized notion of modifying (or transforming) a value embedded into some structure.

List comprehension
```
  map f xs = [f x | x <- xs]
```

The classic definition

  map f []     = []
  map f (x:xs) = f x : map f xs

Just as structures could be nested, maps can be nested too.

fmap (fmap f)

is a common idiom.

These could be different fmaps - the inner of a Maybe, and the outer of a List, lets say.

Filter

This is a generalized notion of selection, of such that, of defining a subset or a sub-class.

Hudak’s style with where, common to maths

filter p (x : xs) = if p x then x : rest else rest
  where
    rest = filter p xs

List comprehensions Even more declarative (but not the most), set idiomatic, suggests mathematical notions of such that, and provided p x.

filter p (x : xs) = [x | x <- xs, p x]

Hutton’s style, with guards, OR (disjoint union) branching

filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x : xs)
  | p x       = x : filter p xs
  | otherwise = filter p xs

Ultimately declarative “logical” and “operational”

filter p = fst $ List.partition p

Bird’s style - concatMap, uses list as Maybe

filter p = concat . map (test p)
  where
    test p x = if p x then [x] else []

Here one could see the “empty/non-emopty” aspect of a List (captured in the Maybe type).

Not coincidentally, concat after map are used in one of several definitions of the List Monad, where concat is join.

Concat

This captures the generalized notion of collapsing of a nested structures (one level at a time).

List comprehensions

  concat xss = [x | xs <- xss, x <- xs ]

Bird’s style

concat []       = []
concat (xs:xss) = xs ++ concat xss