Nullable Reference Types are FINE, and here’s why

So my friend Steve wrote a long article on why he doesn’t like nulls in C#, and I promised him a good fisking so, of course, the first thing I did last night was to fire up the Ms Marvel finale. It’s very good. This was following by a mini-marathon of black-ish episodes (it’s also very good) and honestly I highly recommend watching those in preference to reading this or Steve’s original article. However, because I’m the living embodiment of XKCD 386, sooner or later I was going to write something on the subject.

Let’s start with his first code example:

Person p = null;

He’s correct in saying that this code would blow up at runtime with no compile-time warnings, and that using null reference types would catch this error. But he fails to include an example of how this would look using Functional.Maybe

Maybe<Person> p = Maybe<Person>.Nothing;

So, what’s different? Well, now C# 9 won’t catch the error and you’ll get a runtime exception. So the Maybe solution is, out of the gate, worse than the straight-forward regular C# example in that it can’t even catch the simplest example in the blog post.

Now, I’m being somewhat disingenuous in that there are other constructions of Maybe that don’t have this problem and indeed the code Steve employs later on in the post doesn’t display this problem. There are other issues, but describing everything wrong with language-ext would take me much longer than I plan to spend and, in any event, I’m a little sick of hearing myself talk about it at length. Let’s move onto the second example:

