Introduction

I see a lot of people complain about the state of Haskell documentation. Some of the complaints are reasonable. After all, it took me a very long time to understand data families. The documentation on the extension that enables them doesn't really say much about them. But there are persistently recurring complaints that everything is too hard to understand because of all the math and the lack of tutorials.

Those complaints make very little sense to me. The great thing about Haskell is that for many purposes, you don't need to understand the math or have a tutorial to use a new library. You just need to be able to read type signatures.

A Missing Library

I wanted to use this site to write up the story of my discovery of what data families can do. I was excited about finding a use for a language feature I hadn't previously understood. Data families fill an expressiveness gap in Haskell in a way I appreciate. But I quickly ran into an obstacle. The motivating example for my story was using an operational library to build a DSL with many different interpreters. But while there are two different operational libraries available on Hackage, neither one is available here.

I decided to assemble a minimal library of my own to embed in my write-up. I have some experience with the libraries on Hackage and I find both to be more complex than I really need or want. I decided to use the approach from free-operational to implement my version, because it leans more heavily on third-party libraries. My hope was that those dependencies would reduce the amount of code I'd have to embed.

The hitch in my plan was that I barely knew anything at all about the dependencies. I have the very slightest understanding of the free package. I know that it's for building a monad out of a functor. Somehow. That's the end of what I know about free. The other dependency, the kan-extensions package? I don't know anything about it.

I know they're both based on some heavy-duty math. I don't care. I'm not scared of math, but I haven't dug into category theory much, which is where both of those packages originate. That's because so far, I haven't needed to.

How To Not Math

I started by drawing inspiration from free-operational and sketching out my target API.

