Warning: The following post is longer than some PhD dissertations, read when you have free time!
So I was playing with Haskell and wrapping my head around typeclasses.
I came across the work of
Bartosz Milewski and I really like the way he can seamlessly translate between C++ and Haskell.
So, I decided to do something similar with the Functor typeclass.
1. The low-down
Functors are things which can be mapped over. This means if you have a function
f , you can apply map it over the functor to get a new functor with
f applied to it.
Lists are functors. You can map a function over a list to get a new list with that function applied to it:
fmap (+1) [1,2,3,4]
=> [2,3,4,5]
fmap (+1) []
=> []
The function
fmap takes a function (in this case
(+1)), and a functor (our list) and maps that function over the functor to produce a new functor. Mapping a function over the empty list gives you the empty list, because there's nothing to do!
2. Uncertainty
Lists aren't the only things that are functors. The
Maybe type is also a functor. Maybe is a type that can have either a value of
Nothing or
Just T, where
T can be anything, an
int, a
char, whatever.
Here's a definition of Maybe in Haskell:
data Maybe a = Nothing | Just a
Let's translate that to C++:
template<typename T>
struct Maybe
{
bool isNothing;
T just;
};
So now, we can have a
Maybe<int>. When
isNothing is true, variables of this type contain Nothing, otherwise, they contain some data in the
just field. Let's write some functions to make it easier to create values of this type:
template<typename T>
Maybe<T> Nothing()
{
Maybe<T> r;
r.isNothing = true;
return r;
}
template<typename T>
Maybe<T> Just(T x)
{
Maybe<T> r;
r.isNothing = false;
r.just = x;
return r;
}
So now, we can do things like this:
Maybe<int> m = Just(5);
Maybe<int> n = Nothing<int>();
Maybe<bool> nb = Nothing<bool>();
Maybe<Maybe<int> > double_maybe = Just(Nothing<int>());
We need an easy way to display these values, so let's overload the
<< operator:
template<typename T>
ostream& operator<<(ostream& out, Maybe<T> m)
{
if (m.isNothing) {
out << "Nothing";
} else {
out << "Just " << m.just;
}
return out;
}
Simple, right? If our Maybe is a Nothing, we print "Nothing", otherwise we print "Just <value>".
That's about all there is to know about Maybe in the context of C++. It's really useful when a function can return a value or nothing.
3. Mapping stuff over Maybe
So how is
Maybe a functor? In order for it to be a functor, there needs to be a function,
fmap, that we can use to map functions over values of type
Maybe.
In Haskell:
fmap (+1) (Just 5)
=> Just 6
fmap (+1) Nothing
=> Nothing
Just like in the list example, mapping
(+1) over
Just 5 gives us a new
Maybe with the value
Just 6.
Notice that mapping a function over
Nothing gives us
Nothing because there's nothing to do, just like in the case of the empty list.
Well, that's awesome and everything, but how do we define
fmap. Let's look at how Haskell does it:
The type signature of
fmap for
Maybe looks like this:
fmap :: (a -> b) -> Maybe a -> Maybe b
And the implementation is like so:
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
We can see from the definition that mapping a function over
Nothing yields
Nothing, and that mapping a function over
Just x will first apply that function to
x and then produce a
Maybe out of the result.
Let's translate this into C++:
template<typename A, typename B>
Maybe<B> fmap(B (*f)(A), Maybe<A> a)
{
if (a.isNothing) {
return Nothing<B>();
}
return Just(f(a.just));
}
Our
fmap takes a function pointer and a
Maybe<A> and returns a
Maybe<B>. Naturally, the function
f must take an
A and return a
B. The implementation is the same as in Haskell. If
a is
Nothing then the result is
Nothing, otherwise we apply
f to the value contained in
a and wrap the result in a
Just.
4. Obeying the law
All functors have to obey two laws in order for
fmap to make sense.
1.
fmap(id, F) == id(F). Where
id is the identity function and
F is a functor.
2.
fmap(fDotg, F) == fmap(f, fmap(g, F)). Where
f and
g are functions, and
fDotg is
f(g(x)).
The identity function is simply a function that returns its parameter without doing anything, it looks like this in Haskell and C++:
Haskell:
id x = x
C++:
template<typename T>
T id(T x) { return x; }
Naturally, mapping
id over, say,
Just 5 will give us
Just 5. An applying
id to
Just 5 will also give us
Just 5.
Does our C++ definition obey this law? Try the following code
int (*idfn)(int) = id;
Maybe<int> m = Just(5);
Maybe<int> l = fmap(idfn, m);
Maybe<int> n = id(m);
cout << l << endl; // => Just 5
cout << n << endl; // => Just 5
The output for both
l and
n is
Just 5. This means they are equal, so our implementation of
fmap definitely obeys the first law.
The second law of functors (you do
not talk about functors!) is that when you take two functions and compose them together into a third function and map it over the functor, that should give you the same result as first mapping the first function over the functor, and them mapping the second one.
Let's define some stuff:
int f(int x) { return x * x; }
int g(int x) { return 2 * x; }
int h(int x) { return f(g(x)); }
Now we can test our code like so:
Maybe<int> m = Just(5);
cout << fmap(f, m) << endl; // => Just 25
cout << fmap(g, m) << endl; // => Just 10
cout << fmap(h, m) << endl; //=> Just 100
cout << fmap(f, fmap(g, m)) << endl; // => Just 100
The interesting parts are the calls to
fmap(h, m) and
fmap(f, fmap(g, m)).
The first call maps
h (which is just
f(g(x)) over
m. The second one first maps
g over
m and then maps
f over the result. As you can see, the resulting value in both cases is
Just 100, showing that the two calls are equal. This means that our implementation also obeys the second law.
The second law tells us that composing functions and then mapping the composition over a functor is exactly the same as composing calls to
fmap, each with a single function.
In Haskell, this lets you do awesome stuff like:
fmap ((^2) . (*2)) (Just 5)
=> Just 100
The code above first applies the function
(*2) to 5, producing 10, and then applies (^2) to 10, squaring it, to produce 12, and then wraps that up in a
Just and gives it back to us.
5. Conclusion
C++ is a twisted language with a crazy template system that can let you do some cool things.
Today we implemented the
Maybe type and showed how it behaves as a functor by implementing
fmap and demonstrating the two laws.
Next time, if there is a next time, we'll discuss Applicative Functors, they're even cooler than functors, and
Maybe happens to be one of them!
Feel free to ask questions or flame me for this exceedingly long post.