Haskell through Stories: Functors

Dennis J. McWherter, Jr. bio photo By Dennis J. McWherter, Jr. Comment

In my free time I have been playing with Haskell a lot recently. Seeing as this makes me an imperative programmer by day in my day job and a functional programmer by night, I tend to rely on the interwebz and IRC for most of my questions. Upon stumbling around, I have noticed there is a lot of confusion on some fundamental concepts in Haskell. Even those who have read the best Haskell primer on the web seem to have trouble distinguishing Functors, Monads, and Monoids and why each of them is useful. I remember approaching these for the first time and being similarly confused. Truth is, you must think of these concepts as well as your programs in a more mathematical way for any of this to really make sense (see: Category Theory for Computer Science). Specifically, thinking of your program as bits of generic computation which you appropriately glue (read: compose) together seems to be a useful way of thinking. So first thing’s first, put your math hat on (sorry to those of you who left it in your college dorm) and we’ll try to dispel our confusion together.

Functors

In this post, we will start with functors. To be honest, I don’t see many people having much trouble with this one but since it is one of the most straightforward abstractions represented in Haskell, I figure we would work our way through it to setup a framework for attacking Monads and Monoids in future posts (stop cringing: you’ll get it). Haskell defines the Functor type-class as follows:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Many people see this definition and say to themselves, “oh, it’s simply a generalization of map over some type f.” If you clicked on the functors link and read the wikipedia page, you would notice that this justification is a little loaded. Though it must be verified by the implementor, a true Functor “must preserve identity morphisms and composition of morphisms.” What this statement means is that your functor f must support an identity operation (just like X x 1 is identity in multiplication over the reals) and it must also compose (i.e. f(g(x))). This is an awful lot of talking, so let’s see it in action.

Our Story

Suppose you run your own software company and you employ three programmers and some other administrative staff. It’s that time of year where you start thinking about raises, so you need a good metric to rank employees and give them raises. Times are tough, so you choose to ignore your administrative staff and only give raises to programmers which you feel have worked hard; you need to quantify this. After countless nights of thinking, you’ve finally got it. Despite the advice you have read online about employee performance metrics, you think you have finally figured out how to determine employees line-of-code quality: all programmers who wrote an even number lines of code will not receive a raise. You are certain this is the right thing to do. After all, you did the math and any questions about it can wait until next year, right?

image

But time is money and to do this by yourself would be a real hardship, so we’re going to show how we can use functors to our advantage and solve this problem using Haskell.

How to do?

Let’s first show some code:

module Main where

data Employee a = Programmer String a | Other String deriving Show
type LoC = [String]
type Money = Int

instance Functor Employee where
  fmap f (Programmer n v) = Programmer n (f v)
  fmap _ (Other n) = Other n

-- Employees with lines of code
employees :: [Employee LoC]
employees =
  [Programmer "super1337" ["<?php"],
   Programmer "humbleServant" ["int bEndian()", "{", "union {", "int x;", "char c[4];", "} v = 0xdeadbeef;", "return c[0] == 0xde;", "}"],
   Programmer "n00blet" ["public static void main(String[] args) {", "System.out.println(\"woot\");", "}"],
   Other "reallyImportantSecrataryWhoTakesCareOfPrettyMuchEverythingNotSoftware",
   Other "Jim"
   ]

calculateRaises :: [Employee LoC] -> [Employee Money]
calculateRaises = fmap (fmap convert)
  where convert :: LoC -> Money
        convert xs = let len = length xs in
          if len `mod` 2 == 0 then 0 else len * 2

The first thing we should do is see if our instance of Functor is actually a functor. To prove to you that it is, first try running:

let x = Programmer "test" ["a", "b"]
fmap id x
-- Returns: Programmer "test" ["a","b"]
</pre><p>This shows us that our identity property holds. Similarly, we should ensure that our functor composes. More precisely, we should show that fmap'ing a composed function or composing two partially applied fmap functions yields the same results (for the same functions, of course). For example,</p>
<pre class="brush: haskell">
let x = Programmer "test" ["a", "b"]
(fmap (++"!") . fmap head) x
fmap ((++"!") . head) x
-- Both return: Programmer "test" "a!"

Great. It looks like we actually have an employee functor. Notice that we don’t do anything special in our functor; it really simply acts as our lifting function (i.e. take a typical function and apply it within the functor type). So our calculateRaises method actually works by applying the partially applied fmap convert to every element in the list (the outer fmap applies the function to each element in the list).

What just happened?

Let’s take a look at this a little more closely.

image

Other than upsetting both your strongest programmer and your administrative staff, you quickly calculated the amount of money each person earns based on lines of code. Assuming you had some model setup, the only real work here was your business logic (i.e. the convert function) which converted lines of code into money according to the devised scheme.

fmap (and, as a result, Functor instances) was the magic that really made this possible for us. We applied our convert function to a list of Employees by “lifting” our function to the correct type. This allowed us to use our simple and more general convert function instead of using a more specific employeeConvert function which strictly dealt with converting LoC per Employee into Employee’s Money. The distinction seems subtle, but with large programs this makes your computations incredibly reusable.

Anyway, let’s take a look at that substitution:

fmap :: (a -> b) -> [a] -> [b] -- List's fmap
fmap' :: (a -> b) -> Employee a -> Employee b -- Employee's fmap
convert :: LoC -> Money -- Our logic function

(fmap' convert) :: Employee LoC -> Employee Money -- First sub
(fmap (fmap' convert)) :: [Employee LoC] -> [Employee Money] -- Full sub

If you follow the type substitutions (I disambiguated fmap calls with a ’ symbol), you can see how we actually built up this function. The reason this is useful is that it makes it easy for us to think about particular logical units aside from decoration of the context in which its used. What I mean is that– as the boss– you can focus on turning lines of code into money rather than dealing with employee data types, etc.

So now that you have effectively upset your whole office dynamic, you can now share and reuse your LoC -> Money algorithm with the world (and people don’t need to have or use your Employee data type!). Or, on the other hand, you can use it in other areas of your business. For instance, when you want to forecast your revenue for the year based on the value you’re going to be producing from your software. With that in mind, I do suggest you revise this model before actually applying it to the anywhere.

Recap

That was a lot to look at, so what did we learn? First of all, we learned that when you arbitrarily apply mathematical definitions, you typically produce a model which has no correlation to the real world. Also, if you don’t give raises to your staff members who really deserve them, they get angry.

On the other hand, we took a look at what a functor is as well as what it does for us in the context of Haskell. We saw that it provided us power to increase code reuse and ignore implementation details of irrelevant types. In this way we can write functions which describe our important business logic and then simply apply them to whatever relevant types make sense later through substitution. This is an incredibly useful tool to have in our functional tool belt, but it is only one of many. Later on we will continue to discuss monads, monoids, and arrows. Until then, keep working on your compensation models!

comments powered by Disqus