## Sunday, October 4, 2015

### List comprehensions in C++ via the list monad

As explained in Monads for functional programming by Philip Wadler, a monad is a triple $(t, unit, *)$. $t$ is a parametric type, $unit$ and $*$ are operations:

  val unit : α -> α t
val ( * ) : α t -> (α -> β t) -> β t


$m * \lambda\;a.n$

as, "perform computation $m$, bind $a$ to the resulting value, and then perform computation $n$". Referring to the signatures of $*$ and $unit$, in terms of types we see $m$ has the type α t, $\lambda\;a.n$ has type α -> β t and the whole expression has type β t.

In order for $(t, unit, *)$ to be a monad the operations $unit$ and $*$ need satisfy three laws :

• Left unit. Compute the value $a$, bind $b$ to the result, and compute $n$. The result is the same as $n$ with value $a$ substituted for variable $b$.

$unit\;a * \lambda\;b.n = n[a/b]$.

• Right unit. Compute $m$, bind the result to $a$, and return $a$. The result is the same as $m$.

$m * \lambda\;a.unit\;a = m$.

• Associative. Compute $m$, bind the result to $a$, compute $n$, bind the result to $b$, compute $o$. The order of parentheses doesn't matter.

$m * (\lambda\;a.n * \lambda\;b.o) = (m * \lambda\;a.n) * \lambda\;b.o$.

Lists can be viewed as monads.That is, there exist operations $unit$ and $*$ that we may define for lists such that the three monad laws from the preceding section hold.

#include <list>
#include <iterator>
#include <type_traits>
#include <algorithm>
#include <iostream>

/*
*/

//The unit list containing 'a'
/*
let unit : 'a -> 'a t = fun a -> [a]
*/
template <class A>
std::list<A> unit (A const& a) { return std::list<A> (1u, a); }

//The 'bind' operator
/*
let rec ( * ) : 'a t -> ('a -> 'b t) -> 'b t =
fun l -> fun k ->
match l with | [] -> [] | (h :: tl) -> k h @ tl * k
*/
template <class A, class F>
typename std::result_of<F(A)>::type
operator * (std::list<A> a, F k) {
typedef typename std::result_of<F(A)>::type result_t;

if (a.empty ())
return result_t ();

result_t res = k (a.front ());
a.pop_front ();
res.splice (res.end (), a * k);

return res;
}

The invocation $unit\;a$ forms the unit list containing $a$. The expression, $m * k$ applies $k$ to each element of the list $m$ and appends together the resulting lists.

There are well known derived forms. For example, $join\;z$ is the expression $z * \lambda\;m. m$. In the list monad, it results in a function that concatenates a list of lists.

//'join' concatenates a list of lists
/*
let join : 'a t t z = z * fun m -> m
*/
template <class A>
std::list <A> join (std::list<std::list<A>> const& z) {
return z * [](auto m) { return m; };
}

The function $map$ is defined by the expression $map\;f\;m = m * \lambda\;a.unit\;(f\;a)$.
//'map' is the equivalent of 'std::transform'
/*
let map : ('a -> b') -> 'a t -> 'b t =
fun f -> fun m -> m * fun a -> unit (f a)
*/
template <class A, class F>
std::list<A> map (F f, std::list<A> const& m) {
return m * [=](auto a) { return unit (f (a)); };
}


## List comprehensions

List comprehensions are neatly expressed as monad operations. Here are some examples.
int main () {

//l = [1, 2, 3]
std::list<int> l = {1, 2, 3};

//m = [1, 4, 9]
auto m = l * [](int x) { return unit (float (x * x)); };

//n = l x m = [(1, 1), (1, 4), (1, 9), (2, 1), (2, 4), (2, 9), ...]
auto n = l * ([&m](int x){ return m * ([=](float y){ return unit (std::make_pair (x, y)); });});

return 0;
}