public void ProcessPerson(Person p) {

Here the contention is that, even in modern C#, you could still be called with a null person. The proffered solution is to insist that we check things for null even when we’ve declared them as not null. This begs the question: why not just declare them as nullable if you think this is a real scenario? Which in turn begs the question: how often does this actually come up in code-bases that use pretty much pure `#nullable enabled? Having used it fairly heavily for three years, I can answer that question quite definitively: the only time I encounter this kind of a problem where something is declared as not-null but isn’t null is when I’ve forgotten to implement a mock. i.e. I’ve only really encountered it whilst writing tests. The issue was never in the code base proper and moreover, the very tests I was writing caught the problem. Code merged down to main? I honestly can’t think of a single instance where this has been a problem.

In theory, yes, programmers can make mistakes and send you invalid values. However, this isn’t a problem unique to null handling and we handle this by being explicit about our expectations. The difficulty with C#7 and earlier where you just didn’t know if something was meant to be nullable or not is already gone.

The acute will observe that the proposed solution: Maybe, doesn’t actually address the problem outlined in the code example, because that’s meant to be employed in circumstances where there might not be a value and this scenario requires a value. What solutions do exist?

  • Only use language constructs that cannot be null. (In practice, I don’t think anyone’s going to adopt “everything is a struct” as a convention in C# outside of one finance shop who will remain nameless).
  • Use a language that doesn’t have these problems. There’s exactly one, it’s called Rust and I highly recommend you check it out. Learning Rust probably isn’t going to help you with your C# coding issues, though.
  • Develop programming practices to reduce the impact of the problem.

Now, the last one is fine, but the most effective practice I’ve found to deal with this is pervasive use of nullable reference types.

Semantics, Shmemantics

Now we get onto one of the big ideas in Steve’s post:

The fundamental thing to observe here is that we don’t know why we were given a null value.

Steve, obviously

A more fundamental thing to observe is that this is true of every value we ever process. We don’t know why we got sent 5 as a security id either. There are programming techniques you can employ where you pass around values with their derivation but: Maybe is not one of them. The vagueness complained about holds just as true regardless of your representation of missing values.

The Meaningless of Null

null means nothing, so what intent can be applied to it?

Steve, again

The phrase “null means nothing” caught my eye because it reminded me of how unnecessarily difficult mathematicians used to make their lives before finally accepting the existence of zero. And leads me to another fundamental observation about all modelling: what the code means is entirely in our own heads and has nothing to do with the code or what it actually does. In this particular case, there’s a mental model that’s helpful and a mental model that’s unhelpful. Thinking of null as “nothing” isn’t a helpful mental model. A better way of understanding null in regular code is “This value is not present” or “This value was not supplied”. Going back to the intent, unless you have a model for the intent of “This value is present”, you’re basically tying yourself up in knots over nothing. (Or Nothing)

I’ll restate this point because it’s extremely important: if you have two things that are operationally identical, if you are treating them as semantically different you have a problem is in your modelling. Platonism, where things have meaning independent of their behaviours, has been discarded in philosophical circles for centuries. The other major popular expression of this idea is the transubstantiation of Eucharist, an idea which, whilst by no means discredited, has at the very least sparked actual wars between subscribers and non-subscribers to the notion.

It is worth mentioning the one operational difference between nullable reference types and Maybe constructs: you can have a “Maybe<Maybe<Person>>” but you can’t have a “Person??”. This can matter if you’re doing heavy levels of functional programming, but in C# I can honestly say it hasn’t come up.

Call Me Maybe

There follows a lucid description of how to use Maybe culminating in the following example:

public static void ProcessPerson(Maybe<Person> p) {
        p => Console.WriteLine(p.Name),
        () => Console.WriteLine("Nothing to process."));

Let’s rewrite that back to regular idiomatic C# code:

public static void ProcessPerson(Person? p) {
    Console.WriteLine(p?.Name ?? "Nothing to process");

An obvious objection is “Well, this is just example code, what does it look like in real world scenarios at scale?”. The answer, sadly, is much, much worse. If you’ve got three Maybes, you’ve now got a chain of three nested callback functions. Not even the fancy syntax provided by `language-ext is going to save you from that horror.

Let’s double down on the point though: in the Maybe example, what happens if p.Name is null? The answer is, of course, that it prints a blank line. Is that the right behaviour? It’s an arbitrary example so who knows, but it probably isn’t. Another observation is that this could happen even without nulls if Name was an empty string or, even worse, a string of whitespace characters. But this goes back to my fundamental observation: Maybe or Option or whatever you want to call it isn’t going to save you from bad input data. Only good programming practice will do that.

You might be asking yourself at this point: so how do languages like Haskell handle this, given that they not only don’t have nulls but don’t even have control flow? The answer is “do notation” which is way beyond the scope of this post, but needless to say, C# doesn’t have it and isn’t likely to any time soon. A related observation is that while Haskell doesn’t have “null”, it most definitely has “undefined” or “bottom” which is, if anything, worse. Even weirder, it turns out that language-ext went to all the effort to introduce it to C#, which is a design decision I would love to discuss with the creator. So how does Haskell deal with this? In short, it doesn’t. There’s even a widely-cited paper explaining how you can, for the most part, just ignore the fact it exists.

Nulls That Map Database Tables

Steve then goes on to give an example of some code that could be remodelled to avoid the use of nulls. Whilst certainly the case that the class can be restructured as he describes for that particular purpose, what if the class is actually needed for multiple purposes and some of those permit nulls? What if, moreover, you don’t know the final purpose when you construct the object? These questions I raise are not just theoretical. A lot of the time, the best modelling of a database table is just to convert the table to its C# equivalent.

With all of that said, I’ll concede that yes, sometimes it’s possible to reconfigure things so that you don’t need to deal with missing values. However, you also have to consider the trade-off of whether or not the effort is worth it and if the use of a Maybe or null is actually a problem or if it’s just offending your sense of neatness.

What Have We Seen and Unseen?

Hopefully I’ve made the point that this is a nuanced question. As Steve mentions, Tony Hoare regards introducing pervasive null references as a billion dollar mistake and I’m not going to argue with him. But the fact remains that it’s a mistake we live with, unless you’re a Rust programmer (and don’t use unsafe code). We’ve also seen that an undesired null reference is actually just a small subset of a much larger problem of receiving undesirable inputs and that none of the coding strategies laid out in this or the original article will address this in general.

So really, we’re only left with two questions: what’s the best available technology for representing values that should not be null, despite the runtime supporting nulls and how should we represent values that may be missing, where we have no further information about why they’re missing? Ideally, the answers to both questions should satisfy the following requirements:

  • It should be idiomatic C# code.
  • A corollary of this is that it shouldn’t rely on a third-party library.
  • It should impose a low run-time overhead in high-performance scenarios.
  • It should have compile-time support.

The good news is, we have solution that satisfies all of these criteria: nullable reference types.

In Praise of Postmodernist Programming

So, one of those dear people on Twitter who have been trying and failing to be Twitter’s Main Character for years published a rant about post-modernist programming. Now, let’s leave aside the fact that they’ve literally created a fictional concept that sounds like it’s from a dril tweet to get angry about. Let’s actually engage with the fundamental narrative and point out how dumb it is in the context of programming.

What is Postmodernism Anyway?

Postmodernism is a movement that produced some really striking visual art and some utterly unreadable prose, but the fundamental concept of it was a rejection of the certainties of the modernist movement. Which is kind of hilarious because that was itself a rejection of the certainties of the enlightenment. Yes, I cribbed that from Wikipedia. This is very different from our dear failed main character’s definition of Postmodernism, which is kind of ironic since he was lecturing us about the absolute certainty of knowledge.

FMC’s contention is that there are certainties in programming, these are obvious and, implicitly, that these are important and can be extended by logical deduction into broad areas. Also, typically that they’re in a good place to determine these eternal truths and that if you disagree with them you’re wrong. This is a rhetorical framework shared between tradcaths, biblical fundamentalists and constitutionalist originalists that reaches back as far as Plato (and probably further) that, sadly, hasn’t actually fared very well since people started doing science. It turns out that it really seriously matters what your first principles are, incontrovertible ones are thin on the ground and everything, absolutely everything, needs to be checked empirically. Logical reasoning is only as good as your assumptions and it turns out that your assumptions are nearly always faulty when tested against the real world. There’s a tendency then to try to conform the world to your assumptions rather than the other way around. This is as much a problem in politics as it is in systems design.

Let’s Beat This Strawman Like A Piñata

So, in spirit of the discourse, I’m going to set up a strawman, knock it down and then act like I’ve proved something. Here’s my naively true, but actually easily falsified statement:

An O(n) algorithm is better than an O(n^2) algorithm

Me, obviously

So, the first question is “better how”? There’s an obvious subtlety to do with time/space complexity but that’s not even scratching the surface. Let’s say space doesn’t matter. Is the O(n) faster? Well, constant values can matter and it depends on your workload. Again, we’ve left the realms of pure logic and entered the realms of science and engineering. Then there’s the question of whether or not it matters at all, our dear originator’s big beef with “postmodernism”. Is the difference between the two twenty nanoseconds in a 5 second process? Then it honest to God doesn’t matter. (Well, probably, but if you’re arguing with me on this you’ve accepted my broader point, like an intellectually dishonest Catch-22.)

Let’s say it is slower to a significant extent. How complex is the faster algorithm? How easy is it to maintain? How easy is it to verify it doesn’t have any bugs? How much time will it take to develop and PR? Does it operate without locks while the faster algorithm requires us to lock the data structure? Do either of these algorithms actually solve the problem we have?

None of these questions are answerable without context, which I have pointedly failed to provide. But it’s my contention that the decisions any serious developer has to deal with every day look more like this: there’s no easy answers, things need to be thought through. It’s not that nothing matters, as that everything matters, and there are 100 concerns including, requirements capture, project velocity and team health that are an awful lot more important than whether you’re using a ring buffer correctly.

Postmodernist Programmers

So there you have it, a clickbait response to a clickbait tweetstorm shorn of all context because apparently truth is universal so you shouldn’t need it. If you actually want a considered and thoughtful response to the original screed, Dan North took down the whole mentality fourteen years ago. A guy who will happily tell you, if you ask, that he 100% believes there are eternal, immutable truths. Context is everything, nothing matters without it and there’s a whole raft of uncertainties we just have to navigate. So yeah, I’m proud to be a postmodernist programmer. Although I prefer the more vernacular term: a good one.

An Illustrated Reader

I’m writing this down before I forget because it’s really cool. Imagine you have the following code

> g a b = (show a) ++ (show b)
> h = (+5) 
> f x = g (h x) x

And you run f through pointfree, because you enjoy being made to look stupid. It’ll print up

> f' = g =<< h

You’ll stare at this going “I didn’t even say anything here was a Monad, but OK” try typing into your GHCi and… GHCi will tell you it doesn’t type check. Suitably chastened, you’ll go off to learn more Haskell elsewhere.

About a year later, you revist the problem and remember that all functions are examples of Reader monads and things start to make sense. You try

> import qualified Control.Monad.Reader

And, hey presto, it actually works. You can even check on the command line that it works. Let’s talk about how.

Reader, Illustrated

Start with a nice simple function x :: initial -> intermediate. As long as we’ve got Control.Monad.Reader imported, it’s automatically an m intermediate, where m means “a function taking an input”.

Since it’s a monadic value, we can reasonably ask what (y =<< x) is. Well, y has got to be a function that is of the form b -> m result. Since m in this case is “a function taking an input”, that makes y an intermediate -> input -> result. So the whole thing becomes input -> result.

This finally explains to me why so much of the lens library is written in terms of (MonadReader s m): it provides an extra free level of generality as long as you recall that (->) s (which is a function that takes an s) satisfies it. i.e. you can just read it as m b as s -> b.

Having fun

I don’t think I’ve ever published a FizzBuzz solution on the blog, so here’s one that heavily uses this reader monad trick.

> import Data.Maybe (Maybe(Just, Nothing), fromMaybe)
> import Data.Foldable (asum, for_)
> import qualified GHC.Base 
> -- also provides the MonadReader instance
> toMaybe :: Bool -> a -> Maybe a
> toMaybe False _ = Nothing
> toMaybe _ value = Just value
> fizzbuzz :: Integer -> String
> fizzbuzz = fromMaybe <$> show <*> asum . sequence rules
>     where fb m output n = toMaybe (n `mod` m == 0) output
>           rules = [fb 15 "FizzBuzz", fb 3 "Fizz", fb 5 "Buzz"]
> main :: IO ()
> main = for_ [1..100] $ putStrLn . fizzbuzz

Code golfers welcome.

A Simple Hylomorphism Example

I remarked last time that I’d wanted to write up a good example of using the recursion-schemes library to solve a computational problem in Advent of Code. However, as previously discussed, I found a more appropriate way of solving Day 7. However, it turns out that Day 24 has an elegant solution with a hylomorphism and judicious application of two ordered monoids.

Let’s get started.

> {-# LANGUAGE DeriveFunctor #-}

If you’re dealing with the recursion-schemes library, you’re going to be deriving Functors.

> module Day24blog where 
> import qualified Data.Set as S 
> import Data.Foldable (foldMap, toList)
> import Data.List.Split (splitOn)
> import Data.Monoid ((<>), Sum(Sum), mempty, mappend)
> -- import Data.Functor.Foldable (hylo)

I haven’t actually included Data.Functor.Foldable because in this case we need so little functionality it’s more clear if we just recreate the function in the text.

To restate the problem, we have a list of “components” that have two values, one for each end. The components can be reversed. The task is to find the “best” chain that can be built under a certain metric. Both parts a and b conform to this design.

The data input is sufficiently simple I didn’t bother reaching for my trusty MegaParsec.

> newtype Component = Component (Int,Int) deriving (Eq, Ord, Show)
> components :: IO (S.Set Component) -- luckily, all Components are distinct, so Set is OK.
> components = foldMap (S.singleton . c) <$> day24text
>     where c [x,y] = Component (read x, read y)
>           day24text = splitOn "/" <$$> lines <$> readFile "c:\\users\\me\\advent\\day24.txt"
>           (<$$>) = fmap . fmap

So, having established that we need to build chains, the first thing we need to do is establish whether a particular component can be added to a chain and if so, what the new value at the end of the chain would be.

> match :: Int -> Component -> Maybe (Int)
> match v (Component (x,y)) | x == v = Just y
> match v (Component (x,y)) | y == v = Just x
> match _ _ = Nothing

Introducing hylo

A hylomorphism is a refold, that is an expansion (anamorphism) followed by a contraction (catamorphism). The obvious examples of these are unfoldr and foldr, but recursion-schemes is more general and, in particular, can handle the branching structure we’re going to need to solve this problem.

> hylo :: Functor f => (f r -> r) -> (i -> f i) -> i -> r 
> hylo collapse expand = fp where fp = collapse . fmap fp . expand

One nice thing about hylo is that its type is relatively simple. Comprehending cata and ana, which are theoretically simpler functions, involves significantly more type dependencies.

You might be wondering how this self-recursive definition ever actually gets from an input to a result. It helps to remember that

  • [a] can be mapped to [b] pretty easily when the list is empty.
  • A lot of the work is, in practice, done by the Functor itself.

Exactly how it works requires someone with more experience than me.

The rest of this is an exercise is satifying hylo’s type requirements. First off, we need an input type.

> data Day24Precondition v = Day24Precondition {
>   valueToMatch :: Int,
>   componentsToUse :: S.Set Component,
>   componentMetric :: v
> } deriving (Show)

Strictly speaking the v is part of the output, but it works pretty well for our purposes. We can easily define the start state:

> start :: (Monoid v) => IO (Day24Precondition v)
> start = f <$> components
>     where f c = Day24Precondition {
>               valueToMatch = 0,
>               componentsToUse = c,
>               componentMetric = mempty
>           }

Collapsing the intermediate data structure

We then need something to capture the range of possibilities. This is going to be the f in our call to hylo.

> data Day24State v a = Day24State {
>   precondition :: Day24Precondition v,
>   alternatives :: [a]     
> } deriving (Functor, Show)

Having defined our f, we can define our collapse, which needs to be f result -> result.

> best :: (Monoid v, Ord v) => Day24State v v -> v
> best st = (componentMetric $ precondition st) <> bestAlternative
>     where bestAlternative = foldr max mempty $ alternatives st

So, we take the bestAlternative and add it to the value of the component. Note that this is not generic in the type of the Functor.

Creating the intermediate data structure

expand is a bit trickier than collapse. Given a precondition, get the list of subsequent preconditions (and compute the component values, since we stuck the component value on the input). First we expand upon the match function we defined earlier to work with Day24Precondition.

> matchToPrecondition :: (Component -> v) -> Day24Precondition x 
>        -> Component -> Maybe (Day24Precondition v)
> matchToPrecondition calculateMetric input c = f <$> m
>     where m = match (valueToMatch input) c
>           f x = Day24Precondition {
>               valueToMatch = x,
>               componentsToUse = S.delete c (componentsToUse input),
>               componentMetric = calculateMetric c
>           }

Then we use it to get a list of next states:

> choices :: (Component -> v) -> Day24Precondition v 
>         -> Day24State v (Day24Precondition v)
> choices calculateMetric input = Day24State {
>     precondition = input,
>     alternatives = foldMap toInput $ componentsToUse input 
> } where toInput = toList . matchToPrecondition calculateMetric input

Putting it all together

So, the first part of the Day 24 problem asked for the heaviest weight possible.

> weight :: Component -> Sum Int
> weight (Component (x,y)) = Sum $ x + y
> day24a = hylo best (choices weight) <$> start

The second part asked for the longest bridge, with weight as a secondary metric. For that, we just need a different ordered monoid.

> newtype LengthAndWeight = LengthAndWeight (Int, Int) 
>        deriving (Ord, Eq, Show)
> instance Monoid LengthAndWeight where
>     mappend (LengthAndWeight (x0,y0)) (LengthAndWeight (x1,y1)) = LengthAndWeight (x0+x1,y0+y1) 
>     mempty = LengthAndWeight (0,0)
> lengthAndWeight :: Component -> LengthAndWeight
> lengthAndWeight (Component (x,y)) = LengthAndWeight (1, x+y)
> day24b = hylo best (choices lengthAndWeight) <$> start

Hopefully this has shown how useful hylo can be. If you’re into Clojure, I gave a talk a few years ago about ana, cata and hylo implemented in pure Clojure for those of you who are interested. If people have examples of the more sophisticated recursion schemes or how to use the dist versions I’d be very happy to hear from you.

Marvellous Moeb

TL;DR; Haskell can process flat files as though they were hierarchal with the help of lazy evaluation and one ridiculously clever one-line function.

When working on Day 7 of the Advent of Code, I asked an innocuous question on r/haskell that led me down an extremely deep rabbit hole. The first part of the problem gives you a textual specification of a tree as an unordered series of nodes and asks you to compute the depth. It doesn’t take a genius to figure out that the second part will also involve computing some property of the graph.

I’d originally planned to solve the problem like this:

  • parse the lines
  • assemble the lines into a tree structure
  • use recursion-schemes to evaluate the answer

recursion-schemes is a powerful but rather impenetrable library (rather like lens) that provides generalisations of foldr and unfoldr that work for recursive structures other than List. Those familiar with the library will see that my final solution looks pretty similar to a solution using cata.

Unfortunately, my plan somewhat resembled the following plan:

  • steal underpants
  • ???
  • profit!

in that, I had nice elegant ways of dealing with 1 and 3, but 2 was going to be just plain annoying to write. So I asked a question as to whether there was a better way to do it. There was, courtesy of a function called loeb. loeb is a way of using Haskell’s pervasive laziness to circumvent a lot of busy work by the neat trick of constructing the final object as if it already existed. This makes it a generalisation of those Stupid Dwarf Tricks like the Fibonacci ZipList implementation we trot out when showing how powerful laziness is.

This gave me a fairly neat way of doing processing the tree structure by creating a map of node names to parsed assembled nodes, but something still bothered me: I had to write one function that created the map in the first place, and one function that looked up values in the map. This offended my sense of symmetry but I finally came up with what I believe to be a very nice way of solving it that uses the generalisation moeb, which is described in more detail in the above linked David Luposchainsky article.


I’ve written this up as literate Haskell, so next we have the inevitable headers:

{-# LANGUAGE ScopedTypeVariables #-}

Although not used in the final code, the ability to constrain types of identifiers in where clauses is vital for me when I try to figure out why my code isn’t typechecking.

Some of the following declarations are used in part two.

module Day7blog2 where 

import qualified Text.Megaparsec as MP
import qualified Text.Megaparsec.String as S
import qualified Text.Megaparsec.Char as C
import qualified Text.Megaparsec.Lexer as L

Megaparsec is a fork of the Parsec library with a very similar API that aims to be faster and produce better error messages.

import qualified Data.Map.Lazy as M
import qualified Control.Monad as CM
import qualified Control.Monad.Trans.Either as E
import qualified Control.Monad.State.Lazy as St

import Data.Function (on)
import Data.List (maximumBy)
import Data.Monoid (<$>)

Parsing the input file

We start by defining a type that corresponds to a line in the file.

data Node = Node {
    name :: String,
    weight :: Integer,
    children :: [String]
} deriving (Show)

This is the first surprise of the code: if I were using recursion-schemes, I’d have created Node a where children :: [a] and derived Functor. If I had actually wanted to construct the tree as I had originally planned I’d have still gone with that design, but as we’ll see, it’s possible to never actually construct the tree.

Next, we need a parser to map the lines of the file to our Node representation. We’ll recall that the format looks like this:

ktlj (57)
fwft (72) -> ktlj, cntj, xhth
nodeParser :: S.Parser Node
nodeParser = do
  n <- identifier
  _ <- C.char ' '
  w <- C.char '(' *> L.integer <* C.char ')'
  c <- MP.try parseChildren MP. pure []
  _ <- MP.try C.newline -- the final line of the file doesn't have a newline
  pure Node { name = n, weight = w, children = c }
  where comma = C.char ',' <* C.char ' '
        parseChildren = C.string " -> " *> MP.sepBy identifier comma
        identifier = MP.many MP.letterChar

I’m growing very fond of parser combinators very fast. I had trouble getting Megaparsec to work when I used its whitespace functions, but the file is very regular so I just threw them away.

day7text :: IO String
day7text = readFile "C:\\Users\\me\\advent\\day7.txt"

Yes, I’m using Windows. As long as you don’t try to use a C library it’s not that bad.

nodes :: IO (Either (MP.ParseError Char MP.Dec) [Node])
nodes = MP.parse (MP.many nodeParser) "" <$> day7text

This type is pretty ugly, but I don’t know what I could do to fix it.

Computing the depth of the tree

Now we’ve got a list of Nodes, we need to figure out how to process them as or into tree. We currently have no idea which Node relates to which Node and the data isn’t organised in a way to make this easy. Indeed, if we had constructed a tree of Nodes computing the depth would be pretty simple. The standard way I’d handle this in C# would involve multiple passes building up partial results until we’d finally take everything off the “todo” pile. It works, but it’s not an approach I much like.

Wouldn’t it be great if we could process the nodes without worrying about the order, and let Haskell’s laziness resolve everything as appropriate. It turns out we can, using moeb.

moeb :: (((result -> intermediate) -> intermediate) -> input -> result) -> input -> result
moeb f x = go where go = f ($ go) x

This type signature is, frankly, too complex for someone at my level to work out, but the article by David Luposchainsky mentions that ((r -> m) -> m) -> i -> r is satisfied by fmap, foldMap, traverse. (As an aside moeb foldr attempts to construct an infinite type, so maybe don’t use that.) I don’t know if there are any other interesting functions that satisfy it.

So, here’s what those applications give us:

moeb fmap :: Functor f => f (f b -> b) -> f b
moeb foldMap :: (Monoid r, Foldable t) => t (r -> r) -> r
moeb traverse :: (Applicative f, Traversable t) => t (f (t b) -> f b) -> f (t b)

As established in the article, moeb fmap is loeb. Using f = Map String would give you Map String (Map String b -> b) -> Map String b. moeb traverse gives you a monadic version of loeb, which doesn’t seem to buy us much over loeb.

Originally I tried implementing this code using loeb. It would have worked, but as mentioned earlier I still had some reservations. It was then that it occurred to me that, as well as a Functor and Applicative, Map String b is a Monoid.

So, a specialized version of moeb foldMap would be [(Map String b) -> (Map String b)] -> (Map String b) where the Strings are the node names and the bs are whatever values we want to compute. We need a list of (Map String b) -> (Map String b) and obviously they need to be generated from the list of Nodes or we haven’t got a result that depends in the inputs. (There’s probably some Yoneda-adjacent insight to be had here, but I’m not there yet.)

So that means what we actually need is a function like this: Node -> (Map String b) -> (Map String b). The first parameter is the Node, the second parameter the lazily evaluated final result. And the result will be the singleton map entry for the original node. This can use the “final result” map to look up the child nodes and compute the current node’s value.

Then moeb foldMap constructs these singleton maps and smushes them together to get the final result. i.e. final result -> intermediate results -> final result. As I’ve said before, none of this would work without a serious amount of lazy evaluation.

For such a long explanation, the resultant code is extremely short.

getDepth1 :: Node -> M.Map String (Maybe Integer) -> M.Map String (Maybe Integer)
getDepth1 n m = M.singleton (name n) (((1+) . foldr max 0) <$> z)
  where z = traverse CM.join $ (`M.lookup` m) <$> children n

We’re using Maybe Integer rather than Integer to capture the possibility that there’s a broken reference in the file. So this function:

  • takes the node names of the children,
  • looks up the depths in m (adding another Maybe to the type in the process)
  • takes [Maybe (Maybe Integer)] and turns it into Maybe [Integer] courtesy of traverse CM.join
  • finds the largest value (0 if it’s empty)
  • adds one
  • makes a singleton map for the node to that new value

That’s the hard work done, now we just follow the types to get this solution

day7a = do
    Right n <- nodes
    (pure . maximumBy (on compare snd) . M.assocs . moeb foldMap) $ getDepth1 <$> n

Print that out in GHCI and it gives us the depth and the name of the root node. This is good, but still a bit ugly and also not very general.

Taking it further

Let’s imagine that, instead, we wanted to sum the weights. At this point, we should come up with something more reusable. After all, all we really want to write is a catamorphism function that takes the current node, the results of its children and gives you the result for the current node. The type for this would be Node -> [a] -> a and we want a function that would take that and give us something that looked like getDepth1.

So cleaning up the code we’ve already written gives us this:

nodeReduce :: (Node -> [a] -> a) -> Node -> M.Map String (Maybe a) -> M.Map String (Maybe a)
nodeReduce f n m = M.singleton (name n) (f n <$> z)
  where z = traverse CM.join $ (`M.lookup` m) <$> children n

This is pretty similar to the code in getDepth1. Now we can write a general routine for processing Nodes. It’s also obvious how to generalize this even further.

process :: (Node -> [a] -> a) -> [Node] -> M.Map String (Maybe a)
process f l = moeb foldMap $ nodeReduce f <$> l

getDepth2 :: Node -> [Integer] -> Integer
getDepth2 _ = (1+) . foldr max 0

day7a2 = do
    Right n <- nodes
    (pure . maximumBy (on compare snd) . M.assocs . process getDepth2) n

So, now we have a cleaner way of getting the same result as last time, let’s now extend it to sum the weights.

data NodeWeight = NodeWeight {
  node :: Node,
  totalWeight :: Integer
} deriving (Show)

We could just compute the Integer and throw away the type, but when you’re debugging it’s rather useful to have all the relevant information around.

sumNodes :: Node -> [NodeWeight] -> NodeWeight
sumNodes n l = NodeWeight {
    node = n,
    totalWeight = weight n + sum (totalWeight <$> l) 

So, by dropping sumNodes in instead of getDepth2 we can solve a different problem.

day7sumNodes = (fmap . fmap) (process sumNodes)  nodes
lookup x = (fmap . fmap) (M.! x) day7sumNodes

Of course, no-one was actually asking us for this answer, and the second part is significantly harder. However, this has hopefully shown the power of the technique, that allows you to process flat files in an order imposed by their logical structure. In the second part we’ll show how this can be used to solve the much harder part b of Day 7: finding the incorrect value in the file.

Many thanks must go to Kris Jenkins for reviewing this post providing some really valuable feedback, and those that helped me out and showed me interesting things on r/haskell.

Why Your Code Has Lots of Spelling Mistakes

Spelling mistakes are cognitive noise. Everyone makes them, but you’d be hard pressed to find any obvious ones in the average word document for a simple reason: Word’s got a spell checker. So, for that matter, has Firefox. In general terms, if you’re writing English text, a spell checker’s got you covered.

So, what’s the state of play for spell checkers on programming language text? Parlous. Forget contextual errors and weird homophones, just basic “Is this word in the dictionary?” stuff doesn’t work in most editors.

I probably wouldn’t have thought that deeply about the problem if it wasn’t for a rather excellent plug-in for Visual Studio with a profoundly boring but search friendly name. This does everything I need and improves my day job immensely.

So, I thought, how about I write something to do the same thing for Visual Studio Code? Well, I’ll save you reading the rest of the article and say that you are basically doomed. And if you use Vim or Emacs and are feeling superior right now, let me tell you right now that you’re basically doomed for the same reason.

Check Yourself

Let’s start with what a spell checker for a programming language should do:

  • It should be able to spell check comments.
  • It should be able to spell check identifiers.
  • It should be able to distinguish between identifiers defined in the file from identifiers that are not, or you’re going to spend your life with errors you can’t correct.

This is pretty minimal. I’d also like to be able to include directives that specify language etcetera.

The comment requirement’s not too bad. There’s only a couple of comment formats out there and you could easily write some code to support them all. Identifiers are a whole different ball game, though. To recognize when something’s an identifier, you need at least a lexer for the language. Even that’s surmountable: there’s CSON files for most languages out there. The final requirement is the one that’s going to break you. Recognizing when and where an identifier is defined requires a parser.

Just as well we’ve got language servers to help us out isn’t it? No, they’re not going to help a bit. Language servers don’t really have any high level protocols. They just say “offer the following actions here”. What our putative spell checker plug-in would need is a protocol that said “this is the definition of a PascalCase identifier”. This is kind of doubly moot since Visual Studio Code only allows one language server at once, so any hope for modularity is gone before we started.

So, what can be done? Well, you could write a spell check library (most of the hard work’s already done for you) and then try to submit PRs to every last language server there is. This sounds like a prohibitively large amount of unpaid work.

Check Please

Unless your editor has spell checking built in and a way for your language plug-ins to interact with it and explain their identifier conventions et al, the chances are you’ll never have a decent spellchecker in your code editor. Meanwhile your code will continue to have spelling errors and your colleagues will curse you for being an illiterate. Of course, you’ll be cursing them at the same time whilst staring at the screen displaying the tool whose fault it really is.


Haskell: More about TypeClasses and QuickCheck

Last time, I was looking into establishing equality on various conditions on Wai.Request, but established that this wasn’t what I was looking for. We did, however, establish how to perform casts and use polymorphic lists in a fashion that’s quite OO. Now I’m planning to drive right off road and try a bit of type-level reasoning.

Let’s start by simplifying the problem we had last time. Let’s stoop worrying about complex record types and just deal with primitive types. We’ll restrict our attention to equality and comparison conditions on those types. Let’s start by setting up some machinery.

data Equality = Eql | NEql deriving (Show, Ord, Eq, Typeable)
equalityAsFunc :: (Eq a) => Equality -> a -> a -> Bool
equalityAsFunc Eql = (==) equalityAsFunc NEql = (/=)
data Comparison = LTh | LThE | GThE | GTh deriving (Show, Eq, Ord, Typeable)
comparisonAsFunc :: (Ord a) => Comparison -> a -> a -> Bool
comparisonAsFunc LTh = (<)
comparisonAsFunc LThE = (<=)
comparisonAsFunc GTh = (>)
comparisonAsFunc GThE = (>=)
class Invertable a where
  invert :: a -> a
instance Invertable Comparison where
  invert LTh = GThE
  invert GTh = LThE
  invert GThE = LTh
  invert LThE = GTh
instance Invertable Equality where
  invert Eql = NEql
  invert NEql = Eql
-- I could make all functors of a invertable invertable, but I'm not sure that would actually be a good idea.
instance (Invertable a) => Invertable (Maybe a) where
  invert = fmap invert
-- Util
infixl 3 <|!> (<|!>) :: Maybe a -> a -> a
(<|!>) = flip fromMaybe

Now, we’re going to have a Condition typeclass, and at the very least we’re going to have instances for “always true/false”, “test for equality/inequality” and “compare against value”. And here’s the important bit: we’re going to want to analyze the relationship between them, even if they’re not the same type.

data ConditionRelationship = Same | Compatible | Incompatible | AImpliesB | BImpliesA deriving (Show, Ord, Eq, Typeable)
instance Invertable ConditionRelationship where
  invert AImpliesB = ImpliesA
  invert BImpliesA = AImpliesB
  invert x = x

Young Rankenstein

Now, how would we achieve this in an OO world? Well, we’d implement something like this:

class Condition0 c where
  analyze = (Condition0 d) => c -> d -> Maybe ConditionRelatioship

Where we’d return Nothing if c didn’t know how to analyze its relationship with d. Using the cast mechanism we’ve already seen, you can definitely implement this. And indeed, I did. (I tried an approach involving a more symmetric approach and some type magic, but ultimately couldn’t get it to fly.)

Let’s revise the definition a little so that we can actually it to test values. But we’re going to have to introduce a second type, v, the value under test.

{-# LANGUAGE RankNTypes #-}
class Condition1 v a where
  analyzeSame :: a -> a -> ConditionRelationship
  analyzeDifferent :: (Condition1 v b) => a -> b -> Maybe ConditionRelationship
  test :: a -> v -> Bool
analyze :: (Condition1 v a, Condition1 v b) => a -> b -> ConditionRelationship
analyze x y = a <|> b <|> c <|!> Compatible
                      -- If we have no idea, say it's compatible
  where a = analyzeSame x <$> (cast y)
        b = analyzeDifferent x y
        c = invert $ analyzeDifferent y x

Now, there’s actually a serious problem with this code: it doesn’t even compile! The problem is with the vs in analyze. It can’t determine that they’re the same. This I actually find weird, given that I’ve specified that a and b share a v, but it’s solvable.

First, I want to talk a bit about what the rank 2 typeclass actually is. It specifies a set of functions that can be called with an a and a v, but doesn’t restrict the a or the v in any way. So, all it’s really giving you is a relationship between the two types. And analyze never uses v, so it can’t deduce anything about it.

Now, there’s an extension called FunctionalDependencies and another called TypeFamilies that’d resolve this, but actually all we need to do is take the test method back out.

class (Eq a, Show a, Typeable a, Invertable a) => Condition2 a where
  analyzeSame2 :: a -> a -> ConditionRelationship
  analyzeDifferent2 :: (Condition2 b) => a -> b -> Maybe ConditionRelationship
class (Condition2 a) => Condition3 v a where
  test :: a -> v -> Bool
analyze2 :: (Condition2 a, Condition2 b) => a -> b -> ConditionRelationship
analyze2 x y = a <|> b <|> c <|!> Compatible -- We have no idea, say it's compatible
    where a = analyzeSame2 x <$> (cast y)
          b = analyzeDifferent2 x y
          c = invert $ analyzeDifferent2 y x

That works, doesn’t use any more extensions, (although Lord knows I’ve been playing extension pokemon recently) and also leaves us with the possibility of using different vs with the same a, even if in this particular case I can’t see why we’d wish to. For that matter, we could remove the interdependency between the two.

class Condition4 v a where
  test :: a -> v -> Bool

I found it really interesting the process I went through here: we actually ended up with a better design and separated our concerns as a consequence of the type system complaining about the functions we actually implemented.

Into The Lens

Let’s rename our concepts:

class (Eq a, Show a, Typeable a, Invertable a) => Analyzable a where
  analyzeSame :: a -> a -> ConditionRelationship
  analyzeDifferent :: (Analyzable b) => a -> b -> Maybe ConditionRelationship
class Testable v a where
  test :: a -> v -> Bool

First some definitions:

data Value c v = Value {
  _value :: v,
  _condition :: c
} deriving (Typeable, Eq, Show)
makeLenses ''Value
instance (Invertable c) => Invertable (Value c v) where
  invert = over condition invert

I’m using the lens package here, although to be honest I’m really only using it to start learning it. The actual practical benefits of it in the code I’ve written are very small, but I’m hoping to slowly pick up more aspects. In fact, of the code I’ve written so far this is the only bit that actually shows an improvement.

Breaking it down, we’re saying that if a condition is invertable, a Value using that condition is invertable by inverting the condition. Even though this is pretty elegant, but it’s going to take me a fair while to get my head around lens in general (There’s been loose talk of a lens NICTA-style course, that would be awesome.).

Scopes Monkey

So, we can declare an equality value to be a condition:

instance (Typeable a, Show a, Eq a) => Condition a (Value Equality a) where

I’m deliberately skipping the instance code because it’s pretty boring and predictable. The interesting case is when we’re implementing comparison:

analyzeEqualOther :: (Invertable b, Testable v b) => b -> Equal v -> ConditionRelationship

(I’ll skip the implementation.) Now for an instance:

instance (Typeable a, Show a, Ord a) => Analyzable (Value Comparison a) where
  analyzeSame = analyzeCompSame -- elided
  analyzeDifferent x y = analyzeEqualOther x <$> y2
    where y2 = cast y

Makes sense. Doesn’t compile. The reason’s a bit weird: it can’t figure out exactly what to cast y to. So let’s try this:

    where y2 = (cast y :: Maybe (Value Equality a))

Still doesn’t work. Here, the error message isn’t particularly helpful (unlike quite a few that just point you directly to the extension that you might need). The problem is actually that the a in the y2 expression isn’t the same as the a in the instance declaration. I don’t really understand why that decision was made (the explanation probably features the word “parametricity”), but you can reverse it by adding in another extension:

{-# LANGUAGE ScopedTypeVariables #-}

QuickCheck Yourself

There’s a plethora of things we could test, but let’s start with this one: What actually is the relationship between the Analyzeable version of condition and the Testable version of condition? Well, the answer is approximately that given two types that are both, we should be able to pick a set of vs such that we can deduce the behaviour of one from the other.

It would be lovely if we could achieve this through the type system, but I think that would be a serious reach, and even if it was possible it’s doubtful it would be readable. So instead let’s try using QuickCheck, the original property testing tool.

Aside: conversely, there should be no value of v where the behaviour of the two contradict one another. However, this latter condition is kind of hard to demonstrate using any example-based system. For that, you really do want Idris.

We need to set up some infrastructure to make cabal run tests.

Test-suite test
  Type:              exitcode-stdio-1.0
  Hs-source-dirs:    test
  Main-is:           Main.hs
  Build-depends:     base >=4.7 && <4.8,

This introduces a new target called test. I’ve not used quickcheck before so this is quite interesting. tasty appears to be the standard test running infrastructure. Note that since the test code is actually a separate executable, you need to put your own code as a dependency.

Stuck In The Middle With You

So, let’s pick five distinct values, a, b, c, d and e. We’ll put conditions at b and d and then test all five values in pairs. We can then read out from the set of pairs what the correct relationships between the two conditions is.

import Test.QuickCheck

data TestValues x = TestValues {
  a :: x,
  b :: x,
  c :: x,
  d :: x,
  e :: x
} deriving (Show, Eq, Ord)

instance (Arbitrary a, Ord a, Num a) => Arbitrary (TestValues a) where
  arbitrary = do
    a <- getPositive <$> arbitrary
    b <- (a +) <$> getPositive <$> arbitrary
    c <- (b +) <$> getPositive <$> arbitrary
    d <- (c +) <$> getPositive <$> arbitrary
    e <- (d +) <$> getPositive <$> arbitrary
    return (TestValues a b c d e)

This is all rather fun: arbitrary returns a value in the Gen monad. getPositive unwraps a Positive and return type polymorphism kicks in.

Normally, though, how to create an Arbitrary instance is obvious given its components, setting them up is going to get boring real fast, which is where the derive package kicks in

{-# LANGUAGE TemplateHaskell #-}
import Data.DeriveTH

derive makeArbitrary ''Equality
derive makeArbitrary ''Comparison
derive makeArbitrary ''Value

This now enables us to write the code we wanted:

propDeduce :: (Analyzable (Value c1 v), R.Testable v (Value c1 v), Analyzable (Value c2 v), R.Testable v (Value c2 v))
  => c1 -> c2 -> TestValues v -> Bool
propDeduce c1 c2 testValues = expected == drawConclusion x y testValues where
  x = Value c1 (b testValues)
  y = Value c2 (d testValues)
  expected = analyze x y

drawResults :: (R.Testable v (Value c1 v), R.Testable v (Value c2 v))
  => (Value c1 v) -> (Value c2 v) -> TestValues v -> [(Bool,Bool)]
drawResults x y testValues = result where
  result = f <$> ([a, b, c, d, e] <*> (pure testValues))
  f v = (test x v, test y v)

drawConclusion :: (R.Testable v (Value c1 v), R.Testable v (Value c2 v))
  => (Value c1 v) -> (Value c2 v) -> TestValues v -> ConditionRelationship
drawConclusion x y testValues = ac (length conclusions) conclusions where
  conclusions = nub $ drawResults x y testValues
  ac 4 _ = Compatible
  ac 3 _ = ac3 missingConclusion
  ac _ x | null $ x \ [(True,True),(False,False)] = Same
  ac _ _ = Incompatible
  missingConclusion = head $ [(True, True),(True, False),(False, True),(False,False)] \ conclusions
  ac3 (False, True) = BImpliesA
  ac3 (True, False) = AImpliesB
  ac3 (True, True) = Incompatible
  ac3 _ = Compatible

You can now write quickcheck properties like

prop_deduceCompEq :: Comparison -> Equality -> TestValues Int -> Bool
prop_deduceCompEq = propDeduce

(There may be a better way of instantiating propDeduce with different types, but this definitely works.)

In practice, what now happens is you spend a large amount of time actually fixing your code and your tests. What you’re seeing above is the output of that process. I learned a few things in the process.

  • Although QuickCheck is good at telling you there’s a problem, it’s got no facilities at all for telling you why.
  • Having relatively complex types makes it quite hard to reproduce a test in the repl. Conceivably the tooling for this could be improved.
  • You need to split your code up into chunks that are testable in the repl. This is a lesson Clojure taught me as well, but having access to an excellent debugger in other languages keeps unteaching it.

This is getting really long: I’ve skipped over the entire tasty code and the entire implementation.


So the Condition design looks more appropriate to the aim of actually allowing us to optimize our tests, and Haskell’s led us to a typeclass design better than the original item. There are, however, certain problems. For instance, the design I’ve outlined here is incapable of spotting that “> 2” is the same as “>= 3” in the Integer domain. Pretty much the only good solution to this is to require stronger conditions than just Eq and Ord for condition values, which allow you to perform these analyses. I’m not very inclined to do that, but this problem doesn’t ruin my intended use. However, it highlights again just how challenging it is to write something truly polymorphic and correct.

It’s pretty easy to see how you can extend this into projections as well. However, in practice it gets pretty tricky, because you need to do an order 2 cast. Thankfully, I got a good answer on StackOverflow of exactly how to achieve that. Separating out the concept of the condition from the projection also seems like a strong idea. Ultimately, though, I don’t really like the way this is going. Casts work, and Maybe makes them safe, but the design feels like I’m circumventing the type system rather than using it.

Principled Casts in Haskell

TL;DR I continue trying to implement a routing library, but instead end up learning about Typeable, writing about orphan instances, reading and (so far) failing to understand type-magic and sending my first Haskell PR.

I remember when I was starting Clojure, one of the big catchphrases was that everything was opt in. A type system, inheritance, multiple dispatch, &c. On the other hand, there were actually plenty of things that weren’t opt-in: Java itself, polymorphism, reflection and so on.

Haskell is another opt-in language. The basic type system and language is a requisite, but there’s still a phenomenal number of things to opt into. Equality is opt in, Hashable is opt in, as we saw in the previous article, polymorphism through existential types is opt-in. Next, we’re going to see “opt-in” type casts, and hopefully you’ll see how they’re better than what you can achieve in Java or C#.

{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
import qualified Network.Wai as Wai
import qualified Network.HTTP.Types as H

So, the question I asked last time was, how can I tell if two RequestConditionBoxs are equal? To do that, we’re going to want to make RequestConditions themselves implement equality.

(As an aside: the whole of the functionality of the last post might have been better implemented using good old functions or possibly the reader monad. However, I always wanted the conditions to be instances of Eq and Show. That’s not going to be possible with that approach.)

class (Show rc, Eq rc) => RequestCondition rc where
  isMatch :: Wai.Request -> rc -> Bool
data RequestConditionBox where
  RC :: (RequestCondition rc) => rc -> RequestConditionBox
  deriving (Show)

Oops, that isn’t going to work: you can’t derive Show on a GADT. So delete it. We’ll need to implement Eq and Show for RequestConditionBox. (I’m going to skip Show.)

instance Eq RequestConditionBox where
  (==) (RC a) (RC b) = a == b

Small problem: a and b are different types. And Eq only allows you to test that two members of the same type are equal. We need some way of checking that the two types are equal. Now, you can test for type equality in a type precondition but I can’t see how I could make that work. We need something more like

testEqual :: (Eq a, Eq b) => a -> b -> Bool

Only right now we have no idea how to implement it.

He’s My Typeable

George Pollard pointed me to an experimental class called Typeable. As I alluded to earlier, it’s opt-in, although I think the opt-in nature is more to do with the fact that it’s not standardized yet than that there are types that can’t logically have a typeclass instance.

Typeable looks like a pretty unpromising typeclass:

typeRep# :: Proxy# a -> TypeRep

Actually, it’s more than just unpromising, it looks positively hostile. What are those hashes? Well, it turns out that hash is a valid character in an identifier if you enable the MagicHash extension. As a convention, GHC uses it to represent unboxed types. Unboxed means exactly the same thing as it does in C# and Java: something that doesn’t have a garbage collected pointer around it. This is a very deep rabbit-hole that I’m just going to carefully step around right now.

Actually, I’m going to skip pretty much everything except to notice that Data.Typeable exports a rather useful function called cast.

cast :: (Typeable a, Typeable b) => a -> Maybe b

Yep, that’s exactly what as does in C#. I’ll skip over the implementation, because it’s slightly scary and I’d need to get into unsafeCoerce. One thing I can’t tell is if this code is actually run at runtime or whether it’s possible for the compiler to optimize it out. After all, the types of a and b are known at compile time.

With that, we can actually test if two values of different types are equal:

testEqual :: (Typeable a, Eq a, Typeable b, Eq b) => a -> b -> Bool
testEqual x y = fromMaybe False $ (== x) <$> cast y

Reading from right to left:

  • cast y
  • map (<$>) the maybe with (== x)
  • this gives us Nothing if x and y are different types, and Just (x==y) if they’re the same.
  • finally, we use fromMaybe to strip off the Just and replace Nothing with False

Orphan Black

To use testEqual, we need to make our RequestConditions typeable

class (Typeable rc, Show rc, Eq rc) => RequestCondition rc where
  isMatch :: W.Request -> rc -> Bool

How do we implement it? Well, we don’t. Typeable is special. Not only is it derivable, the compiler requires you use the deriving version. And that needs an extension:

-- Put this up at the top
{-# LANGUAGE DeriveDataTypeable #-}
newtype And rc = And [rc] deriving Typeable

Unfortunately, H.HttpVersion doesn’t implement Typeable. Luckily we can implement it ourselves. But, you guessed it, we need another extension:

-- Put this up at the top
{-# LANGUAGE StandaloneDeriving #-}
deriving instance Typeable H.HttpVersion

We’re probably alright here, but what we’ve done is, in general, ridiculously dangerous. We’ve implemented an instance in a library that is neither the library that declares the typeclass, nor the library that declares the type. This is known as an orphan instance and will have seasoned Haskellers gathering with torches and pitchforks around your codebase. The reason for this is that, while typeclasses provide the power of ruby’s mixins, orphan instances provide the problems. (They call it “incoherence”, and they mean it.)

While we’re on the subject, you’ll probably have already noticed that when you add projects into your cabal file, you pull in the world, Maven style. This is pretty horrific, but the reason for this is orphan instances. For instance, the functionality of the semigroups package looks pretty small: it just exposes a couple of typeclasses. But when you take a look at what is an instance just of Semigroup you’ll see a whole list of types that the semigroups package needs just to compile. Semigroups itself has defines to try to ameliorate this situation but the truth is that it’s just too much work (at least given cabal in its current design) to enforce small dependency lists and coherence.

Long story short, it’d probably be best to just expose Typeable from the library, so I’ve sent a pull request. (As everyone knows, open source software collaboration is a variable experience. But even at my beginner level, it is possible to make small contributions.)

The Equalizer

Remember last time I mentioned that we could destructure existential types? Now we can actually use this.

equalRC1 :: RequestConditionBox -> RequestConditionBox -> Bool
equalRC1 (RC a) (RC b) = testEqual a b

That looks pretty promising. But we haven’t handled the case where a or b are themselves a RequestConditionBox

equalRC2 :: RequestConditionBox -> RequestConditionBox -> Bool
equalRC2 a1@(RC a) b1@(RC b) = eq3 (cast a) (cast b)
  where eq3 (Just x) _ = equalRC2 x b1
        eq3 _ (Just y) = equalRC2 a1 y
        eq3 _ _ = testEqual a b

Well, that’s kind of fun, but an alternative formulation is arguably better:

infixl 3 <|!> -- Left associative, use same precedence as <|>
(<|!>) :: Maybe a -> a -> a
(<|!>) = flip fromMaybe
equalRC4 :: (Typeable a, Eq a) => a -> RequestConditionBox -> Bool
equalRC4 x (RC y) = a <|> b <|!> c
  where a = equalRC3 x <$> (cast y)
        b = equalRC3 y <$> (cast x)
        c = testEqual x y

<|> is a fairly general function, but in general it means “take the first valid parameter”. Its type is

(<|>) :: Alternative f => f a -> f a -> f a

Here, just remember that Maybe is an Alternative. I’ve also introduced my own infix operator <|!> to get me out of Maybe land. (Hey, I don’t even need an extension for this!)

We now have a vastly better implementation of Eq:

instance Eq RequestConditionBox where
  (==) == equalRC4

(Aside: there’s a very interesting looking function in Data.Typeable called gcast that I thought could be useful here, but I couldn’t figure it out, so everything here stays at the cast level.)

Designed By An Idiot In London

Let’s load what we’re got into a REPL.

> :m + Main
> :m + Data.List
> :m + Network.HTTP.Types
> let td = [RC methodGet, RC methodGet, RC (RC methodGet), RC http10, RC http11]
> nub td

gives us

[RC "GET",RC HTTP/1.0,RC HTTP/1.1]

Well, that’s demonstrated that Eq works. But it also demonstrates something else: Eq isn’t actually what we wanted in the first place. Really we want to be unifying to [RC "GET",RC HTTP/1.1]. To do that, we’re going to have to rip up everything we’ve done so far and start again.

FOOTNOTE: Elise Huard pointed me to the AdvancedOverlap page on the wiki, which details techniques for branching your code by typeclass rather than type. In practice, I decided to just make everything an instance of Eq, which isn’t so much of a problem given the problem domain I’m working within.

A Route To Learning The Haskell Type System

TL;DR I start trying to write a library and get sidetracked into learning about Haskell’s type system.

So last time, I talked about Wai and how you could use it directly. However, if you’re going to do that, you’ll need a routing library. So, let’s talk about how we could build one up. One of the first things you’d need to do is to provide simple boolean conditions on the request object.

It turns out that this raises enough questions for someone at my level to fill more than one blog post.

{-# LANGUAGE TypeSynonymInstances #-}
{-# LANGUAGE FlexibleInstances #-}
import qualified Network.Wai as Wai
import qualified Network.HTTP.Types as H

So, how should we define conditions? Well, the Clojure model of keyword and string isn’t going to work here, because the Wai.Request object is heavily strongly typed. So how about instead we just use the expected values and deduce the key from the type?

So, we’re going to want to implement the same method for several different types. There’s several different ways of doing that: * Create a union/enum class. This is a good approach, but not extensible. * Create a typeclass, which is extensible. * Create a type family, which is also extensible, but I don’t really understand.

You Can’t Buy Class

With that in mind, let’s create our first typeclass!

class RequestCondition rc where
  isMatch :: Wai.Request -> rc -> Bool

So, in English this says “If the type rc is a RequestCondition then there is a method isMatch which takes a Wai.Request and an rc and returns a Bool.” This is pretty interesting from an OO standpoint. The OO representation would look like rc.isMatch(request). A Clojure protocol would change this to (isMatch rc request). In practice, it doesn’t matter: what’s happening is that there’s dynamic dispatch going on on the first parameter.

In the Haskell case, there’s no dynamic dispatch in sight and the first parameter isn’t special. isMatch on HTTPVersion and isMatch on Method are different functions.

We can now implement the RequestCondition for some obvious data types.

instance RequestCondition H.HttpVersion where
  isMatch = (>=) . W.httpVersion

So, here we’ve said “calling isMatch with a HttpVersion as a parameter calls (>=) . W.httpVersion i.e. checks the request is using the version specified. We’d probably need a more sophisticated way of dealing with this if we were writing a real system.

instance RequestCondition H.Method where
  isMatch = (==) . W.requestMethod

This is much the same, with one wrinkle: H.Method isn’t actually a type. It’s a type synonym. In C++ you’d introduce one with typedef, in C# with using. Haskell, because it likes to confuse you, introduces something that is not a type with the keyword type. If you look up method on Hackage you see:

type Method = ByteString

You might wonder why this matters. The answer is that the Haskell standard doesn’t allow you to declare instances of synonyms. You can understand why when you realize that you might have multiple synonyms for ByteString and shoot yourself in the foot. However, for now I’m going to assume we know what we’re doing and just switch on TypeSynonyms in the header.

Let’s do one more, because three’s a charm.

instance RequestCondition H.Header where
  isMatch = flip elem . W.requestHeaders

We’d need (a lot) more functionality regarding headers, but let’s not worry about that now. However, again this will fail to compile. This time H.Header is a type synonym, but a type synonym for a very specific tuple.

type Header = (CIByteString, ByteString)

Problem is, Haskell doesn’t like you declaring instances of specific tuples either. This time, you need FlexibleInstances to make the compiler error go away. To the best of my knowledge, FlexibleInstances is much less of a hefalump trap than TypeSynonyms could be.

For fun, let’s throw in a newtype

newtype IsSecure = IsSecure Bool
isSecure :: IsSecure
isSecure = IsSecure True
instance RequestCondition IsSecure where
  isMatch r (IsSecure isSecure) = W.isSecure r == isSecure

Under Construction

How about when we’ve got multiple conditions to apply? Well, if we were writing Java, we’d be calling for a composite pattern right now. Let’s declare some types for these.

newtype And rc = MkAnd [rc]
newtype Or rc = MkOr [rc]

I described newtypes back in Fox Goose Corn Haskell. Note that there’s no reference to RequestCondition in the declaration. By default, type variables in declarations are completely unbound.

Before we go any futher, let’s fire up a REPL (if you’re in a Haskell project right now you can type cabal repl) and take a look at what that does:

data And rc = MkAnd [rc]
:t MkAnd
MkAnd :: [rc] -> And rc

Yes, MkAnd is just a function. (Not exactly, it can also be used in destructuring, but there isn’t a type for that.) Let’s try expressing it a different way while we’re here:

:set -XGADTs
data And2 rc where MkAnd2 :: [rc] -> And2 rc

(You’ll need to hit return twice) Now we’re saying “And2 has one constructor, MkAnd2, which takes a list of m. The GADTs extension does way more than this, some of which I’ll cover later on, but even then I’m only really scratching the surface of what this does. For now I’ll just observe how the GADTs extension provides a syntax that is actually more regular than the standard syntax.

Incidentally, I could have called MkAnd just And, but I’ve avoided doing so for clarity.

Composing Ourselves

With the data types, we can easily write quick functions that implement the RequestCondition typeclass.

instance (RequestCondition rc) => RequestCondition (And rc) where
  isMatch r (MkAnd l) = all (isMatch r) l
instance (RequestCondition rc) => RequestCondition (Or rc) where
  isMatch r (MkOr l) = any (isMatch r) l

The most interesting thing here is that we haven’t said that And is an instance of RequestCondition, we’re say that it is if its type parameter is an instance of RequestCondition. Since data types normally don’t have type restrictions themselves, this is the standard mode of operation in Haskell.

So, now I can write

Or [H.methodGet, H.methodPost]

and it’ll behave. So we’re finished. Right? Not even close.

What if we wanted to write

And [H.methodGet, H.http10]

It’s going to throw a type error at you because HTTP methods aren’t HTTP versions. If you take a look at the declaration, it says “list of rcs that are instances of RequestCondition” not “list of arbitrary types that are instances of RequestCondition“. If you’re used to OO, (and I have some bad news for you if you’re a Clojure programmer, that means you) this makes no sense at all. If you’re a C++ programmer, this is going to make a lot more sense. You see, when you do that in Java you’re telling Java to call through a vtable to the correct method. Haskell doesn’t have pervasive vtables in the same way. If you want one, you’re going to have to ask nicely.

Pretty Please and Other Existential Questions

What we want, then, is a function that boxes up a RequestCondition and returns a type that isn’t parameterized by the original type of the RequestCondition. What would that function look like?

boxItUp :: (RequestCondition rc) => rc -> RequestConditionBox

Hang on, that looks like the type of a constructor! Except for one really annoying little detail: as I said before, you can’t put type restrictions in data declarations.

Except you can, if you enable GADTs.

data RequestConditionBox where
  RC :: (RequestCondition rc) => rc -> RequestConditionBox

RequestConditionBox is what’s known as an “existential type”. As I understand it that should be interpreted as “RequestConditionBox declares that it boxes a RequestCondition, but declares nothing else”. So its quite like declaring a variable to be an interface.

Since I wrote this, I’ve learned that existential types are indeed very like interfaces in C#/Java: they are bags of vtables for the relevant type classes. They don’t expose their parameterization externally, but destructuring them still gets the original type out. This is bonkers.

It just remains to actually implement the typeclass:

instance RequestCondition RequestConditionBox where
  isMatch r (RC m) = isMatch r m

And now we can finally write

And [RC H.methodPost, RC isSecure]

And the compiler will finally accept it. Not quite as pretty as in an OO language where polymorphism is baked into everything, but keeping the character count low isn’t everything. We’ve traded implicit polymorphism for explicit polymorphism.

So we’re done, right? Well, we could be, but I want to go further.

The Power of Equality

If you take a look, what we’ve built looks very much like a toy interpreter (because it is one). What if we wanted a toy compiler instead? In particular, imagine that we really were building a routing library and we had thousands of routes. We might want to only check any given condition once by grouping, for example, all of the GET routes togther.

Now, you could leave that to the user of the library, but let’s pose the question: given two RequestConditions, both of which may be composite, how do you determine what conditions are common between the two?

One route is to backtrack, and look at HLists. I think that’s probably an extremely strong approach, but I really haven’t got my head around the type equality proofs-as-types stuff. Another approach is add some stuff to RequestCondition to track the types in some way. It turns out there’s a way to get the compiler to do most of the work here, so I’ll talk about that next time.

FOOTNOTE: On the Reddit discussion it was pointed out that RequestConditionBox is an example of the existential type anti-pattern. To summarize: if all you’ve got is a bunch of methods, why not just have a record with those methods as properties? If all you’ve got is one method, why not just use a function.

This is a completely valid criticism of the code in this post as a practical approach. However, we wouldn’t have learned about existential types in the first place, and we couldn’t make functions implement Eq and Show. Implementing Eq is the subject of the next post.

The commenter also added an elegant implementation of the functionality given above in terms of pure functions.

EDIT: Lennart Augustsson clarified that existential types do indeed construct vtables. So “boxing” something in an existential type is very like casting a struct to an interface it implements in C#. I should also clarify that the word bonkers used in the above text was meant as a good thing. 🙂

Hello World Web Application in Haskell

So, I’m learning Haskell. I’ve done the Yorgey course and want to write a web app. How do I start? Should I learn Snap or Yesod? Well, the short answer is no.

Here I’m going to outline the creation of the simplest possible Haskell “Hello World” web application.

Wai Wai Pom Pom Pom

Snap and Yesod are both “big” web frameworks. Of the two, Snap aims to be the smaller. Both have their own web server, templating system and so on. Both are sufficiently complex to need a program to set up a starter project. Both have fairly sophisticated monad stacks to understand. They’re also both phenomenal high-performance pieces of engineering.

What this means for a beginner is that you’re going to spend as much time trying to get to grips with the framework as you are learning how to use Haskell. If like me, you’re coming from Clojure, they both feel a bit more like Rails than Compojure.

So, are there simpler to understand models out there? Well, the equivalent of Compojure/Sinatra is Scotty. But I found the next level down again more interesting: Wai.

Wai corresponds most closely to Ring or Rack. It was intended to be a common API that Haskell web servers could expose. In practice, it’s only Warp that really supports it. However, Warp is a damn fine web server so that shouldn’t hold us back too much. Nearly every Ring app runs Jetty and hardly anyone really worries that the “standard” isn’t as portable in practice as it is in theory.

Setting up Hello World

To start, create a new directory. For our purposes we’ll call it “example”. Then we set up a completely blank project.

mkdir example
cd example
cabal sandbox init
cabal init

The “sandbox” and “wget” lines I’ll gloss over, but they basically constitute the best way I know to avoid what’s known as “cabal hell”. And believe me, you don’t want cabal hell.

When you run the init command, you’ll be asked a whole bunch of questions. The defaults are fine, just make sure you specify you’re creating an executable. It’ll create a file “example.cabal”. You then need to go in and make it look like this:

-- Initial semele.cabal generated by cabal init.  For further
-- documentation, see

name:                example
-- synopsis:
-- description:
license:             AGPL-3
license-file:        LICENSE
author:              Rainbow Dash
-- copyright:
category:            Web
build-type:          Simple
-- extra-source-files:
cabal-version:       >=1.10

executable semele
  hs-source-dirs:      src
  main-is:             Main.hs
  -- other-modules:
  -- other-extensions:
  build-depends:       base >=4.7 && <4.8,
  default-language:    Haskell2010

There’s two import edits here. The first is that we specify hs-source-dirs. The default is that the Haskell files are dumped in the project’s root directory, which is a lousy default. The other is that we set up our dependencies: wai, warp and http-types. Wai and http-types from our API, Warp our implementation. Note that dependencies are case-sensitive.

You may also be wondering why I haven’t specified any version constraints. That’s because we’ve set them up in the cabal.config instead. Welcome to the new world of LTS Haskell.

Writing Hello World

mkdir src
cd src

Now create Main.hs.

{-# LANGUAGE OverloadedStrings #-}

We need this because Wai uses ByteStrings rather than Strings, and overloaded strings makes using them lower friction.

import qualified Network.Wai as W
import qualified Network.HTTP.Types.Status as HS
import qualified Network.Wai.Handler.Warp as Warp

I’m qualifying everything for clarity. In practice, I do this a fair bit even when I’m not writing a blog post.

main :: IO ()
main = main = do
  putStrLn "Starting Web Server..."
  Warp.runSettings Warp.defaultSettings app

So, all we’re saying here is “Run the app with the default settings for a Warp server.” The default port is 3000.

Finally, we need the app itself:

app :: W.Application

Let’s take a huge detour and examine what that actually means.

Understanding W.Application

Now, the type of app is W.Application, but that tells us nothing. So let’s look it up (LTS has a hoogle, search for Wai.Application). You’ll find

type Application = Request -> (Response -> IO ResponseReceived) -> IO ResponseReceived

So, it’s a alias for a type of function. However, the type’s way more complex that we were expecting. What were we expecting? Well, in Ring the type’s more like

type ApplicationRing = Request -> Response

Take a request, return a response. However, in order to allow for correct resource management, it uses a continuation passing style instead. (I’m hoping to expand on that in another post.) So instead, you need a callback. As you see, we called that respond.

What’s respond‘s type? Well, it’s got to take a response. At this point I hit the limits of my understanding. I’d have made the function return (), but instead it returns ResponseReceived which appears to be a placeholder type. Finally, obviously respond is going to have to write to a socket, so it’s going to have to incorporate the IO monad. Now, in most of the more complex APIs, what you find here is a monad transformer stack with IO somewhere in the mix. In Wai, you just get a naked IO ResponseReceived and can build your own later.

To summarize, the type of respond is Response -> IO ResponseReceived and that means “when you call it with a response it will do some IO and return that it’s been processed`.

Finally, Application expects IO ResponseReceived to be returned from the function. I believe this to be practically motivated: nearly every handler is going to want to call respond as the last thing it does, and this means that the types work when you do that.

You Had Me At Hello

So, now we’ve understood the type, let’s write the function

app request respond = respond $ W.responseLBS HS.status200 [] "Hello World"

To unpack this: when you receive a request, respond using status 200 (success), no headers ([]) and byte string “Hello World”.

So, that’s about the simplest thing we can possibly do without writing our own web server.

Let’s Be Frank

So, how does this compare to Sinatra’s famously good home page? Well, for a start we have three files instead of one. However, two of those files are devoted to ensuring that our dependencies don’t mess us around, if you want to do the same in Ruby, you’ll be setting up bundler, using a gemfile.lock in addition to your normal gemfile, so three files again.

Haskell actually comes out slightly ahead here if you’re willing to forgo some flexibility, in that the cabal.config is repeatable and upgrading is a matter of trying a new cabal.config/ reverting if it doesn’t work.

In comparison, bundler generates a lock file dependent on your current gemfile. If you need to add another library later, it’s up to you to figure out which versions are compatible with your code.

On the other hand, if you need more flexibility, you’re going to encounter cabal hell pretty quickly. Good luck.

We’ve got three dependencies instead of one. That’s a pity. But it comes from the two sources:

  • We’ve got to import types declaring interfaces as well as just implementation code.
  • We don’t have the web server appearing by magic.

On the other hand, Sinatra’s actually provided a routing library, and we don’t have one yet. But we could have used Scotty instead.

Keep On Running

So, let’s see it in action. Get back to the root project directory and type

cabal install && dist/*/build/example/example

and navigate to http://localhost:3000/. Hey presto, you’ve served a web page. Looking at the headers, all that it’s specified is a Date, the Server and Transfer-Encoding, so we’ll definitely have a bit more work to do to for a full experience.

FOOTNOTE: I’m quite pleased with the response this article had on reddit. This discussion is quite interesting and I recommend reading it.

FOOTNOTE: Quite a few people have remarked that the comparison section isn’t really fair on Haskell in that I’ve implemented something at the Rack/Wai level, rather than the Sinatra/Scotty level, which is true. However, I wanted to use Wai rather than Scotty to avoid going into monads and monad transformers and ultimately, I think the Haskell one is still quite concise and beautiful in a very precise manner.

EDIT:A number of people have pointed out that modern ruby is indeed capable of precise version locking. I’ve updated and expanded the comparison to reflect that.

EDIT:Originally I believed that Wai’s continuation passing style was due to asynchronous concerns. Instead, it’s driven by resource management concerns. I’ve corrected the line.