The Identity Monad

This is a definition of the Identity monad in haskell, for reference. This is using the relatively new Applicative typeclass between Functor and Monad.

import Control.Monad

data Id a = Id a deriving Show

instance Functor Id where
    fmap f (Id x)   = Id (f x)

instance Applicative Id where
    pure x          = Id x
    Id f <*> Id x   = Id (f x)

instance Monad Id where
    (Id x) >>= f    = f x

Id wraps a single value. There is no empty state. The mapping function, fmap, simply applies the a funtion to the value being wrapped. The function (<*>), also known as ap, takes a wrapped function, applies it to a wrapped value, and returns it wrapped up. The function pure, which is the same as return, just constructs an Id with the value in it. The bind function (>>=) does the same thing, only with a function that returns a wrapped value.

The basic data structure for the Identity monad is fairly trivial. It's a generic type, and holds a single element, privately, of that type. I am ignoring any issues about reference types, non-copyable types, non-moveable types, etc. as distractions. I'm also assuming it's default constructable, for simplicity.

template <typename T>
class Identity {
    T t_;

  public:
    Identity() : t_(){};
    Identity(T const& t) : t_(t){};

    // ...
};

In particular, there are no accesors for the T t_ being held. Values go in but they can't get out. At least not yet, and not without side-effect using functions. This is why it's sometimes used as Taint, where you can not lose track of the data coming from outside and being untrusted.

To make a data structure a Functor a fmap function needs to be provided that satisfies certain requirements. It also turns out that if there is such a function, for a particular data struture, all of the implmentations are isomorphic. So there's basically only one for a particular data structure. Fmap for a functor F takes two arguments, a function from T->U, an F<T>, and it will return an F<U>. Although, for C++ this is a bit over-restrictive, and we probably want to be able to apply any function where the template type of the Identity can be used to call the function being mapped. Fortunately C++17 added some traits to work with invocables, and we can use std::invoke_result_t to both detect if a call can be made, and determine the type of the result.

template <typename U, typename Func>
auto fmap(Identity<U> const& i, Func const& f)
    -> Identity<std::invoke_result_t<Func, U>> {
    using V = std::invoke_result_t<Func, U>;
    return Identity<V>{std::invoke(f, i.t_)};
}

It's also declared as a friend, so that it can have access to the internally held t_.

There are two "laws" for how fmap must behave

-- identity preserving
fmap id = id

-- Composition
fmap (f . g) = (fmap f) . (fmap g)

The first one says that fmaping the identity function won't change the object, so it's equivalent to just the identity function. For Identity, this is straightforward to show, since the held value isn't going to be changed, the result won't change the value of the Identity. We can write an equality test for Identity:

template <typename T, typename U>
bool operator==(Identity<T> t, Identity<U> u) {
    return t.t_ == u.t_;
}

template <typename T, typename U>
bool operator!=(Identity<T> t, Identity<U> u) {
    return !(t == u);
}

It's expressed as a non-member, in order to support allowed conversions between T and U. So we can compare Identity<int> and Identity<long> the same way we can compare int and long.

The second law is more interesting. It's expressing that you can distribute fmap over function composition. Chaining functions works transparently. with appropriate adjustment of the types of the functions. So what does applying fmap to a function, without a Functor object like Identity do? It's a higher order function, one that takes and returns a function.

template <typename Func>
auto fmap(Func const& f) {
    // maps (T -> U) -> (Identity<T> -> Identity<U>)
    return [f](auto t) { return fmap(t, f); };
}

In haskell this is natuaral, and does not need a separate defintion because of currying. In haskell if you have a function of type (T -> U) -> F<T> -> F<U>, it is both a function taking one argument, and returning a function, and a function taking two argument and returning a value. Both (T->U) -> (F<T> -> F<U>) and (T -> U), F<T> -> F<U> are true, depending on how many arguments you supply.

The operator (.) in haskell has type (.) :: (b -> c) -> (a -> b) -> (a -> c), so f . g is g(f()), more function chaining. We can either lift the the function (a -> c) into F<a> -> F<c>, or we can chain together F<a> -> F<b> into F<b> -> F<c> and get the same result. This is a natural property of container-like Functors, like Identity, or an optional, or std::vector.

It's surprisingly tricky to get a good identity function, one that really returns the same object in the C++ sense. This is the one I use:

