Look out; I’ve been digging into Haskell again. I enjoy learning about Haskell, but more than that, I enjoy learning to think in a functional way. Haskell is a particularly good language to facilitate that, as it is arguably the most functional of functional languages. It boasts “pure” functionality, and while some might believe that means it is of no practical use, I think it makes it pretty cool.
While I enjoy my Haskell studies, I still struggle with a few core concepts. For example, I keep having to go back and reread explanations of Functors. I understand them at the time, but it doesn’t stick, and I keep having to come back and read it again. Maybe my appreciation for some of the staples of Haskell would be a little less volatile if I had the experience of implementing them myself in an imperative language like C#.
To implement Functors, there are a few building blocks we’ll need first, and it will be helpful to establish a simple concept map between pieces of Haskell and C#. Let’s start with one of the foundational constructs of the functional world, the map function. The type of Haskell’s map function is defined like this:
This means that the map function takes a function that takes a value of type a and returns a value of type b, and a list of values of type a, and returns a list of values of type b. In fewer words, it takes a function from a to b, and a list of a, and returns a list of b. It takes a function and a list of inputs to it, and returns a list of outputs. You’ve probably seen this kind of thing in other languages. I think I first encountered it in Ruby. Shortly thereafter I was thrilled to see that LINQ had brought this goodness to .NET in the form of the Select extension method on IEnumerable. Of course the LINQ implementation uses the very OO approach of adding an extension method onto the IEnumerable type. Its signature looks like this:
Stare at the two for a minute if you need to; the Haskell type and the C# method signature say exactly the same thing, only stated in reverse order from one another. (And C# takes a heck of a lot more notes to name that tune.)
So the two languages have some common ground to start with. Now we need to get a little bit of Haskell vocabulary under our belts. I will try to describe Haskell constructs in terms of C# constructs as much as possible.
Try to ignore the word class; it’s not like an OO class. A type class in Haskell is closer to an interface in OO. Types can be instances of various type classes much like classes in C# can implement various interfaces. A type class comprises a list of functions, and any type that wants to be an instance of that type class must implement its functions. It might not be too much of a stretch to say it is interface implementation. Each instance type has its own unique implementation of each function, just as each implementing class has its own unique implementation of an interface’s members, affording the system the same benefits of polymorphism that we have always enjoyed in OO.
You can think of a type constructor as something like a generic type in .NET, such as List<T> or Nullable<T>. It can’t stand alone as a type; it needs another type to make it complete. You can’t instantiate a List<T> unless the identifier T is bound to an actual type such as int or string. Type constructors work the same way.
Haskell’s Functor is a particular type class, and it’s pretty simple as type classes go, in that it has only one function, fmap, but it wields some serious power. fmap’s type is defined like this:
This means that, given that a type constructor f is a functor, fmap takes a function that takes an a and returns a b, and an f of a, and returns an f of b. We could express this signature in C# like this:
It is commonly stated that functors are structures than can be “mapped over.” They establish a context that contains a particular type of value, and then they can take a function, apply it to the contained value, and wrap up the result in the same type of context again, returning the new context as the result. Think of the map function we just looked at. It maps functions over lists. It pulls a value out of a list, applies a function to it, and puts the result into a list. Hey, if lists can be mapped over, does this mean that lists are functors? Why, yes, it does. Take another look at the fmap type definition above and think of f as a context. f a represents an a in this context. f b represents a b in the same type of context. Now imagine that context is a list, and therefore that f a is a list of a. As it turns out, map is the list’s implementation of fmap that makes it a Functor instance. Nice!
A C# Implementation
But can we do this in C#? The Select method uses generic type variables to give its parameters the same flexibility that Haskell’s map function has. It uses IEnumerable as its context in place of Haskell’s list. Now we’re looking to define a new generic type that could take the place of IEnumerable. If different functor types have different implementations of fmap, we’re headed for some polymorphism here. If we’re going to implement fmap polymorphically in C# we’ll need an interface and at least one class. Since we’re going OO here, we’ll eliminate the input parameter we included before and replace it with a self reference (this) in the implementation.
First the interface:
Simple enough. Now for a class to implement it. Let’s try a list. It will implement IEnumerable
Now for a bare-bones, boilerplate implementation of IEnumerable
Thanks to System.Linq and the Select extension, MyEnumerable already has the ability to map functions over itself, but it can’t join in any functor games until it implements IFunctor’s FMap. Fortunately, we can have FMap delegate to Select, since it already does the same thing. Select takes the value from the context (MyEnumerable) and applies the function, but it’s still up to us to put the result back into context, which we can easily do by passing it to MyEnumerable’s constructor.
There’s the MyEnumerable-specific implementation. Now let’s just add the explicit interface implementation and have it delegate to the method we just added.
That’s it. We have implemented a functor in C#. Let’s try it out before we move on. Say we have a function that takes an integer and returns a string of its square.
And we have a list of integers that we want to map this function over.
Of course, in C# we tend to love lambdas, and we could just as easily do it that way.
But wait a minute. We haven’t done anything but wrap Select, have we? So far, yes, but think about this: What if the context we want to map over is not a listy kind of thing? Another functor type in Haskell is Maybe a, which is just like .NET’s Nullable<T>. It has a particular type, and it may or may not have a value. Just like a list, it provides a context for particular type of value, only in this case the context is the possibility of there being no value. Let’s throw together our own homegrown nullable class.
The guts are pretty simple.
Now for the FMap implementation. Once again, we take the value from the context, apply the function, and wrap it up in context. In this case, if the MyNullable<TSource> instance has a value, we apply the function and put the result into a new MyNullable<TResult>. If there is no value, we simply return a new empty MyNullable<TResult>.
Now let’s see what MyNullable can do.
Okay, so we have implemented Haskell’s Functor in C#. What is the value in this? Remember the goal of this exercise was not to bring C# something that I thought it needed, but rather to help me understand what Functors are doing for us in Haskell. What I find here is that it’s all about separation of concerns. The benefit of the separation is in the reusability of the functions that we pass to fmap.
Each Functor, or type context, has its own set of concerns that are not the business of any function we might want to map over it. The list and MyEnumerable need to iterate, call the specified function multiple times, and collect the results into a new list. The Maybe and MyNullable need to deal with the absence of a value and possibly not call the specified function at all. This Functor mechanism enables simple functions such as SquareString to be reused in these and limitless other contexts that they are unaware of. Each Functor context can take any simple function, and each simple function can be used in any Functor context. Without the Functor, we would have to code each function-context combination separately. With it, we have a pallette of primary colors that can be combined in unforeseen and beautiful ways.