Notes on Haskell functors and F#

I've been learning a bit of Haskell lately, and I wanted to share some of what I have learned so far, from a F# perspective. I hope you find these notes useful, and if you find a mistake please let me know. I'll start with a brief explanation of functors and how they translate (or not) to F#.

Functors are basically things that can be mapped over. In F# we have lots of them:

Set.map : ('a -> 'b) -> 'a Set -> 'b Set 
Seq.map : ('a -> 'b) -> 'a seq -> 'b seq 
List.map : ('a -> 'b) -> 'a list -> 'b list 
Array.map : ('a -> 'b) -> 'a [] -> 'b []

See the pattern? If we could generalize this, the signature would look something like this:

map : ('a -> 'b) -> 'a 'T -> 'b 'T

or:

map : ('a -> 'b) -> 'T<'a> -> 'T<'b>

This function is called fmap in Haskell, and it defines the Functor typeclass, one of the most basic typeclasses in Haskell. (I won't talk about typeclasses here, the post would go way out of scope). Unfortunately, .NET's type system isn't flexible enough to express this. Joe Duffy has a great article explaining it for us .NET developers. Actually it seems that OCaml's functors can be encoded in .NET so it would be possible in principle, but quite awkwardly so.

At this point you might be thinking that the concept of functors only applies to collections, but it's actually more general than that. For example, Options are also functors:

Option.map : ('a -> 'b) -> 'a option -> 'b option

Even functions are functors. The map function in this case is the composition operator (<<)

(<<) : ('a -> 'b) -> ('c -> 'a) -> ('c -> 'b)

To make it easier to recognize this as a functor, you might interpret it as:

(<<) : ('a -> 'b) -> "function that takes 'c and returns"<'a> -> "function that takes 'c and returns"<'b>

Haskell's type system is powerful enough to be able to abstract that.

Also, all monads are functors. You can define map in terms of Bind and Return. For example, for async:

let asyncMap f m = 
    async { 
        let! x = m 
        return f x 
    }

asyncMap : ('a -> 'b) -> Async<'a> -> Async<'b>

In the context of monads, map is usually called lift. In fact, in Haskell they're pretty much equivalent, save for class constraints. The name "lift" comes from the notion of lifting a function to operate in the domain of the monad.

The same code as above, desugared:

let asyncLift f m = async.Bind(m, fun x -> async.Return(f x))

For a FParsec monad:

let parserLift f m = parser.Bind(m, fun x -> parser.Return(f x))

Now, F# can't generalize over monads (for the same reasons I mentioned above), but can we still write a generic lift for all monads? Sort of, thanks to inlining and member constraint invocation expressions:

let inline lift builder f m = 
    let inline ret x = (^a: (member Return: 'b -> 'c) (builder,f x)) 
    (^a: (member Bind: 'd * ('e -> 'c) -> 'c) (builder, m, ret))

You can find more generic monad stuff like this in the M<'a> Lib project. Using this generic lift function we can create monad-specific lifts like this:

let asyncLift x = lift async x
let parserLift x = lift parser x

Actually, FParsec already includes lift, although slightly disguised:

(|>>) : Parser<'a,'s> -> ('a -> 'b) -> Parser<'b,'s>

This is lift, only with flipped parameters.

One thing to note about functors is that not everything that satisfies the signature of fmap automatically becomes a functor. There are some laws that functors must obey to have the behavior one would expect. These laws actually come from the definition of a functor in category theory. I'm not going to explain these laws in detail here, you can find good explanations in this article on basic category theory from a Haskell perspective or this one on functors from a Scala perspective.

Haskell developers can test these laws using QuickCheck, so in F# we could try to test them with FsCheck:

open FsCheck
open FsCheck.Prop

let runAsyncRet f a = Async.RunSynchronously (f (async.Return a)) 
let liftId x = runAsyncRet id x = id x 
let liftDist x (f,g) = runAsyncRet (asyncLift (f << g)) x = runAsyncRet (asyncLift f << asyncLift g) x 
Check.Quick liftId 
Check.Quick liftDist

I haven't showed any real-world examples of functors in F#. The lack of ad-hoc polymorphism takes away much of the power of the abstraction, but still many times it's simpler to use lift instead of computation expression sugar for trivial expressions. Moreover it encourages writing simpler, shorter, composable functions, which fits the functional style better. There's a good article on the Haskell wiki against "do notation" (i.e. syntactic sugar for monadic code).

In the next article I'll talk about applicative functors, in my opinion a more interesting abstraction, and I'll show some more concrete real-world examples of how they can be used in F#.