constexpr auto identity = [](auto &&v) -> decltype(auto)
{
    return std::forward<decltype(v)>(v);
};

A short example, from a test case of using the two argument fmap:

Identity<int>  i;
Identity<long> l;
Identity<char> c;

auto twice = [](auto z) { return 2 * z; };
auto i2    = fmap(i, twice);
auto l2    = fmap(l, twice);
auto c2    = fmap(c, twice);

ASSERT_EQ(Identity{0}, i2);
ASSERT_EQ(Identity{0L}, l2);
ASSERT_EQ(Identity{'\0'}, c2);

Identity<int>  i3(3);
Identity<long> l3(3);
Identity<char> c3(3);

auto i6 = fmap(i3, twice);
auto l6 = fmap(l3, twice);
auto c6 = fmap(c3, twice);

ASSERT_EQ(Identity{6}, i6);
ASSERT_EQ(Identity{6L}, l6);
ASSERT_EQ(Identity{'\6'}, c6);

And the one argument form, where the only difference is we can use the fmapped lambda on all of the Identity instances:

Identity<int>  i;
Identity<long> l;
Identity<char> c;

auto twice     = [](auto i) { return 2 * i; };
auto fmapTwice = fmap(twice);

auto i2 = fmapTwice(i);
auto l2 = fmapTwice(l);
auto c2 = fmapTwice(c);

ASSERT_EQ(Identity{0}, i2);
ASSERT_EQ(Identity{0L}, l2);
ASSERT_EQ(Identity{'\0'}, c2);

Identity<int>  i3(3);
Identity<long> l3(3);
Identity<char> c3(3);

auto i6 = fmapTwice(i3);
auto l6 = fmapTwice(l3);
auto c6 = fmapTwice(c3);

ASSERT_EQ(Identity{6}, i6);
ASSERT_EQ(Identity{6L}, l6);
ASSERT_EQ(Identity{'\6'}, c6);

Fmap, and the Functor laws, gives a way of applying chains of functions to a Functor object and know that the application will behave sensibly. The equivalent STL algorithm is std::transform, however that requires that there be iterators for the Functor, which means it can not be used for Functors like std::optional. If it were, then we could write code like

std::optional<int> mult(std::optional<int> o1, std::optional<int> o2)
{
    for (auto const& a : o1)
    {
        for (auto const& b : o2)
        {
            return a*b;
        }
    }
    return {};
}

The core function (a * b) is also something that fmap can't deal with directly. Fmap deals with functions of one argument, and this has two. It's int -> int -> int, not int -> int. That's what Applicative is about.

Applicative is a little unnatural in C++. It arises via partial application, which functional languages usually have a direct syntax for, while in C++ we have at best lambda capture, and at worst std::bind, or the late, and unlamented, std::bind1st. The idea, though, is that you can treat a function like (*), multiply, with the type int -> int -> int as a function that takes an int and returns a function with type int -> int. And it is useful to be able to do this with Functors.

Applicative introduces two operators in Haskell, one is an infix version of fmap, and the other is new, and exists to deal with chaining multi-argument functions.