{-# LANGUAGE RankNTypes #-}

import Control.Applicative

data Program instr a
instance Functor (Program instr)
instance Applicative (Program instr)
instance Monad (Program instr)

singleton :: instr a -> Program instr a

interpret :: Monad m => (forall x. instr x -> m x) -> Program instr a -> m a

The sketch consists of one data type, three instances for that type, and two functions. That's nice and small.

The documentation for free-operational suggested that the representation for Program is newtype Program instr a = Program (toFree :: Free (Coyoneda instr) a). Like I said, I vaguely know what Free is. Don't ask me what a Coyoneda is. I don't know. I don't care, at least for the purposes of writing a library. But I'm not scared of math. I'm happy to use its results when they work for me, even when I don't understand the underlying theory.

One thing I do know is that the documentation for Free suggests that F is a better choice of data type unless you plan on inspecting the tree built up by the Monad instance. There's nothing in my target API that inspects the tree, so I decided to use F instead of Free.

{-# LANGUAGE RankNTypes, GeneralizedNewtypeDeriving #-}

import Control.Applicative

import Control.Monad.Free.Church
import Data.Functor.Coyoneda

newtype Program instr a = Program (F (Coyoneda instr) a)
                          deriving (Functor, Applicative, Monad)

singleton :: instr a -> Program instr a

interpret :: Monad m => (forall x. instr x -> m x) -> Program instr a -> m a

Thanks to GeneralizedNewtypeDeriving, I got the three instances I wanted for free via F. I still don't know anything about F. I just know that the docs say those instances exist, so I get to use them.

The rest of the work is writing the two functions in the API. singleton is the easier of them, judging by the type signature, so it's what I worked on next.

Program is a newtype wrapper, so singleton starts by applying the wrapper.

singleton = Program . undefined

That undefined needed to have the type instr a -> F (Coyoneda instr) a. This made the mystery how to create an F. I looked at the documentation to see what functions return an F. The first thing I found in the docs was toF. The full type signature makes it clear this is for converting from Free to F, which is not what I wanted.

That's the only thing that returns an F value explicitly, so I had to look a little harder. The next thing to do was look for something that could return F, and didn't take an F as an argument. There's only one thing I found that fit that pattern, liftF.

Before I was sure I had what I wanted in liftF, I had to make the type of liftF work. I started with (Functor f, MonadFree m f) => f a -> m a. For my purposes, m has to be F (Coyoneda instr). I checked to see if MonadFree has the necessary instance for that to happen. I found Functor f => MonadFree f (F f) in the instance list, which was likely the instance I needed. The functional dependency in the definition of MonadFree means that there can be only one choice of the first argument for any given second argument to MonadFree. That means that instance must apply, and furthermore, it means that f is Coyoneda instr. Progress! I managed to move from needing to figure out how to create an F to needing to figure out how to create a Coyoneda.

singleton = Program . liftF . undefined

Given the types of singleton and Program . liftF, the undefined needed to have the type instr a -> Coyoneda instr a. And a quick scan through the docs revealed liftCoyoneda, which is exactly the necessary type.

{-# LANGUAGE RankNTypes, GeneralizedNewtypeDeriving #-}

import Control.Applicative

import Control.Monad.Free.Church
import Data.Functor.Coyoneda

newtype Program instr a = Program (F (Coyoneda instr) a)
                          deriving (Functor, Applicative, Monad)

singleton :: instr a -> Program instr a
singleton = Program . liftF . liftCoyoneda

interpret :: Monad m => (forall x. instr x -> m x) -> Program instr a -> m a

I still don't know a thing about what F or Coyoneda mean. But it isn't really slowing me down.

The last remaining piece of my target API is interpret. This one looks a bit tougher, but how much of that is the type signature being more complex? Nearly all of the complexity in that type signature is describing the polymorphic function which is the first argument. I don't need to do anything with that argument other than apply it in the right place, so I can safely ignore that complexity.

To get my bearings, I started with a minimal skeleton:

interpret f (Program p) = undefined

I began to search through F's docs again, looking for something that looked at least partially like Monad m => F (Coyoneda instr) a -> m a, or that could be a helpful building block for it. There were three immediate candidates: fromF, iterM, and retract.

fromF involves a MonadFree constraint on the m, and I wanted any Monad m, so that's too restrictive. retract has the limitation that the m it produces must be the same as in the input, which is also too restrictive.

So I came to the conclusion it must be iterM, somehow. iterM also has another argument, probably a conversion function. I have no idea where its type signature came from, or what that says about the internals of F. But I didn't need to understand those things, I just needed to be able to supply arguments of the correct type. The extra argument is also helpful in providing a way to use f in the call to iterM. If I could fit it in there, it would mean that interpret is just a specially-crafted call to iterM, which would be convenient.

Putting together the known types, I had the following code:

{-# LANGUAGE RankNTypes, GeneralizedNewtypeDeriving #-}

{-# LANGUAGE ScopedTypeVariables #-}

import Control.Applicative

import Control.Monad.Free.Church
import Data.Functor.Coyoneda

newtype Program instr a = Program (F (Coyoneda instr) a)
                          deriving (Functor, Applicative, Monad)

singleton :: instr a -> Program instr a
singleton = Program . liftF . liftCoyoneda

interpret :: forall m instr a. Monad m => (forall x. instr x -> m x) -> Program instr a -> m a
interpret f (Program p) = iterM eval p
  where
    eval :: Coyoneda instr (m a) -> m a
    eval = undefined


main = putStrLn "It must have type-checked successfully"

The ScopedTypeVariables extension was a temporary addition to help machine checking of my understanding of the types in use. It allowed me to be sure that I've got the correct type signature on eval by running GHC against the code and verifying that it compiled. I made the code block above active because that allows this site to compile and execute it too.

This felt close to done. The types all seemed to fit together correctly. There's just one that hadn't been filled in yet. All that remained was implementing eval, knowing that it must use f. Back to the docs for Coyoneda!

Fortunately, it's a small module. I want something that will eliminate the Coyoneda type constructor, so I can immediately reject about half the module. There are lowerCoyoneda and lowerM. Neither of them quite work, though. Each would introduce a new constraint on the type instr, which is otherwise unconstrained. That's not acceptable, so I needed to look elsewhere.

The next step was looking at the instance list for F. I needed something that didn't put any constraints on instr, which ruled out most of the instances. Of the three remaining instances, none provide anything helpful.

There was one last place to look. This was actually the part that took me the longest to remember when I was first implementing this. There's one more way to interact with values of a data type than functions that operate on them. You can pattern-match on the constructor that built them.

interpret :: forall m instr a. Monad m => (forall x. instr x -> m x) -> Program instr a -> m a
interpret f (Program p) = iterM eval p
  where
    eval :: Coyoneda instr (m a) -> m a
    eval (Coyoneda g i) = undefined

Unfortunately, I couldn't annotate g and i with type signatures to have GHC check them for me. They involve an existential type variable that there's no way to specify in GHC's syntax, so I just have to describe the types informally here.

g is a function b -> m a, for some type b. i is a value of type instr b, for the same unknown type b. I needed to put those together with f :: forall x. instr x -> m x using the knowledge that m is an instance of Monad and come up with a value with the type m a. Fortunately, that unknown type b fit together perfectly with f's polymorphic type. The first step had to be f i :: m b, because it's the only way to use f. With f i :: m b and g :: b -> m a, I had f i >>= g :: m a, still without knowing what type b is. And now the b is gone from the type. Even more successfully, what I have left matches exactly the type eval is supposed to return. This had to be it!

Of course, even in Haskell, compilation doesn't guarantee correctness. I still have to verify that. Here's a silly little test of it all together:

{-# START_FILE main.hs #-}
{-# LANGUAGE GADTs #-}

import Control.Monad.MiniOperational

data Demo a where
    GetNumber :: Demo Int
    PrintSomethingLike :: Int -> Demo ()

getNumber :: Program Demo Int
getNumber = singleton GetNumber

printSomethingLike :: Int -> Program Demo ()
printSomethingLike = singleton . PrintSomethingLike

runDemo :: Program Demo a -> IO a
runDemo = interpret vaguelyEval
  where
    vaguelyEval :: Demo a -> IO a
    vaguelyEval (GetNumber) = return 7 -- the best number
    vaguelyEval (PrintSomethingLike x) = do
        putStrLn $ " ** " ++ show x ++ " **"

main :: IO ()
main = do
    x <- runDemo $ do
        a <- getNumber
        printSomethingLike $ a - 1
        printSomethingLike $ a + 1
        fmap ((,) a) getNumber
    print x


{-# START_FILE Control/Monad/MiniOperational.hs #-}
{-# LANGUAGE RankNTypes, GeneralizedNewtypeDeriving #-}

module Control.Monad.MiniOperational
    ( Program
    , singleton
    , interpret ) where

import Control.Applicative

import Control.Monad.Free.Church
import Data.Functor.Coyoneda

newtype Program instr a = Program (F (Coyoneda instr) a)
                          deriving (Functor, Applicative, Monad)

singleton :: instr a -> Program instr a
singleton = Program . liftF . liftCoyoneda

interpret :: Monad m => (forall x. instr x -> m x) -> Program instr a -> m a
interpret f (Program p) = iterM eval p
  where
    eval (Coyoneda g i) = f i >>= g

Not only does it compile, it works!

Conclusion

I still don't really understand free. I definitely don't have a clue what kan-extensions are in general, or what Coyoneda is specifically. Those are math topics deep in the realm of category theory. But I was able to use the libraries without the slightest clue about the math behind them. I didn't need a tutorial. I'm not even sure what tutorial could possibly have helped – unless you decide this article is a tutorial that should have been titled "How to Free Coyoneda".

I was able to use the absolutely fantastic documentation we call type signatures to quickly figure out how to assemble pieces I don't fully understand into an effective final result. The whole process of doing this from scratch the first time only took about an hour, and that was including the decision of which implementation strategy I was going to use. This is why most Haskell libraries don't have tutorials. They already have better documentation than most tutorials could ever hope to be.

Of course, I'm not saying that libraries can't benefit from tutorials. lens benefits greatly from its myriad tutorials. That's because it has some of the most ridiculously abstract and flexible type signatures I've ever seen. Flexibility makes it possible to combine more things in more ways, such that types provide less guidance, and tutorials fill in some of that guidance. But a complaint that you can't use most libraries because they involve math you don't understand and don't have any tutorials? That's one of the silliest things I've ever heard. They have type signatures! Look what I was able to do in this case with just some knowledge of types and an idea what my goal was.

I'm not special. Anyone can learn to do this. All it takes is for people to focus on what's present and how useful it really is.

Discussion

Discussion of this article can be found on reddit and hacker news.