(<$>) :: Functor f => (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

Infix notation, putting the operation in the middle of the arguments, can improve readability and ergonomics. It's one of the reasons the Uniform Function Call Syntax proposal gets traction. It's useful and natural to be able to say things in noun verb order, and is one of the attactions of member functions in the first place. There are libraries, such as Hana, that provide mechanisms to be able to infix funtions with syntax like f <fmap> x, which would translate to fmap(f, x). Note this doesn't match the argument order of the fmap I've used so far. The ergonomics of C++ dictate that functions that might take lambdas put that argument last, unless there is a compelling reason otherwise. API design work is hard.

The new function (<*>), also known as ap, takes a function wrapped in a Functor and applies it to an object wrapped in the Functor, and returns the result wrapped in the Functor. That function usually comes from fmaping, so you will see a chain of <$><*><*>… providing arguments to the function. For Identity this will just be calling the function with the contents. Often with the pure function as part of it, which is the other piece that Applicative introduces, with a terribly misleading name. The pure function takes a value and lifts it into the Functor in the most natural way possible. For container-like Applicatives, that is putting a single value into the container.

pure :: Applicative f => a -> f a

Pure is also known as return for Monad, and also known as unit. All of these are somewhat misleading names. For C++ I tend to prefer make. This is generally a constructor, but we want to disambiguate constructor calls with control parameters. That is, we want to be sure we're calling the constructor of std::vector that makes a std::vector<size_t> that has one element, not a std::vector<unsigned long> that has size_t elements, all zero. In the case of the identity monad, make is pretty simple to implement.

template <typename T>
Identity<T> make(T t) {
    return Identity<T>{t};
}

If I wanted a more fully general make that handled other Applicative generic types, it would be a bit more complicated. If I want something like:

    Identity<int>           i  = make<Identity>(1);
    Identity<Identity<int>> ii = make<Identity>(i);

where I can parameterize the make function on the template type parameter, it's a bit more complicated, because we can't partially specialize a function, and we want to be able to on the Value type of the Identity template. The standard trick is to delegate to a class template that is partially specialized. The base template looks like

template <template <typename> typename Ap, typename Value>
struct Applicative {
    Ap<Value> make(Value const& v);
    Ap<Value> make(Value&& v);
};

specialized as

template <typename Value>
struct Applicative<Identity, Value> {
    typedef typename std::decay<Value>::type V;
    Identity<V> make(V const& v) { return Identity<V>{v}; }
    Identity<V> make(V&& v) { return Identity<V>{v}; }
};

so that a make function looks like

template <template <typename> typename Ap, typename Value>
Ap<typename std::decay<Value>::type> make(Value const& v) {
    Applicative<Ap, Value> a;
    return a.make(v);
}

The base Applicative type allows writing generic code against different Applicative types. We'll come back to that in a bit.

The ap function, takes a function lifted into the applicative and a value lifted into the applicative, and invokes the function on the value. For Identity, this is just function invocation. For other Applicatives it can be more complicated, but it is always some variation on calling functions. Since there's no way of getting a value out of the Identity, ap needs to be a friend or member.

template <typename T>
class Identity {
// ...
    template <typename Func, typename U>
    friend auto ap(Identity<Func> const& f, Identity<U> t)
        -> Identity<std::invoke_result_t<Func, U>>;
// ...
};

template <typename Func, typename U>
auto ap(Identity<Func> const& f, Identity<U> t)
    -> Identity<std::invoke_result_t<Func, U>> {
    return std::invoke(f.t_, t.t_);
}

A function wrapped in an applicative context shows up when you partially apply a function to an applicative. That is if you had a function like add

auto add(int a, int b) -> int {return a + b;}

which takes two ints and returns an int, and you bind the first argument, returning a function from int to int

auto bind_add = [](int a) {return [a](int b){return add(a, b);};};

so instead of a function (int, int) -> int, we have a function (int) -> (int -> int) and we fmap that function, where fmap takes a function (a -> b) and gives you a function (a -> F<b>), so the fmap gives you a function a function (int -> F<(int -> int)>). And then that function is something we can use for ap

    Identity<int> i3(3);
    auto partial = fmap(i3, bind_add);
    // partial is Identity<int -> int> (roughly)
    Identity<int> i4(4);
    Identity<int> k = ap(partial, i4);
    ASSERT_EQ(Identity<int>(7), k);

In Haskell, where partial application comes built into the syntax of the language, this is all much more natural. The expressive power comes in cases where ap is more than just simple function application, as it is for the Identity applicative. Applicatives like Maybe or Expected can short circuit evaluation, for example. For multivalued functions, like List, the eventual result is the cartesian product of all the parameters, in a list.

Another way of looking at ap involves the curry conversion of a multiparameter function, named after Haskell Curry. A curry converts a function from something called like f(a,b,c) to something called like f(a)(b)(c), where each call returns a function taking a single parameter, an the final result is the same.

    auto curry1 = [](auto func) {
        return [func](int a) {
            return [func, a](int b) {
                return func(a, b);
            };
        };
    };
    auto g = curry1(three);
    auto h = g(3);
    ASSERT_EQ(7, h(4));

Here curry1 unrolls a func(int, int) -> int into a function that takes an int and returns a function taking an int returning an int. It's a straightforward generalization of bind_add from above. We can tale the curried function g, fmap it over an Identity<int> and then apply that partially bound function to another Identity<int>, as so:

    Identity<int> id3(3);
    Identity<int> id4(4);
    auto partial2 = fmap(id3, g);
    Identity<int> id7 = ap(partial2, id4);
    ASSERT_EQ(Identity<int>(7), id7);