Infinite Negative Utility

I want to say a few words on how I write Haskell as of 2017.

Before I go on, I want to make very clear: this is neither a style recommendation nor a judgment on any other style. This is how I write Haskell, and many of the principles below I've come to either because of past experiences with writing or maintaining Haskell, because of how I originally learned or was taught Haskell, or because of experiences I've had with other languages in general.

However, even though I like to adhere to these principles, I don't want to advocate that any of them are universal! You probably write Haskell differently, and that's not just okay but actively good: one of the great things about Haskell as a language is that it's a powerful raw material that permits all kinds of different powerful and expressive idioms, and someone else's Haskell style will definitely take advantage of Haskell in ways mine doesn't.

The Boring Basics

This stuff isn't actually interesting, and I make an effort to stick to the code style of the codebase I'm writing in, but here's the textual details of how I write Haskell in the absence of any other factors:

I prefer two spaces and, whenever possible, to keep code further to the left: that means, for example, that I like to start a new line after the = in data and (if they're longer than one line) after function heads and after the do keyword, in order to 'swing' the indentation back left. I also prefer left-aligning operators as much as possible, and I do like alignment of repeated operators within lines (like :: in record definitions or -> in case-expressions). For example:

data Pair a b = Pair
  { pFirst  :: a
  , pSecond :: b
  } deriving (Eq, Show)

data Bool
  = True
  | False
    deriving (Eq, Show)

printTheBoolAndItsNegation :: Bool -> IO ()
printTheBoolAndItsNegation b = do
  putStrLn ("I got " ++ show b)
  putStrLn ("And `not " ++ show b ++ "` is " ++ show (not b))

A special case of my always-to-the-left principles is that if a function applies a short expression to something which can be 'swung' to the left, like a do block or a list comprehension, then I'll often include the shorter expression on the same line as the function head, and then swing the expression it applies to. That's a bit abstract, so for a concrete example:

fizzBuzz :: IO ()
fizzBuzz = mapM_ print
  [ fizz ++ buzz ++ mbNum
  | n <- [0..100]
  , let fizz = if n `mod` 3 == 0 then "fizz" else ""
  , let buzz = if n `mod` 5 == 0 then "buzz" else ""
  , let mbNum = if null fizz && null buzz then show n else ""
  ]

(I'll also talk about this in more detail later, but I use list comprehensions pretty regularly in day-to-day programming, and I think they're the right choice for a lot of iteration.)

I always camelCase my names. This is largely for consistency—-I actually find snake_case and kebab-case to be vastly more readable, and in the absence of an existing community style, I probably would gravitate to them—-but it's what Haskell uses, so it's what I use.

I try to name things using names whose length is proportional to the range of the scope in which they appear—-that is, fewer characters for a scope of a line or two, more characters if a name shows up for a longer block—-but I tend to feel that it's never a bad idea to pick a slightly longer name. I definitely have a few conventions I hold to lightly for particular varieties of names:

• x:xs for iterating over a generic sequence, and a similar _:_s for iterating over sequences of specific things. (e.g. if I'm iterating over a list of addresses, I might use addr:addrs or, for a single-line function, a:as.)

• Functions for creating a thing are generally mkThing. I mostly like mk because it's evocative but also only two characters: it gets out of my way.

• Things which might be Nothing I often give an Mb suffix, specifically when I'm going to discriminate on that same value and pull out the interior value. For example:

  logPathMb <- getEnv "LOG_PATH"
  case logPathMb of
    Nothing   -> die "No LOG_PATH provided"
    Just path -> runWithLogPath path
  

Naming is an art that's worth getting good at, and I don't know that I'm great at it, but I do like to think hard about exported names in APIs before I commit to a name.

Extensions

There are some extensions that are so comfortable to me that I almost always turn them on if there's even a minor chance I might need them: specifically, ScopedTypeVariables and OverloadedStrings.

There are a lot of syntactic extensions that I'm okay with if I feel like they're pulling their weight: a good example here is that some code can be made significantly cleaner by application of extensions like MultiWayIf, LambdaCase, and RecordWildCards. I'm not likely to turn those on in a source file unless I feel like not having them is painful. For a concrete example: parsing and reading JSON using the aeson library is much easier and more readable with RecordWildCards enabled, but I wouldn't use it if it made just one function nicer.

I have a similar relationship with a some of the type system extensions: RankNTypes, ExistentialTypes, GADTs, and TypeFamilies all can make code cleaner and more powerful, but again, I'm not going to turn them on unless it becomes very clear that I need them, or that a particular desirable API is straight-up inexpressible without them. Of these, I want to call out TypeFamilies in particular: sometimes, using TypeFamilies, especially closed type families, can make certain abstractions much nicer, as in using a type family to change the types of AST nodes based on the current phase of a compiler.

A lot of other extensions, though, I've never felt like I needed, and when I've used them I often feel they obscure the problem I'm solving. Many extensions—-even some of the ones I've already mentioned—-can make refactoring or analyzing code harder, and there are often better tools to reach for in those situations. In particular, almost any extension that exists to help with the definition or selection of more elaborate typeclass instances or contexts—-things like FlexibleInstances, FlexibleContexts, MultiParamTypeClasses, ConstraintKinds, and so forth—-tend to tip me off to the fact that I'm solving a problem with typeclasses that I should be solving another way. I'll get into that a little more down below, when I talk about my relationship with typeclasses in Haskell code.

(If I'm being honest with myself, I actually kind of like MonadComprehensions—-and I have semi-seriously pushed for ApplicativeComprehensions in the past as a better alternative to ApplicativeDo, which I find slightly rickety—-but I don't actually use monad comprehensions in my code in practice.)

Broader Principles

Now this section contains what I think is interesting: not, say, how many spaces to indent things, but rather, what kind of higher-level trade-offs to make while writing code.

Haskell records are bad, but use them anyway

I use a lot of records in my code, and the reason is simple: I like giving things names. I know naming things is supposed to be one of the hard problems in computer science, but in this case, I like to think of names as documentation of the purpose of a piece of data: giving a field a name tells me what that field is supposed to be or do. Any time a data type has exactly one constructor, I will try to give every piece of data inside it a field name. If it's a newtype, then it might be a field name like fromFoo, but I still do that anyway.

I should also be clear here: I use record syntax when I have a type with just one constructor. Partial functions are a dangerous thing to include and can silently introduce errors into code, and record selectors defined on only some constructors end up being partial functions! When I say 'records' here, I mean 'single-constructor types with record syntax'.

When creating values of a record type, I effectively always use the record syntax to do so. This is especially useful for records that contain more than two or three fields: sure, for a five-argument constructor, I could always look up what the arguments mean for every constructor and what order they appear in, but it's so much nicer to provide those by name and have that redundant characterization.

It's also a powerful way of refactoring function calls with more than two or three arguments. Haskell doesn't have named parameters, but they can be faked by bundling the information needed for a call into a single piece of data, and then that allows for e.g. providing defaults that can be overridden with record update syntax. I consider doing this for functions of four or more arguments; by the time I get to about six or seven arguments, not doing this is almost criminal.

This brings me to another point:

Never hesitate to create a type alias or—-even better—-a type

It doesn't matter if it doesn't get exported, or only gets used by one function, or has a wonky name: types are always good. One of my major pet peeves about Haskell-the-language is that I can't define new types within let bindings or where clauses, like one can in other ML languages, because sometimes I want a new type for just a few lines. Doesn't matter. Make it. This can go a long way towards clarifying data-structure-heavy code, and almost always makes it less susceptible to bugs, too.

It doesn't matter if the type I'm defining is 100% isomorphic to some other type, too: a common pattern in code I've written is to include a type which is identical to Maybe, occasionally monomorphized to some particular type, like

data CommandResult
  = SuccessfulResult Text
  | ErrorResult

In my view, a type like this is often better than just using a Maybe Text in these situations: using a Maybe is more flexible, but the flip-side is that it permits a slew of operations that I might not want to be valid on a CommandResult. Additionally, Maybe Text tells a reader little about where it came from—-it might or might not have a Text!—-but a CommandResult would localized to a smaller chunk of code.

As a related point:

Specialize for intent

This is one where I run against current Haskell orthodoxy, not to mention popular Haskell linters: while I like exporting polymorphic functions, I often prefer using (comparatively) monomorphic functions, even when they're a monomorphic variation on a more general polymorphic function. A good example here is concatMap, a function which I genuinely like. In many situations, concatMap acts exactly like the monadic (>>=) operator, but with the monadic type monomorphized to []:

concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
(>>=)     :: Monad m    => (a -> m b) -> m a -> m b

The only difference between the two functions (at present) is that concatMap can take an arbitrary Foldable value and turn it into a list. However, code that uses concatMap with an argument whose type is known to also be [a] will raise complaints from linters like hlint, which suggests using (>>=) instead.

This runs contrary to my taste in code: I prefer using concatMap in these situations precisely because it is less generic. The typechecker can easily tell that my use of (>>=) is working on lists, and upon deeper examination of the code I can of course find that out, but that may not be obvious to me, the reader, from a perusal of the textual context of the code: on the other hand, the function concatMap always produces a list, and thus gives a human reader specific, concrete type information, even if that type information is redundant to the type-checker.¹

In general, if I'm not explicitly working within an abstraction, I don't want to borrow generic features of that abstraction: I am happy to use ++ instead of <> to concatenate lists, and type-specific length functions instead of a generic Foldable one, and I do not like to rely on the Arrow typeclass unless I am explicitly writing Arrow-polymorphic code. Borrowing an abstraction to do something I can do without that abstraction feels like mixing concerns for me: if I have to keep details of the current code in mind, I'd rather be thinking in terms of what the code is actually doing, rather than in terms of a higher-level abstraction that's not actually abstracting anything.

Of course, if I am writing something that needs to be polymorphic, then of course I will use the polymorphic functions: if I'm writing a snippet of code that I want to be able to use different Monoid or Foldable or Arrow² instances, then those polymorphic functions make sense. That means that I am using those abstractions as abstractions. Similarly, sometimes an API has been designed so that no monomorphic operations are actually available: an example of this is the excellent trifecta parsing library, which is written to expose most practical operations in terms of a Parsing typeclass defined elsewhere, rather than exporting its own monomorphic operations. (This is, after all, why these abstractions exist in the first place: so that people can provide functionality while abstracting over them!) But, all else being equal, if I have to choose between a monomorphic and a polymorphic version that are otherwise the same function, and I'm working with concrete types that I know, then I will generally prefer the monomorphic function.

Another, related phenomenon is redundant typeclass constraints. As a simple example: say I'm implementing a set using a binary tree, ordering it by the type's Ord instance. An insert operation will of course need to have an Ord constraint, but in theory, my empty set doesn't actually need any such constraint: after all, the Ord constraint is only necessary in insert because I'm comparing the inserted value against existing values in the set. Why include an Ord constraint for empty, where there are no values to even attempt to order?

data Set a = Node a (Set a) (Set a) | Leaf

insert :: Ord a => a -> Set a -> Set a
insert datum Leaf = Node datum Leaf Leaf
insert datum node@(Node c l r)
  | datum < c = Node c (insert datum l) r
  | datum > c = Node c l (insert datum r)
  | otherwise = node

-- This constraint is unnecessary!
empty :: Ord a => Set a
empty = Leaf

In many (although not all) cases, I would prefer to include such a redundant constraint, and the reason, yet again, is communicating programmer intent. While there's nothing stopping me from creating an empty Set of an unorderable type, there is also no practical reason to ever do so: I would never be able to insert or remove anything from it, and I could only ever peform entirely trivial operations on it, such as observing that its size is indeed zero. My intent in exposing this API is for all sets to contain orderable types: why not enforce that intent with these constraints, even if those constraints aren't strictly necessary in the function body?

In many of the above cases, what I am doing is deliberately opting out of abstractions in favor of concrete knowledge of what my program is actually doing. Abstractions can enable powerful behavior, but abstractions can also obscure the simple features of what a program is doing, and all else being equal, I'd rather communicate to a reader, “I am appending two lists,” instead of the more generic, “I am combining two values of a type that implements Monoid.”

Qualify imports, even when it's not strictly necessary

This is a habit that I've come around to after writing several larger pieces of software in Haskell, especially Matterhorn: qualified imports are pretty much always a good thing. At some point, my habit was to carefully curate import lists instead, but there are trade-offs there: it becomes easy to find out where a function comes from by looking at the source file header, but harder to find out where it comes from when looking at the use site. By qualifying imports, I can instead get information at the use site about where an import comes from, which I've found to be more and more useful over time: coming in and reading the center of a module, I can easily observe that this function comes from the module imported as X while this one comes from the module imported as Y.

A side-note here is that sometimes, especially when I'm using only one or two functions from an external module, or when two or more external modules are closely related in their operation, I will import multiple modules qualified under a single namespace. For example, if I need one or two functions from both System.Directory and System.FilePath, then I might import them both to the same shared namespace:

import qualified System.Directory as Sys
import qualified System.FilePath as Sys

I also do this often with Data.Text and Data.Text.IO together. This is something to be done with care, and it's good to err on the side of importing each module with a distinct qualified name, but occasionally it does help readability to keep the number of distinct module names in use in a particular file low.

Treat imports and dependencies as a minor liability

External dependencies in general have a cost: it's not a huge one, but a cost nonetheless, and I think it's worth weighing that cost against the benefit pretty actively.

A minor cost—-one that matters, but not all that much—-is total source size. Haskell programs tend to pull in a lot of dependencies, which means compiling all of them can take a very long time and produce a lot of intermediate stuff, even if a comparatively small amount makes it in to the final program. This isn't a dealbreaker—-if I need something, I need it!—-but it's something to be cognizant of. If my from-scratch build time triples because I imported a single helper function, then maybe that dependency isn't pulling its weight.

A bigger cost—-in my mind, anyway—-is breakage and control. It's possible (even likely) my code has a bug, and then I can fix it, run my tests, push it. It's also possible that an external dependency has a bug: fixing this is much more difficult. I would have to find the project and either avail myself of its maintainer (who might be busy or overworked or distracted) or figure it out myself, learn the ins and outs of that project, its abstractions, its style, its contribution structure, put in a PR or discuss it on an email list, and so forth. And I can freeze dependency versions, sure, but the world goes on without me: APIs break, bugs get introduced, functionality changes, all of which is a minor but present liability.

It's not a dealbreaker, but it's a cost, one that I weigh against the value I'm getting from the library. Should I depend on a web server library for my dynamic site? Well, I'm not gonna write a whole web server from scratch, and if I did, it'd take forever and be worse than an existing one, so the benefits far outweigh the costs. But on the other hand, if I'm pulling in a few shallow helper functions, I might consider replicating their functionality inline instead. There's always a cost: is it worth the weight of the dependency?

A concrete example where I decided, “No, it's not worth the dependency,” is in my config-ini INI parsing library. It includes an API that uses lenses. The lens library is very heavyweight: it includes a lot of transitive dependencies and a significant amount of code in its own right, and even minimal lens-compatible libraries like lens-family-core are comparatively hefty for what I needed: the Lens type alias and the ability to get and set a lens. Redefining those inline takes less than a dozen lines of code. In this case, the cost of duplicating those functions—-easily verified as correct!—-in my module was low enough that I didn't bother importing any lens library at all!

But of course, the Matterhorn chat client I work on does import a lens library. I'm less concerned about the cost of dependencies for a final executable, as it's not going to inflate anyone else's binary size or build process, and we use a significant number of other helper functions. In that case, the cost of duplicating that functionality inline is much, much greater than just using the library.

So my principle here isn't “always minimize dependencies”, but rather, “always remember to weigh the value of the dependency against its cost.”

Iterate with list comprehensions

I'll start out by saying that there are times I wouldn't prefer list comprehensions. For example, if I'm just mapping an existing function over a list, then I'd definitely prefer map f xs to its comprehension cousin [ f x | x <- xs ]: the former is clearer in its intent and doesn't introduce any new short-lived names. Similarly, a quick filter or even a map f . filter g will usually be shorter and clearer than the comprehension [ f x | x <- xs, g x ].

However, there are a lot of situations where a comprehension is much clearer than its hypothetical map– and filter-based equivalent. One of the biggest advantages to comprehensions, at least in my experience, is that they can use refutable patterns in order to simultaneously decompose and filter expressions from a list. Consider the actual definition of the catMaybes function from Data.Maybe:

catMaybes :: [Maybe a] -> [a]
catMaybes ls = [ x | Just x <- ls ]

We could write this using a combination of existing partial functions (i.e. as map fromJust . filter isJust) or other abstractions (>>= maybeToList) or we could write it with manual recursion, but this snippet is, in my opinion, much more terse and readable, and doesn't rely on any other helper functions. This extends to more complicated list processing tasks, as well:

getGoodDogs :: [Person] -> [String]
getGoodDogs people =
  [ name ++ " is a good dog."  -- all dogs are good
  | Person { personPets = pets } <- people
  , Pet { petName = Just name, petType = Dog } <- pets
  ]

For comparison, here's a point-free alternative to this snippet:

getGoodDogs' :: [Person] -> [String]
getGoodDogs'
  = map (++ " is a good dog.")
  . Maybe.catMaybes  -- assuming that Data.Maybe is imported
  . map petName
  . filter petIsDog  -- assuming this is defined
  . concat
  . map personPets

Some people may prefer this style (or might prefer a slightly different variation, e.g. by combining the concat . map personPets into (>>= personPets)), but for my personal preferences, I prefer reading the comprehension-based one: both of them transform a list in a 'step-by-step' manner, but the comprehension-based one has three 'logical' steps that correspond to decomposing each element of the people list, selecting and decomposing each pet from a person's list of pets, and then joining the final string, while the point-free one includes several steps or details related to massaging the relevant types (c.f. the concat and catMaybes lines), and also relies on a handful of other helper definitions that aren't necessary in the comprehension case.

Finally, ParallelListComp is a very good extension, because it provides a single language-level mechanism that otherwise would have to be filled with various zip and zipWith variants of various arities. (I will admit I'm less sold on TransformListComp, but maybe I haven't found a good use for it yet!)

Be 100% sure a typeclass is the right choice

I'm not gonna go hard-line like some people and assert that typeclasses are “considered harmful” or that they should be blanket avoided, but I do think they're easy to overuse, and it's easy to reach for one without weighing the upsides and downsides of typeclasses. And what's more, non-typeclass solutions can be surprisingly powerful!

The biggest advantage typeclasses provide is implicit instance selection. This is why typeclasses are such a powerful net win when working with, say, numeric types: without typeclasses, we'd have to have a separate monomorphic + for each numeric type, and that'd get unwieldy pretty fast! With a typeclass, we get that instance selection for free.

But on the other hand, typeclasses necessarily permit at most a single instance per type. In the case of +, that's pretty reasonable, but it's a little bit of a harder proposition when talking about something more like show. There are a lot of ways to turn a value into a String: we might want to control indentation, or padding, or use different representations (e.g. decimal or octal or hexadecimal for numbers), all of which would require elaborate newtype wrappers if we wanted to do them with the existing Show abstraction.

Of course, I'm picking on Show when I shouldn't be: Show isn't for tight control over printing, it's for quick programmer-focused output: if I wanted to tightly control how to print a structure, then I should be using a printf-style library or a pretty-printer, not Show. Let's instead talk about a classic example of a typeclass that I think shouldn't be a typeclass: QuickCheck's Arbitrary.

A simplified form of QuickCheck's Arbitrary typeclass looks like

class QC.Arbitrary a where
  arbitrary :: QC.Gen a

Where the Gen monad encapsulates non-deterministic generation of structures along with some extra information about the 'size' and 'depth' of what's being generated. In practice, that means that an Arbitrary instance for a type is going to look pretty mechanical: most of the fields can be initialized with the result of a simple call to arbitrary:

data Pet = Pet
  { petName :: Maybe String
  , petType :: PetType
  , petAge  :: Int
  }

instance QC.Arbitrary Pet where
  arbitrary =
    Pet <$> QC.arbitrary
        <*> QC.arbitrary
        <*> QC.arbitrary

Ah, but wait, I say to myself in this contrived scenario! My application's validation code only ever creates Pet values with non-negative ages, so most of my QuickCheck tests—-the ones that test internal application functionality—-are going to only be interested in valid Pet values. I will modify my instance accordingly: in this case, I can using the QuickCheck-provided Positive newtype, whose Arbitrary instance will only ever create positive numbers, in order to only ever generate pets with non-negative ages:

instance QC.Arbitrary Pet where
  arbitrary =
    Pet <$> QC.arbitrary
        <*> QC.arbitrary
        <*> (QC.getPositive <$> QC.arbitrary)

Ah, but sometimes I do want to run QuickCheck tests over invalid Pet values, just in case. Well, what to do now? I guess I need a newtype wrapper over Pet, too, so I can have one instance for valid Pet values and another for possibly-invalid ones:

-- lies; all pets are valid
newtype InvalidPet = InvalidPet { fromInvalidPet :: Pet }
instance QC.Arbitrary InvalidPet where
  arbitrary =
    (InvalidPet . Pet) <$> QC.arbitrary
                       <*> QC.arbitrary
                       <*> QC.arbitrary

Ah, but also pet names aren't going to be arbitrary unicode sequences; they're going to be validated so that people don't name their pets emoji or the empty string or something like that, so now I have two axes along which a pet might be invalid. Do I need four newtypes, for the cross-product of the four configuration options I want?

I'm of course being obtuse: my obvious choice here would be not to create an Arbitrary instance for Pet, but rather to create a function that returns a Gen value that I can use explicitly:

genPet :: Bool -> Bool -> QC.Gen Pet
genPet validName validAge = Pet <$> name <*> QC.arbitrary <*> age
  where
    name | validName = genValidName
         | otherwise = QC.arbitrary
    age | validAge  = QC.getPositive <$> QC.arbitrary
        | otherwise = QC.arbitrary

While somewhat contrived, I don't think the above is an unlikely scenario. In most situations, I wouldn't want just a single, non-modifiable generator for a type: I'd almost always want a generator that has some controls, or one of several different generators depending on context. Even with simple types like the built-in numeric types, I would want to generate numbers that have various properties that aren't inherent to the type: an Int that's always non-negative, or that's a valid index into a list, or something like that. QuickCheck offers various newtypes to work around this, but even still, one often has to resort to other generation methods (e.g. by filtering by a check or generating from a list of possibilities instead of using the bare Arbitrary instance.)

All that is to say: the Arbitrary typeclass makes sense if the choice of Gen t is always a function of the type t, but in practice, that's rarely true.

I've established now that some uses of a typeclass like Arbitrary are probably ill-advised, or at least could be better served by using named functions: but of course, QuickCheck does have many named functions of that sort which coexist peacefully with Arbitrary instances. And there's another big factor in the use of the typeclass: the convenience of being able to use a single value name (arbitrary) instead of looking up a different name for every generator function. There is something very pleasant about being able to write (,) <$> QC.arbitrary <*> QC.arbitrary: no need to look up the right function name for every type, and using Gen becomes almost mechanical!

But in the long term, I would still prefer an explicit version. Consider what the above, naïve generator—-the one that only generates 'valid' pets—-would look like using the API provided by hedgehog, a newer QuickCheck-like library that does not include a typeclass analogous to Arbitrary:

genValidPet :: Gen.Gen Pet
genValidPet =
  Pet <$> Gen.maybe (Gen.string (Range.linear 1 50))
      <*> Gen.element [Dog, Cat]
      <*> Gen.int (Range.linear 0 30)

Notice that every Gen function is explicit about exactly what it's generating: a Maybe wrapper around a String of a length that's at least 1 and at most 50; one of the two values Dog or Cat; an integer in the range 0 to 30. This is definitely more tedious to write than the typeclass-based version: I can't just spam arbitrarys separated by <*> until it compiles, now I gotta make sure I know the right function names, and it's noisier and bigger, and there's more information per line...

But if I haven't touched this code in weeks or months or years, and I come back to it: I can clearly see what it's doing. I don't have to go consult the definition of Pet to find out what the types are and what instances are getting called, because I know exactly what functions are getting invoked at every point.

That is to say: the implicitness of the Arbitrary approach is optimized for writing, but the explicitness of manual functions is optimized for reading and remembering.

And I haven't gone into the other places where typeclasses can fall down: for example, the way that typeclass resolution can sometimes fail, the various complicated extensions that can be used to get around typeclass selection, the sometimes voluminous and sometimes inscrutable error messages that they can sometimes generate: all those are factors, sure, but they're not the main reason that I try not to reach for typeclasses: even if all those things were solved via some kind of technical magic or a tower of LANGUAGE pragmas, I still would try to use explicit functions instead of typeclasses in my Haskell code.

I also should reiterate that I still use typeclasses, and sometimes I do want them! There are times that the explicitness is too heavy a cost, or the instance selection maintains invariants that I want to have maintained, or the code is just plain better-looking. But I also think that there are many places in Haskell where a typeclass is used and an explicit function or record of functions would be preferable, which is why my personal tendency is to avoid writing a new typeclass until I'm sure that what I need is a new typeclass.

In Summary

There's a unifying theme to a lot of my Haskell style, and it is this: be explicit and use names. Why pervasively use record fields? I'm being explicit about the purpose of those pieces of data by giving those fields a name. Why qualify imports? I'm being explicit about their provenance by giving their provenance a name. Why use functions or records of functions instead of typeclasses? I'm being explicit about what functionality I'm dispatching to by giving that functionality a name. A related theme is: optimize for reading code later. If it takes longer to write or uses more lines or more variable names, but it's going to be clearer to another person reading my code—-or to me, coming back to that source file in a month or a year—-I will absolutely take the time to write the longer code.

But also, like a mediocre high-school essay writer, I want to reiterate what I wrote at the beginning: this is one of many styles, and it has its own tradeoffs! (Verbosity being a big one here.) Your style might be (and probably is) different, and that's a good thing: in fact, I'd be interested in reading analogous posts to this one that describe the specifics of and motivation for other people's Haskell styles! I don't think there's a “wrong way” to write Haskell: there's a multiplicity of possibilities, and we as Haskell users should embrace that!

...well, unless y'all use TypeInType, in which case you're clearly depraved in ways that medical science cannot fix.

This post is a bit more opinion-heavy than my usual fare here, but I wanted to lay out my position on this pretty clearly so I can point to it in the future.

I recently saw a comment on Twitter which irked me a bit. I'm not going to link to the original—I certainly don't want to start the kind of argument Twitter is infamous for!—but the comment went:

From a Curry-Howard perspective, “I like programming but I don't like maths.” means “I like programming but I don't like programming.”

I objected to this on Twitter as well, but it's hard to be nuanced or insightful in 140 (or even 280) characters, so I'm writing this slightly longer, hopefully clearer explanation of what it is that bothers me about this sentiment.

My first objection is that this sentiment draws an analogy that is materially and practically incorrect: when someone says, “I like programming,” it is a safe assumption that they mean, “I like sitting down at a computer and using various tools to describe software that I can then run.” On the other hand, when someone says, “I don't like maths,” it is a safe assumption that they mean, “I don't like performing operations in formal systems in my head or on paper in order to solve problems.” These two tasks are, in material and concrete terms, not the same: the way you set about them is often different, the artifacts you produce and the goals you have are often different, and the problems that arise in the course of performing them are often different! (I rarely have to debug segfaults when I do pen-and-paper mathematics, for example.)

You might object that programming and math do have much in common: in order to write a good program, you have to simulate a formal system in your head before you run your program just as in mathematics, and you also you can perform mathematical tasks using a computer-aided sytem (e.g. with an interactive theorem prover like Coq or Lean.) And there are some common goals, common artifacts, and common problems between the two. All that is true: programming and math have a common structure, and there are strong overlapping areas of practice, and I would argue that we should make the practices of both computing and mathematics more like each other! But for many people who do math or programming or both, the two activities are decidedly not identical.

Consequently, a reasonable interpretation of the sentence, “I like programming but I don't like maths,” might be, “I like making a computer do things but I don't like simulating a formal system on paper,” and indeed, if someone said this to me sans context, this is probably what I'd understand it to mean!

My second objection is that it's a somewhat broad (although not at all unusual) overstatement of what the Curry-Howard Isomorphism actually is. The Curry-Howard isomorphism is generally stated as, “Proofs are programs and programs are proofs.” Already, we can see a problem: the comment in question didn't say 'proofs', it said 'maths'. There are many things that a person might refer to as 'maths' that are not just proof-writing.

And even that short statement of Curry-Howard is a bit reductive: the Curry-Howard isomorphism is actually an isomorphism between proof calculi like natural deduction or sequent calculus, and static type systems for models of computation like the simply typed lambda calculus. Many programming languages—especially statically typed functional languages like Haskell and OCaml, but by no means only them—have type systems that correspond to reasonable proof systems, but many other programming languages used in practice have static type systems that correspond to unsound or nonsensical proof systems, and many other programming languages used in practice are dynamically typed and therefore have little if any meaning when viewed through the lens of Curry-Howard!

So Curry-Howard is not really about all programming, nor is it about all math. An accurate statement might be, “All programs in typed languages correspond to proofs in a formal proof system,” but that might be excessively pedantic, and it's rather a lot of characters to tweet. “All programs are proofs,” is reductive, but probably fine in context. “All programming is math,” is a clear step beyond what the Curry-Howard Isomorphism actually means.

Now, to be clear, the Curry-Howard isomorphism is an incredibly powerful idea, and I genuinely think that working programmers should be familiar with it. But assembly-language programming is also programming, after all, and it's not isomorphic to proof-writing in the same way that Haskell programming is.

My third and biggest objection to this statement is much, much simpler: it's divisive and, well, smug. While I nitpicked the phrasing above for being over-broad and reductive, I did carefully mention that there's still truth to it: someone steeped in the kinds of programming and mathematics where Curry-Howard is commonly cited likely wouldn't bat an eye at the quote! Programming (of a certain kind) and mathematics (of a certain kind) are deeply intertwined to the point of being slightly different views on the same underlying concepts and activity—and to the extent that they're not, I'm sure the sure the originator of the quote would agree with me that we should endeavor to bring them closer together by both tooling and practice.

But it's important to note that not everyone does this kind of programming or this kind of math. For a person whose exposure to mathematics is calculus and statistics, and whose exposure to programming is Python and R—a likely scenario for many people who do scientific computing!—the sentence above comes across at best as obscurantist and pedantic, at worst as nonsensical. This is true even for several working programmers and mathematicians to whom I mentioned this quote. Its phrasing is clearly intended to wow people, to evince a deep and perhaps surprising truth about the practices of math and programming: “Programming and math are exactly the same thing, have I blown your mind yet?” This quote is also radically non-applicable to the experience that many people have had of mathematics and of programming. When such a person reads the statement in question, it comes across as being a self-satisfied kind of ivory-tower sentiment.

Which—not at all coincidentally!—is exactly the impression that many working programmers have of functional programmers.

The person who wrote the original comment apparently saw my criticism—at least, he identified that criticism existed, and I can only assume that he was referring to mine—and his rebuttal was this:

What good does it do you for programming not to be a mathematical activity?

This comment is a pretty radical misreading of what I had said: I was specifically criticizing the rhetoric, not the content, and my comment had even identified this kind of statement as coming from “...people I in general basically agree with.” But even so, the content of this restatement is not actually the same as the content of his earlier statement: the first one glibly identified programming as identical to mathematics while explicitly minimizing any difference between them, while the second comment claims programming is a mathematical activity, a much weaker, less contentious, and less divisive statement.

Is programming a mathematical activity? Very often, yes! And I would contend that our work as programmers should be to make programming even more of a mathematical activity than it is already. We should build proof tools around code and simultaneously make code more amenable to proving. We should educate programmers about the kinds of mathematics that can make their day-to-day job of programming easier and more powerful. We should elucidate the existing mathematical structure they might not realize is already present in what they're doing. And we should build new mathematical abstractions that can benefit both programmers and mathematicians in new and powerful ways.

Right now, many programmers don't think of themselves as mathematicians. In order to bridge this divide, it's important to reach out and talk to these groups in the language that they understand: exposing the mathematical structure of programming and illustrating through example and practice the power of understanding programming as a mathematical activity.

But if we articulate our position as, “Math and programming are identical, have I blown your mind yet?” we don't come across as people trying to push for a better world, who are trying to share tools and knowledge to make both mathematics and programming better. We come across as preaching sectarians, and we unfortunately become yet another data point for the “functional programmers are smug and out-of-touch” pile.

This is apparently quite a contentious opinion, but after having worked with them for a while, I in general like Rust's modules. However, it's not contentious at all to say that they are complicated and hard to understand for someone looking at them for the first time. So, let's talk about Rust modules, building up some principles for understanding them as we go.

Important note: this blog post represents the state of Rust modules as of the time of writing. There are changes in store, and the module system as used in the Rust of 2019 is gearing up to be pretty different!¹

Part One: Modules

Before I get to actual code snippets, let's talk about the first two basic principles:

• Every named item in Rust—-functions, types, values, modules—-can be made public by prefixing it with the pub keyword.
• Every compilation unit—-a library or an executable, what Rust calls a crate—-contains a 'root' module. For a library, this root module is defined in lib.rs, and for an executable, it's defined at main.rs.

Let's say I make a new fresh Cargo project that's a library. I get a file at src/lib.rs. Every item defined in that file lives in the root module, so let's write a simple function here:

// in src/lib.rs
pub fn hello() {
    println!("Hello!");
}

Inside of this module, we can refer to this function using the unqualified name hello, but we also can use a qualified name, which represents a path through our module hierarchy to get to the name. In this case, hello is exposed through the root module, so the qualified name for hello is ::hello, which leads us to another principle:

• The root of the current compilation unit's module hierarchy is indicated in qualified paths with an initial ::.

So let's make a new module inside of the root module. Submodules are always indicated with the mod keyword, but (as we'll see) this keyword can be deployed in different ways depending on where we want to implement the module. For now, we'll define the contents of the module inside the same source file, in a curly-brace-delimited block headed by pub mod my_module_name:

// in src/lib.rs
pub mod english {
    // #1
    pub fn hello() {
        println!("Hello!");
    }
}

// #2
pub fn hello() {
    ::english::hello();
}

At this point, the root module contains two public items: ::hello, a function, and ::english, a module. In turn, the module ::english contains a public item: a function ::english::hello. In this case, I'm using a fully qualified names for disambiguation: this is useful here because I have two different defined functions both named hello. Without explicit qualification, the name hello will refer to different things depending on the module scope: when referenced inside the english module, hello refers to the hello function we defined the that I've indicated with the comment // #1, and outside of the english module, hello refers to the hello function I've indicated with the comment // #2.

While there is never 'ambiguity' from the point of view of the Rust compiler, having the same name in different scopes can be confusing for us as readers and writers of code. We can always be explicit and use fully qualified names to alleviate any confusion. For example, we can (although I don't know why you would) write the following code:

// in src/lib.rs
pub mod english {
    pub fn hello() {
        println!("Hello!");
    }

    pub fn outer_hello() {
        ::hello();
    }
}

pub fn hello() {
    ::english::hello();
}

In this example, we've added the new function ::english::outer_hello, which invokes ::hello using a fully qualified path, which in turn invokes ::english::hello using a fully qualified path.

So we've discovered a new principle:

• Name lookup in expressions is relative to the module in which the expression appears unless the name is fully qualified.

There are also ways of traversing the module hierarchy with relative names. The above example can be rewritten using relative names like so:

// in src/lib.rs
pub mod english {
    pub fn hello() {
        println!("Hello!");
    }

    pub fn outer_hello() {
        super::hello();
    }
}

pub fn hello() {
    english::hello();
}

The expression english::hello() inside of the function ::hello is in the root module, and therefore the name is looked up relative to the root module. The declaration of ::english::outer_hello, however, is relative to the module ::english, so therefore if we want a relative reference to ::hello, we need to first move up a module level with the super keyword in order to access the item we want in the parent module. There's also a self keyword, which allows us to look up names relative to the current module. That keyword is redundant here—-we're already looking up names relative to the current module by default!—-but we'll find a use for it later on.

• You can use super and self in qualified names to traverse the module hierarchy in a relative way.

(Note also that super and self only work at the beginning of a path: that means we can't write a perverse relative path like ::english::super::english::hello—-not that you'd want to write that anyway!)

There are also two other ways of creating a module, but all of them use the mod keyword in some way. Right now, we've defined a module using a curly-brace-delimited block in a single file, but we can also create a module by placing the definitions of items in that module into a separate file named the same name as the module. In these examples, because our module is called english, we can put declarations into the file src/english.rs, so our two source files will look like

// in src/lib.rs
pub mod english;

pub fn hello() {
    self::english::hello();
}

and

// in src/english.rs
pub fn hello() {
    println!("Hello!");
}

pub fn call_outer_hello() {
    super::hello();
}

Notice that we've kept the pub mod english declaration in the root module, but we've removed the body of that declaration. At the same time, the contents of src/english.rs are (modulo indentation and the comment) identical to the contents of the english module before, and similarly none of the rest of the code had to change at all. This reorganization is purely for our benefit: the code does not care whether we use an inline module or an external module.

There's a third way we could have organized our code, as well: instead of creating a file named after our module, we could have created a directory named after our module, and included a file called mod.rs inside that directory. Again, we could have equivalently written these modules:

// in src/lib.rs
pub mod english;

pub fn hello() {
    self::english::hello();
}

and

// in src/english/mod.rs
pub fn hello() {
    println!("Hello!");
}

pub fn call_outer_hello() {
    super::hello();
}

Notice that even less had to change this time: the contents of the files are identical to before, and only the on-disk organization has changed! Again, from Rust's point of view, the tree of modules and items we've created here is identical. This final on-disk organization method is more convenient if we want to create other nested submodules that are contained in their own files: if we wanted to have a module ::english::plurals, then we could define the module ::english in the file src/english/mod.rs, and then define the module ::english::plurals in src/english/plurals.rs². If we used either of the other two on-disk organization methods, then we would either have to write nested module blocks like

pub mod english {
    pub mod plurals {
       // ...
    }
}

Or we would have to have a pub mod plurals { ... } block inside of the source file src/english.rs.

However, like I said, all of these choies are mostly important to us as programmers structuring a project on-disk and maintaining it as a repository, but from Rust's point of view, they define an identical namespace. In summary:

• Modules can be defined in three ways—-using lexical pub mod my_module { ... } blocks, using a src/my_module.rs file, or using a src/my_module/mod.rs file, but the choice of approach is immaterial to the namespace structure being constructed.

This can be a powerful way of growing a project: a module might start life as one or two types and functions inside a source file, and as they grow, they can get moved first into another file, and then into a directory that itself contains several more files, and this can happen transparently, without any user of the code (inside or outside my crate) having to be aware of it.

Now we can move on to

Part Two: Extern Crates

The extern crate declaration does two things at once: it specifies a dependency on an external named crate, and it includes that crate's root module as a named module in the current module's namespace.

Let's build some randomness into our example code. We will use the rand crate to get some random numbers, and use them to choose from a list of greetings.

// in src/lib.rs
// importing an external crate in the root
extern crate rand;

// our statically-chosen list of greetings
static GREETINGS: &[&'static str] = &[
    "Hello!", "Heya!", "Greetings!",
];

pub fn hello() {
    // choose a random valid index
    let index = ::rand::random::<usize>() % GREETINGS.len();
    // and print the chosen greeting
    println!("{}", GREETINGS[index]);
}

Notice that the library functions in the rand crate are now available as though they were defined in a module called rand in the root of our crate. By default, the name of the imported module is the same as the name of the crate—-but we can change that! If we want a different module structure, we can use the as keyword to rename the imported module to a different name—-in this case, let's call it my_rand:

// in src/lib.rs
// importing an external crate in the root, with renaming
extern crate rand as my_rand;

static GREETINGS: &[&'static str] = &[
    "Hello!", "Heya!", "Greetings!",
];

pub fn hello() {
    let index = ::my_rand::random::<usize>() % GREETINGS.len();
    println!("{}", GREETINGS[index]);
}

Now, we've separated out the specification of the external name of the crate we want (the rand crate) from the name we're giving its root module in our internal module hierarchy (::my_rand).

Unlike many programming languages, we can declare extern crate dependencies anywhere in the module hierarchy we want! So, for example, let's import rand underneath a new module. Notice that we need to include a pub qualifier to make sure the module it creates is accessible outside of the deps module. (Remember that all names brought into scope must be made explicitly public with the pub keyword!)

// in src/lib.rs
// importing an external crate in a submodule
pub mod deps {
    pub extern crate rand as my_rand;
}

static GREETINGS: &[&'static str] = &[
    "Hello!", "Heya!", "Greetings!",
];

pub fn hello() {
    let index = ::deps::my_rand::random::<usize>() % ::GREETINGS.len();
    println!("{}", ::GREETINGS[index]);
}

This is a pretty stark departure from how most languages think of external dependencies: usually, they just get placed in some kind of root namespace, and you might be able to import them under a different name (like with Python's import module as name syntax). In Rust, you have full control over your own module hierarchy, and so you can insert the root module of an external crate whever you'd like.

• The extern crate declaration specifies a dependency on a named external crate and imports that crate's root module as a named module in the current module scope.
• The name of a module created by extern crate defaults to the name of the crate, but can be explicitly specified with the as keyword.

As an aside: why would you want to do this? Well, one reason is that you might have a lot of external dependencies, and it would be nice to manage them. Imagine that you're writing a video game, and therefore depend on a lot of libraries for things like graphics and physics and so forth. You could therefore imagine wanting to both organize and rename your dependencies in order to manage them, something along the lines of:

pub mod graphics {
    pub extern crate opengl as gl;
    pub extern crate sdl;
}
pub mod img {
    pub extern crate png;
    pub extern crate libjpeg as jpeg;
}

Now you can organize your dependencies in a way that's convenient and structured!

Part Three: Uses

The last thing we haven't talked about is the use declaration, which is given a qualified path and creates a new local name for the item named by that path.

• The use keyword pulls in names from another scope into the current one.

We often use this with functions or types defined by external crates, so we can pull them into scope with more convenient local names, but it works with any named item, including modules.[\^2]

It's not uncommon to see declarations like use std::fs;, which allows the module ::std::fs to be accessed locally as fs without the std:: prefix. This brings a module, not a function or type, into the local scope.

// in src/lib.rs
extern crate rand as my_rand;

// ...but pulling the random function into scope here
use my_rand::random;

static GREETINGS: &[&'static str] = &[
    "Hello!", "Heya!", "Greetings!",
];

pub fn hello() {
    // we can now use random unqualified
    let index = random::<usize>() % GREETINGS.len();
    println!("{}", GREETINGS[index]);
}

Confusingly, use declarations work differently from expressions, because names in use declarations are always relative to the root. Consider the example below: because the extern crate rand as my_rand was declared in the root module, the fully qualified name of the random function is ::my_rand::random, but when I use that name inside the english module, I give it a relative path as though I'm looking up the symbol from the root.

// in src/lib.rs
extern crate rand as my_rand;

pub mod english {
    use my_rand::random;

    static GREETINGS: &[&'static str] = &[
        "Hello!", "Heya!", "Greetings!",
    ];

    pub fn hello() {
        let index = random::<usize>() % GREETINGS.len();
        println!("{}", GREETINGS[index]);
    }
}

pub fn hello() {
    english::hello();
}

If I do want to use a name that's relative to the current module, I can use the self keyword in the path, which starts me instead from the module containing the use declaration. In the below example, we've moved the extern crate line inside of the module, so now the my_rand module lives in ::english::my_rand, and we then use an explicit relative path to pull in the function we want.

// in src/lib.rs

pub mod english {
    extern crate rand as my_rand;

    use self::my_rand::random;

    static GREETINGS: &[&'static str] = &[
        "Hello!",
        "Heya!",
        "Greetings!",
    ];

    pub fn hello() {
        let index = random::<usize>() % GREETINGS.len();
        println!("{}", GREETINGS[index]);
    }
}

pub fn hello() {
    english::hello();
}

So our last principle is:

• Name lookup in use declarations is relative to the root module unless the name is explicitly made relative with the self keyword.

I also can use the pub keyword on uses to pull names into a module while simultaneously exposing those names outside of that module. Sometimes I like to do this to carefully namespace a subset of external names I plan on using, allowing me to group several libraries together, or pick-and-choose items from separate but related compilation units into a single module for local use.

pub mod io {
    pub use std::fs::File;
    pub use std::io::*;
}

All The Principles In One Place

To summarize, I'm going to pull all the principles from the above text into a single list:

• Every named item in Rust—-functions, types, values, modules—-can be made public by prefixing it with the pub keyword.
• Every compilation unit—-a library or an executable, what Rust calls a crate—-contains a 'root' module. For a library, this root module is defined in lib.rs, and for an executable, it's defined at main.rs.
• The root of the module hierarchy is indicated in qualified paths with an initial ::.
• Name lookup in expressions is relative to the module in which the expression appears unless the name is fully qualified.
• You can use super and self in qualified names to traverse the module hierarchy in a relative way.
• Modules can be defined in three ways—-using lexical pub mod my_module { ... } blocks, using a src/my_module.rs file, or using a src/my_module/mod.rs file, but the choice of approach is immaterial to the namespace structure being constructed.
• The extern crate declaration specifies a dependency on a named external crate and imports that crate's root module as a named module in the current module scope.
• The name of a module created by extern crate defaults to the name of the crate, but can be explicitly specified with the as keyword.
• The use keyword pulls in names from another scope into the current one.
• Name lookup in use declarations is relative to the root module unless the name is explicitly made relative with the self keyword.

This is a lot to take in at once, and it can be confusingly different from other languages, but the biggest difference is that your module tree is always explicit. The drawback is that it's verbose and sometimes offers flexibility that can be unnecessary or confusing, but the advantage is that what's happening it's always explicit in the code, and also that you can express exactly the hierarchy of names and namespaces that you want.

Over the weekend, a friend of mine who is currently learning Rust asked me a question. He was using serde for serialization, and he wanted a single function that took a file path as argument, opened the file, deserialized it as a particular type, and returned that value, where the return type could be inferred from context. (For this example, I'm going to ignore error-handling and just use .unwrap() to bail out on failures.) I hadn't used serde much myself, so I briefly assumed the function in question would just look like this:

fn load_from_file<T>(path: String) -> T
where
    T: serde::Deserialize
{
    let mut file = File::open(path).unwrap();
    serde_json::from_reader(&mut file).unwrap()
}

But it wasn't quite so easy, and, like most of the trickier parts of Rust, the problem is that lifetimes can be tricky. The serde::Deserialize trait takes a single parameter: a lifetime which corresponds to the lifetime of the input source. In the above function, the input source is file from which we're reading, but it might also be a str (using the from_str function) or a slice of bytes (using the from_slice function). In any case, the deserializer needs to know how long its input source lives, so we can make sure that the input source doesn't get suddenly closed or freed while it's in the middle of parsing.

Okay, that means we need a lifetime parameter to give to serde::Deserialize. Let's try the obvious thing and add a lifetime parameter to the signature of the function:

fn load_from_file<'de, T>(path: String) -> T
where
    T: serde::Deserialize<'de>
{
    let mut file = File::open(path).unwrap();
    serde_json::from_reader(&mut file).unwrap()
}

This looks nice at a glance, but it doesn't compile! You can plug this code snippet into rustc and it will (with its characteristic helpfulness) suggest exactly the correct code to write. But I'm less interested here in what to write, and more in why we're writing it: why does this not work, and why does the suggested fix work?

Let's step back to very basic Rust: when you have a generic parameter to (say) a function, what you're saying is that you want that particular implementation detail to be supplied by the use of the function. Here's an incredibly trivial example: I can write a polymorphic identity function, a function that simply returns the value given it, by giving it a type parameter like this:

fn identity<T>(x: T) -> T { x }

When we use the identity function with a value of a particular type—-say, by calling identity(22u32)—-we're also implicitly providing a concrete choice for the type T, which it can infer from the type of the argument. Rust also allows us to pass this type parameter explicitly, with the slightly unwieldy syntax identity::<u32>(22). Either way, the use site of identity provides the information necessary to choose a concrete type T.

The same goes for lifetime parameters: when we write a function like

fn ref_identity<'a, T>(x: &'a T) -> &'a T { x }

what we're saying is that the reference we're taking as argument lives some amount of time, but that amount of time is going to be known at the call site, and it'll get that information inferred from individual uses of ref_identity. When we call ref_identity(&foo), we're saying that the lifetime parameter 'a is going to be however long foo lives in that context.

Okay, so with that, let's look at the our first pass at writing load_from_file:

fn load_from_file<'de, T>(path: String) -> T
where
    T: serde::Deserialize<'de>
{
    let mut file = File::open(path).unwrap();
    serde_json::from_reader(&mut file).unwrap()
}

What's the problem here? Well, our type doesn't actually reflect what the body of our function does. Remember that the lifetime parameter we give to Deserialize corresponds to the lifetime of the input source to the deserializer, and we already know the lifetime of our source: it's the lifetime of our file variable. That lifetime isn't something we need to get from the caller—-for that matter, it's not a piece of information that the caller would even have access to! Expressing that as a parameter in this instance is blatantly incorrect.

...but then we've got a problem, because we need something to give Deserialize as the lifetime parameter, and Rust doesn't have a way of expressing, “The lifetime of this variable here in the scope I am currently defining.” We're caught: we need some lifetime parameter there, but it can't be an argument, and we can't name the specific individual lifetime that we know it should be.

So instead, one way of writing this is by saying, “This works for any lifetime we might care to give it.” The difference here is subtle but important: we aren't expressing the notion of “any lifetime you, the caller, want to give me”, we are expressing the notion of “any lifetime at all.”

It turns out that Rust has a syntax for this, which uses the for keyword:

fn load_from_file<T>(path: String) -> T
where
    T: for<'de> serde::Deserialize<'de>
{
    let mut file = File::open(path).unwrap();
    serde_json::from_reader(&mut file).unwrap()
}

If we try this, this function now works. And notice that the type parameter list now includes only one thing: the T type that we're deserializing to, which is exactly what we want!

The key here is the for<'a> T syntax: the for acts as a binder for one or more fresh lifetime parameters, which are then used in the following type. Here, we're introducing a new 'de lifetime and then filling that in in Deserialize. Importantly, this lifetime is now quantified over all possible lifetimes, not merely a lifetime that the calling context might supply. And of course, 'all possible lifetimes' includes the lifetime of the file variable inside the function!

The for<'a> T syntax is a feature called Higher-Ranked Trait Bounds and this feature was specifically necessary to support unboxed closures, but it ends up being useful in other situations—-like this one!

Earlier today I pasted a snippet of Haskell code into our work chat that contained a multi-parameter type class instance that looked more or less like this:

instance a ~ b => C a b where {- ... -}

The constraint a ~ b in this declaration is a type equality constraint: it means that a and b must be the same type. One of my coworkers saw this and remarked, more or less, “Why did you write it in that obtuse way? You could have just declared an instance for C a a, which means the same thing.”¹

Those two declarations actually don't mean the same thing—-but I can't blame said coworker for thinking they did, because the difference between the two is subtle and probably won't come up unless you've done a fair amount of fiddling with type classes. To that end, I want to show an example where those two differ, and then explain why.

The Example

Let's say we have this (more than a little contrived) multi-parameter type class (which will require the MultiParamTypeclasses extension):

class PairOf a b where
  thePair :: (a, b)

I then define an instance that looks like this (which will require the FlexibleInstances extension):

instance Monoid a => PairOf a a where
  thePair = (mempty, mempty)

So far, so good! Now let's try a particular use of thePair in a (probably even more contrived) definition:

obtuseMempty :: Monoid t => t
obtuseMempty = fst thePair

What do I expect to happen in this code snippet? I would hope that obtuseMempty ends up being the same as mempty. In particular, I want thePair to resolve to the instance I defined above, and consequently evaluate to (mempty, mempty), and then, fst (mempty, mempty) == mempty. What actually happens when I compile this?

• Could not deduce (PairOf a b0) arising from a use of ‘thePair’ from the context: Monoid a bound by the type signature for: obtuseMempty :: Monoid a => a at sample.hs:11:1-29 The type variable ‘b0’ is ambiguous Relevant bindings include obtuseMempty :: a (bound at sample.hs:12:1) These potential instance exist: instance Monoid a => PairOf a a — Defined at sample.hs:8:10 • In the first argument of ‘fst’, namely ‘thePair’ In the expression: fst thePair In an equation for ‘obtuseMempty’: obtuseMempty = fst thePair

Well, that's not what I had wanted, but I guess it makes sense: thePair has to be a pair (because of the use of fst), but since we never use the second element in thePair, there's no reason for GHC to believe that it's the same type as the first. However, let's try tweaking the definition a bit: instead of PairOf a a, let's define it as PairOf a b and then include a constraint that keeps a and b equal (which will require either GADTs or TypeFamilies enabled):

instance (Monoid a, a ~ b) => PairOf a b where
  thePair = (mempty, mempty)

If we try compiling obtuseMempty with this definition, it works without any errors! But why does one work while the other doesn't? What's the difference between the two? The answer has to do with a subtlety of how type class resolution works, a subtlety that can be hard to observe right until it stares you in the face.

How Type Class Resolution Works

When GHC searches for an appropriate instance of a type class, it has to check against all the instances you've defined and find one that “matches” your use of the type class. This is pretty easy when you define instances for a basic type like Int or Bool. For example, using the following (pretty useless) type class:

class MyClass t where
  myValue :: t

instance MyClass Int where myValue = 0
instance MyClass Bool where myValue = True

If I use myValue in a context where it's being interpreted as Int, then Haskell will search through the available instances and find our declaration of MyClass Int. That's simple enough! Things get a bit more complicated when we add types that include type parameters. For example, this is a definition of MyClass for pairs of values:

instance (MyClass a, MyClass b) => MyClass (a, b) where
  myValue = (myValue, myValue)

As a point of vocabulary, everything before the => in this definition is called the context, and everything after it is called the head. So now, if I use myValue in a context where it's being interpreted as (Int, Bool), then GHC will find the matching instance MyClass (a, b), and then in turn tries to search for two other instances: one for MyClass Int and another for MyClass Bool.

Notice the precise way I phrased that, because this is where the basic intuition around type class instances can diverge from the actual implementation: it looks like the instance definition is saying, “If we have an instance for MyClass a and an instance for MyClass b, then we can also have an instance for MyClass (a, b).” This is a reasonable intuition, but it's precisely backwards from what Haskell is actually doing. What happens instead is that, when it sees myValue being used as a pair, GHC will first select the instance MyClass (a, b) without having even examined the constraints in the context. Only after it's already committed to using the instance MyClass (a, b) will it then examine the context and try to satisfy the MyClass a and MyClass b constraints. Or, to say it in a more concise but jargon-heavy way, it first matches the head, and once it has done so, attempts to satisfy the context.

Consider what happens if write the following code without having defined an instance of the form MyClass ():

blah :: (Int, ())
blah = myValue

The precise error GHC gives us is: “No instance for (MyClass ()) arising from a use of myVal.” GHC has already settled on the MyClass (a, b) instance, has found a satisfying instance for MyClass Int, but then cannot find an instance for MyClass ().

In this case, making that distinction seems a little bit pedantic. In code like this, it amounts to simply an implementation detail! It shouldn't really matter what order GHC is using underneath the surface: either way, the problem is that we don't have an instance for MyClass (), and as long as GHC reports that error to us in some way, it doesn't matter whether it first tries to satify the context before committing to to MyClass (a, b), or if it commits first and then tries to satisfy the context: we'll run into the same problem either way! But knowing the precise way GHC tries to instantiate type classes can be very useful in other contexts.

Repeated Types in Instance Heads

Let's look at our first problematic PairOf instance:

instance Monoid a => PairOf a a where
  thePair = (mempty, mempty)

Remember: GHC has to match the instance head first, and after that it solves the remaining constraints from the context! So, in the definition of obtuseMempty, what is the inferred type of the use of thePair?

obtuseMempty :: Monoid t => t
obtuseMempty = fst thePair

It should be obvious, but for good measure, let's replace thePair with a hole and find out what type GHC is assigning based on the surrounding context:

• Found hole: _ :: (a, b0) Where: ‘a’ is a rigid type variable bound by the type signature for: obtuseMempty :: forall a. Monoid a => a at sample.hs:11:17 ‘b0’ is an ambiguous type variable • In the first argument of ‘fst’, namely ‘_’ In the expression: fst _ In an equation for ‘obtuseMempty’: obtuseMempty = fst _

So GHC needs to find an instance of the form MyPair t b0. Let's look at our instances: do we have one that has a matching head? ...well, no, we only have MyPair a a.

“But wait!” you say. “We don't do anything with the second part of the pair, so why can't GHC choose MyPair a a as a valid instance?” But GHC can't read your mind, and there's nothing in your program to indicate that the type variables a and b0 are supposed to be the same. As soon as you somehow indicate that, GHC will comply and find your MyPair a a instance:

evenMoreObtuseMempty :: Monoid t => t
evenMoreObtuseMempty = let p = thePair in (fst p `mappend` snd p)

In this definition, it's clear that thePair is supposed to have two fields of the same type, because we're clearly using mappend to combine them. But is there a way of making it work even if we don't give GHC that extra nudge at the use site?

Type Equality to the Rescue

Let's move on to the second MyPair instance I described above:

instance (Monoid a, a ~ b) => PairOf a b where
  thePair = (mempty, mempty)

Using typical informal reasoning, it seems like this should be identical to the other instance definition: “It's an instance where both parameters are the same type, and that type needs to be a Monoid”. But remember how GHC chooses instances: first by matching the head, then by elaborating the constraints. And this definition is different in an important way: the fact that the two type parameters are the same type is no longer a feature of the head, but rather a feature of the context! So when we revisit our definition of obtuseMempty with this new definition, GHC behaves differently:

obtuseMempty :: Monoid t => t
obtuseMempty = fst thePair

The value thePair in this context still has the inferred type PairOf t b0 => (t, b0), but now we have an instance for PairOf a b, which means GHC can unify those and select the instance we want! And now that it has chosen that instance, GHC can take the constraints associated with that instance and try to solve them: the expression thePair now has the inferred type (Monoid t, t ~ b0) => (t, b0), which GHC can solve as: (Monoid t) => (t, t). After that, our function type-checks successfully!

So What's The Lesson?

A rough intuition is that you can think of type equality in code like this as helping you propagate the fact that types are equal in some contexts. In the examples above, we as programmers intended the two fields of thePair should have the same type, but the first definition—-the MyPair a a one—-meant we could only use myPair when GHC already knew those types were equal. By moving the type equality to the context, we can use myPair in places where the two types aren't already known to be distinct and introduce that fact. This isn't the only use of type equality—-type equality is very important in the context of type families, for example—-but it's nevertheless an important use.

GHC type class resolution is really very straightforward, even in the face of extensions like the ones we enabled in this post. In fact, part of the problem is that it's sometimes tempting to imagine GHC is doing something more clever than it actually is! Methodically stepping through the way GHC processes your code can really help understand situations like these, where intial intuitions sometimes lead you down the wrong path.

Markov chains are reasonably common on the internet these days: they're often used as way of generating random data that looks similar—-at least, in a sense—-to some existing data set. A lot of the great examples of Markov chains come from combining two very different data sets and building a single Markov model from them:

• King James Programming creates mashed-up versions of the King James Bible and the classic programming text The Structure And Interpretation of Computer Programs.
• At The Modules of Madness creates mashed-up versions of the documentation for the Puppet tool and the eldritch horror novels of H.P. Lovecraft.
• Erowid Recruiter creates mashed-up versions of recruiter emails from programming companies and people's accounts of taking various illicit substances.

I also have my own Markov bot, which right now is just trained on my own tweets¹, and I might eventually decide to add my prose writing as a secondary source of data. It produces a few wonderful tweets and a whole lot of nonsensical crap.

I've just added a little feature which helps to visualize what's going on under the surface, so I wanted to explain how Markov chains work at a high level first, and then show how @guwan_aisamanra now visualizes the underlying mechanisms at work.

What is a Markov Chain?

There are various ways of thinking about Markov chains, but underlying them is the kind of abstract notion of steps in a sequence. You can think of these steps as being actions over time, or as words in a sentence, or as abstract symbols in any kind of sequence of symbols. It doesn't matter what: just a bunch of things one after another, in time or in space.

In many sequences like these, the next step might be random, but the odds of choosing a particular next step are often related in some way to the steps that came before. Let's take a simple contrived example: the capricious chef at your local cafeteria. Every day, the chef chooses one of three meal options: tacos, pasta, or soup. The chef chooses the next meal randomly, but is not allowed to repeat the same meal two days in a row. The chef is also inordinately fond of tacos² and is twice as likely to pick tacos as any other option, but still won't make tacos two days in a row. A possible sequence of meal choices might go: “tacos, pasta, tacos, soup, pasta, tacos, pasta, tacos...”

This example has a very particular property where the choice of each step depends only on the previous step, but not any of the steps before the last one. If last lunch was tacos, then we have roughly equal chances of choosing pasta or soup as the next lunch because the chef has no preference between the two. On the other hand, if the last lunch was pasta or soup, then we have a two-thirds chance of choosing tacos as the next lunch, and one-third chance of choosing soup or pasta respectively, because the chef is allowed to make tacos and is more likely to make them than a different lunch. We can write a table that conveys the odds of a given meal choice given yesterday's meal choice:

yesterday's lunch today's lunch probability

---

tacos pasta ½ tacos soup ½ pasta tacos ⅔ pasta soup ⅓ soup tacos ⅔ soup pasta ⅓

The mathematical way of saying that the probability of a given lunch choice doesn't depend on any history of lunches except for the most recent one is that our sequence of lunches has the Markov property.

If some sequence of things—-words, mathematical objects, lunches, whatever—-has the Markov property, then we can build up a mathematical model of the underlying process. One convenient way of visualizing this model is as a graph with directed edges: each step is a node, and the directed edges between nodes are tagged with the probability that the steps of picking that step next. Consequently, the graph of the lunche pattern I described would look like this:

We can come up with a probably sequence of lunches by moving randomly starting in one state, and then following the edges from one state to another, choosing from our next edge according to the provided probabilities.

Implementing Markov Models

In software, we can implement a directed graph as a table that maps steps to a set of possible next steps, where the possible next steps are randomly chosen according to some set of probabilities. For simplicity in this implementation, I'm going to treat the set of next steps as a multiset from which we can choose any element with equal probability: if we choose at random from the multiset {tacos, tacos, pasta}, then we'll get tacos two-thirds of the time and pasta one-third of the time. This is a terrible representation in practice—-for certain situations, it can use a ridiculously wasteful amount of space—-but it makes the code in this blog post short and easy!

Let's implement a basic, inefficient-but-working Python version of a Markov model! We can represent our model in Python using a plain dictionary, with strings as our step names, and lists as our possible next steps:

model = {
  'tacos': ['pasta', 'soup'],
  # both of the following have double the chance
  # of choosing tacos
  'pasta': ['tacos', 'tacos', 'soup'],
  'soup':  ['tacos', 'tacos', 'pasta']
}

If we want to generate a sequence of lunches with a particular length, we can do so by starting with a random starting lunch, and then choosing our next lunch randomly according to the set of possible “next lunches” provided by the model:

import random

def generate_sequence(model, length=10):
    # choose our initial state randomly
    state = random.choice(model.keys())
    # our output sequence starts empty
    output = []

    # we loop equal to the desired length
    for _ in range(length):
        # each time, we add the current state
        # to the sequence
        output.append(state)
        # and choose a new state randomly from
        # the set of possible next states
        state = random.choice(model[state])

    # once we've gotten as many as we want, we
    # can return our sequence
    return output

If we run this model several times, we'll get various random sequences that conform to the patterns we'd expect:

>>> generate_sequence(model, length=5)
['pasta', 'tacos', 'soup', 'tacos', 'soup']
>>> generate_sequence(model, length=5)
['soup', 'tacos', 'soup', 'tacos', 'soup']
>>> generate_sequence(model, length=5)
['tacos', 'pasta', 'soup', 'tacos', 'pasta']
>>> generate_sequence(model, length=5)
['tacos', 'soup', 'tacos', 'soup', 'pasta']

In the example we've been using, our model was based on perfect mathematical knowledge of the underlying problem domain: we know exactly the logic the chef uses to determine the next lunch. However, in most cases, we don't have that simple knowledge, so instead we want to calculate a model based on some set of existing observed data. Using the same representation of Markov model, we can take a sequence of any kind of things and build a model out of it by looking at each pair of elements in the sequence, and building a model accordingly³:

def build_model(sequence):
    # our empty model knows nothing about anything
    model = {}

    # walking along the sequence, taking each step
    # as well as its subsequent step...
    for step, next_step in zip(sequence, sequence[1:]):

        # make sure that step has an entry in our model
        # data structure:
        if step not in model:
            model[step] = []

        # add the next_step to the list of possible next
        # steps
        model[step].append(next_step)

    return model

Now we can build a Markov model from a sequence of data even if we don't know what probabilistic relationships hold in that data set. This lets us take data we've found “in the wild” and build a model that resembles the raw data! Well, in a limited sense, as we'll see.

Markov Models of Non-Markov Sequences

It turns out that English text—-both on the level of individual letters, and on the level of sentences—-doesn't have the Markov property, because the choice of “next word” depends on a lot more than just the previous word: grammatical structures, semantic context, and so forth. Building and using a Markov mover from raw English text—-in the examples below, I'm using the Project Gutenberg text of Alice in Wonderland, stripped of everything but spaces and alphabetic characters turned lowercase—-produces some nonsense that's English-like from a distance but still mostly gibberish:

>>> alice = open('alice-in-wonderland.txt').read().lower()
>>> model = build_model([ch for ch in alice if ch.isalpha() or ch == ' '])
>>> ''.join(generate_sequence(model))
'xpr yoube '
>>> ''.join(generate_sequence(model))
'be che sof'
>>> ''.join(generate_sequence(model))
'ver athean'
>>> ''.join(generate_sequence(model))
'k wanigroo'
>>> ''.join(generate_sequence(model))
'jeado sshe'
>>> ''.join(generate_sequence(model))
'f tond mpo'

Similarly, a Markov chain run over the sequence of words in the text, rather than the characters, produces strings of English words which lack grammar or real sense:

>>> model = build_model(alice.split())
>>> ' '.join(generate_sequence(model))
'bat, and said alice, she wandered about in an opportunity'
>>> ' '.join(generate_sequence(model))
'coaxing tone, going to leave it had lost something; and'
>>> ' '.join(generate_sequence(model))
'oneself speak--and they are removed. of it; and then the'

Why does it produce such terrible nonsense? Well, because Markov chains have no memory! Each pair of words in sequence is sensible, but higher-level relationships like sentence structure don't get captured in the model, because they rely on larger amounts of context. Let's take a closer look at a four-word sequence generated by the Alice in Wonderland chain:

escape; so much evidence

We can look at as being composed of three overlapping sequential pairs of words, where each ordered pair of words must have appeared at least once in the source text, or else the model would not have provided a path between them. The first pair is escape; so, and it turns out that this word pair appears only once in the source text, in Chapter IV:

This seemed to Alice a good opportunity for making her escape; so she set off at once...

The pair so much appears at least nine times—-it is a very likely pair of words in English more generally, so this makes sense! I'll choose my favorite sentence in which that pairs appears, just as an arbitrary example:

'Curiouser and curiouser!' cried Alice (she was so much surprised, that for the moment she quite forgot how to speak good English)...

And the word pair much evidence appears only once, in Chapter XI:

Alice watched the White Rabbit as he fumbled over the list, feeling very curious to see what the next witness would be like, '—for they haven't got much evidence YET,' she said to herself.

In each case, training the Markov model produced the knowledge that these words appear in sequence somewhere in the source text, so it was okay for them to appear together in the output:

making her ESCAPE; SO she set off at once, and ran till s
ied alice (she was SO MUCH surprised, that for the moment
-for they haven't got MUCH EVIDENCE yet,' she said to her
           ESCAPE; SO MUCH EVIDENCE

But it's not really a full sentence, even if it seems more realistic than some of the others produced. Because we're choosing each word only based on the previous word, the model doesn't know about things like clauses or verbs or sentences, just word-pair frequency. I our training model contains a sentence like

behold the dishwasher, the greatest invention of mankind

then it might learn that it's okay to follow “the” with “dishwasher,” and also to follow “dishwasher,” with “the”, and produce a nonsensical sequence like this:

the dishwasher, the dishwasher, the dishwasher, the dishwasher,

(There's an even sillier example that arose from my own Markov bot: I once tweeted something that included the phrase “stabby stabby”, and consequently my Markov model learned that it was perfectly fine to follow the word “stabby” with “stabby”.)

Visualizing Markov Output Directly

It's sometimes very interesting and illustrative to compare the output of a Markov chain with the input provided to that Markov chain, because you start to see the places where the model “learned” particular patterns. To draw an example from my own bot: earlier today it tweeted [a short phrase]():

bad painter? it's happened in it

My bot is programmed to only start with words which appear at the start of a tweet elsewhere, so it chose to start with the word bad because it came at the start of this old tweet:

Bad idea: double-shot of espresso added to drip coffee (a “redeye”). OTOH now I can see infinity. So I got that going for me. Which is nice.

The word bad also appears in this more recent tweet, where it borrowed several pairs of words in sequence:

Did you know that in addition to being a bad programmer and a bad-opinion-haver, I am also a bad painter? It's true!

The word it's also appears in this tweet where it is followed by the word happened:

It usually happens with weird dream-like books. It's happened before with Dunsany and MacDonald. Last night, it was an R. A. Lafferty novel.

And the word happened also appears in this tweet, followed by a few more words:

Last time I had a fever, I watched all of the Tron cartoon. A+++ would feverishly watch again. ...no idea what happened in it.

In this case, this isn't just a reconstruction of what might have influenced the model, like in the Alice example above. To facilitate exactly this kind of introspection of Markov chain output, I've modified my own Markov bot to consistently record not just which words it's selecting, but also keep track of where it learned of a relationship between two words. That data is presented in a human-readable form on a new web page generated for each tweet and every new tweet generated will be included on a chronological index page.

A Markov model is an almost embarassingly simple example of machine learning, but it's a good, approachable example to start with—-and is also a great object-lesson in the way that machine learning can only picks up on trends that appear in its training data, and the way that the model might not be nuanced enough to pick up on every kind of pattern.

This is a question posed by Aaron Levin on Reddit:

In WAI, Application has the type Request -> (Response -> IO ResponseReceived) -> IO ResponseReceived. There is a note about how historically this was Request -> ResourceT IO Response. There is the following note on Hackage about this change:

Note that, since WAI 3.0, this type is structured in continuation passing style to allow for proper safe resource handling. This was handled in the past via other means (e.g., ResourceT).

A naive implementation might have type Application = Request -> IO Response. I would assume one could still handle appropriate resource cleanup (both on the client side and on the Wai/warp side) in this naive implementation, but I'm assuming I'm wrong in thinking that. So:

1. Why is Application defined in CPS style?
2. Is there an example of how resources cannot be cleaned up appropriately using a naive implementation above?
3. Are there other reasons for the CPS style? (E.g. allows for more efficiency as network resources can be freed while your handler is running)

Like my last post, this is a piece of folklore that's been described in papers, mailing lists, &c, but I don't know of a single resource to point people to, so I'll explain it here.

I'm gonna explain some preliminary details about laziness, the trace function, and the bracket function; if you're already familiar with these, go ahead and skip to the section A Naïve Application Type. Alternately, if you want to puzzle it out on your own, you can skip this blog post entirely try running the code in this gist and figure out why you get the output you do—-all the code examples in this post are modified versions of the code that appears in that gist.

Some Preliminary Explanations

A big part of this post involves the fact that Haskell is lazy: when we write something in Haskell, it won't be evaluated until it's absolutely necessary that it be evaluated—-which might be never! For example, an expression like

>>> let f x y = x in f 5 undefined
5

will happily ignore our use of undefined, as we never actually use it. If we want to make sure that a given expression is evaluated, we need to use it somehow. One way of using a value is to pattern-match on it: in order to pattern-match against a constructor, we need to evaluate it at least enough to know what constructor was used.¹ We can change the example above to pattern-match on the currently unused value:

>>> let f x y = case y of { () -> x } in f 5 undefined
*** Exception: Prelude.undefined

Now, we're pattern-matching on y, which forces it—-that is, evaluating the pattern-match causes y to be evaluated before it can determine whether or not it matches the pattern, which means we evaluate undefined and get a runtime error.

In general—-with the exception of code that loops forever, or inherently unsafe values like undefined—-laziness should be a detail we barely notice! In pure code that doesn't loop forever, evaluation order doesn't matter at all, and imperative code in Haskell uses monads like IO. Because each step in a monad has to be evaluated before the next step can proceed, those computations appear to be strict, and computations that aren't in a monad generally don't have observable side-effects that we can use to peek at the exact process Haskell is using to evaluate them.

However, Haskell has a few features we can use to peek into what's going on under the surface. One of them is the trace function, found in Debug.Trace, which has the signature

trace :: String -> a -> a

This takes a string and any other value, and will print the string as soon as the value is forced—-not before, not after. That makes it of sometimes questionable utility for debugging, as it's possible that our calls to trace won't run in the order we expect, or even won't run at all:

>>> let f x y = x in f 5 (trace "Hello!" undefined)
5

But because trace will print exactly when its result is needed, we can use it to peek into how Haskell chooses to evaluate our code.

Bracketing for Resources

The module Control.Exception.Base exports a function called bracket:

bracket :: IO a -> (a -> IO b) -> (a -> IO c) -> IO c

This function is used for managing resources that we need to clean up, like file handles or large pieces of data we don't want to keep in memory. The first argument is an IO computation that produces a resource, the second one is the cleanup function for that resource, and the third one is a function that uses that resource to produce a value prior to cleanup:

main :: IO ()
main = bracket
  (openFile "tmp.txt" ReadMode)  -- opening a resource: here, a file
  hClose                         -- closing the resource
  (\ handle -> do                -- what to do with the resource
       contents <- hGetContents handle
       putStrLn contents)

The common function withFile is implemented straightforwardly in terms of bracket almost exactly like I used it above. The major utility of bracket is that it knows how to correctly handle exceptions that occur while running computations: if an exception gets raised while the resource is being used, it will nevertheless ensure that the resource gets closed appropriately.

A Naïve Application Type

Let's try writing a toy version of WAI that doesn't actually do anything. We're going to pretend that we're writing some kind of server where some responses might depend on scarce resources, so we want to clean up those resource as soon as we possibly can.

Let's start with importing the functions above and defining some dummy types:

import Control.Exception.Base (bracket)
import Debug.Trace (trace)

-- Our dummy requests and responses
data Request = Request
data Response = Response

-- Our dummy resource
data SomeResource = SomeResource

-- Our naive @App@ type
type App = Request -> IO Response

Let's write our App handler first. Because we're trying to mimic a real application, we pattern-match on the Response value to force Haskell to evaluate it before returning:

runApp :: App -> IO ()
runApp app = do
  response <- app Request
  case response of
    Response -> putStrLn "Sending response"

Now, let's create an App that uses some “resource”. In this case, I'm going to fake it as well. Additionally, I'm going to include a call to trace so that we can be sure of when our Response value actually gets evaluated:

myApp :: App
myApp request = bracket createResource destroyResource respond
  where createResource = do
          putStrLn "Creating resource"
          return SomeResource
        destroyResource _ = do
          putStrLn "Destroying resource"
        respond SomeResource = do
          return (trace "EVALUATING RESPONSE" Response)

And now let's wrap this all up:

main :: IO ()
main = runApp myApp

When I run this program on my machine here's what I get:

$ runhaskell myapp.hs Creating resource Destroying resource EVALUATING RESPONSE Sending response

What does this mean? Well, this means that we end up destroying the resource we are trying to use even before the response gets constructed. That's not good! In this case, the resource is just a dummy value, but if it were instead, say, a file handle, then this program might close the file handle before we ever tried to read from it!²

But we're using bracket and everything! That should mean that the action we're passing to bracket—-the respond function we defined up above—-should run before the resource gets destroyed! Shouldn't it?

As a matter of fact, it is. The IO action is getting run, and the IO steps are getting evaluated eagerly. If we rewrite the myApp function slightly to insert a print statement there

myApp' :: App
myApp' request = bracket createResource destroyResource respond
  where createResource = do
          putStrLn "Creating resource"
          return SomeResource
        destroyResource _ = do
          putStrLn "Destroying resource"
        respond SomeResource = do
          putStrLn "Responding to request" -- A new print statement
          return (trace "EVALUATING RESPONSE" Response)

and then run it again, we'll see that the respond function is getting properly bracketed between resource creation and destruction:

$ runhaskell myapp.hs Creating resource Responding to request Destroying resource EVALUATING RESPONSE Sending response

The specific problem is that while IO steps are evaluated eagerly, the values that get returned are subject to the normal rules of laziness: they aren't forced until we use them. In this case, we don't actually force the Response value until the case-expression in runApp, which doesn't happen until after the entire myApp function—-bracket and all—-has finished running.

So the bigger problem is that, while bracket can ensure that IO actions are properly bookended with resource-related code, it can't make the same guarantees with respect to the values inside it. We need some way of forcing the value before the cleanup code gets run. We can rewrite myApp to do this:

myStricterApp :: App
myStricterApp request = bracket createResource destroyResource respond
  where createResource = do
          putStrLn "Creating resource"
          return SomeResource
        destroyResource _ = do
          putStrLn "Destroying resource"
        respond SomeResource = do
          putStrLn "Responding to request" -- A new print statement
          let response = trace "EVALUATING RESPONSE" Response
          case response of  -- pattern-match to force evaluation
            Response -> return response

This produces the output we want:

$ runhaskell myapp.hs Creating resource Responding to request EVALUATING RESPONSE Destroying resource Sending response

But this has a lot of drawbacks: it's ugly, it inserts apparently extraneous case statements, and I've papered over the fact that, if we had a more complicated data structure, we'd need to force evaluation of the entire thing, not just the outermost structure. But even worse, it's not a general solution: WAI is a library that exports the equivalent of runApp and expects users to write the equivalent of myApp, which means we'd be forcing every single user to remember to force their Response values. If a user forgets to insert the ugly and opaque code, then their program might start crashing or—-even worse—-running but with nonsensical results. What we want is some way of ensuring that any App must force its Response before cleaning up any resources.

CPS To The Rescue

The core idea of continuation-passing is that a continuation is a function that represents “what to do next”: a continuation is a callback function that expects the result of a previous computation as argument. Let's rewrite our program but with an App type that looks like the CPS-ey type WAI actually uses:

-- Our modified @App@ type
type App = Request -> (Response -> IO ()) -> IO ()

Now, our App takes two arguments—-the Request, as before, as well as a function that takes a Response and produces an IO action. The logic of “sending” the response now gets moved into the callback function we pass to the App:

runApp :: App -> IO ()
runApp app =
  app Request
      (\ response -> case response of
           Response -> putStrLn "Sending response")

Our implementation of myApp is almost the same, except we take an extra callback parameter, and instead of returning our Response, we pass it to that callback:

myApp :: App
myApp request cb = bracket createResource destroyResource respond
  where createResource = do
          putStrLn "Creating resource"
          return SomeResource
        destroyResource _ = do
          putStrLn "Destroying resource"
        respond SomeResource = do
          cb (trace "EVALUATING RESPONSE" Response)

If I run this version of the program, I get this output:

$ runhaskell myapp.hs Creating resource EVALUATING RESPONSE Sending response Destroying resource

This is much better! This ensures that the resource outlives the Response, and because now the callback is responsible for forcing the Response, it can guarantee that it gets done. This lets us ensure that propery of any App! This is something we couldn't ensure with the previous one, because it would have required some way of reaching “inside” the App to force the return value. By having a callback that the user has to call, we can force it ourselves without having to hope that the user does!

...well, except there's that remaining little issue: using the implementation above, the user doesn't have to call the callback, so we could write an App that produces no Response at all:

myBadApp :: App
myBadApp _ _ = return ()

We can fix this by creating a new type—-WAI calls it ResponseReceived—-and hiding every way to construct it except using the callback. That way, the user has to use the callback at least once in order to get a ResponseReceived value, which they can return from their App. (We will have the problem that we can call the callback more than once: we could keep working on solutions, but we'd have to move to more complicated solutions and WAI ends up suggesting that you just not do that.)

So this is why the CPS style is indeed necessary for resource management here: it's not enough to use bracket, you have to use bracket and have the appropriate amount of strictness³, and the CPS style helps you achieve that.

The 'WriterT space leak' is something that gets talked about a lot in Haskell folklore. Here's a short explanation of what that means.

Defining WriterT

The Writer monad represents computations with “extra output”: produced data, logging messages, and so forth. That “extra output” has some constraints: we need to know what it means to have an “empty” piece of that data (so we can construct values with no extra output) and we need to know how to combine or append the “extra output” (so we can run two distinct computations and combine them appropriately.) We can get those properties in Haskell by ensuring that the “extra output” parameter has a Monoid constraint.

The WriterT transformer is defined like this:

newtype WriterT w m a =
  WriterT { runWriterT :: m (a, w) }

which is to say: it wraps an underlying monad m, which represents a computation that produces a pair of a (the result of our computation) and w (the “extra output” parameter). The Monad instance (I'm eliding the Functor and Applicative instances) looks like this:

instance (Monoid w, Monad m) => Monad (WriterT w m) where
  -- return the provided value, filling in the "extra output"
  -- with an "mempty" value.
  return x = WriterT $ return (x, mempty)

  -- to chain two WriterT computations together...
  m >>= f = WriterT $ do

    -- A: run the first computation, fetching its result
    -- and extra output
    (x, w)  <- runWriterT m

    -- B: produce the second computation by applying f to the
    -- result from the first computation, and then run it,
    -- fetching its result and extra output
    (y, w') <- runWriterT (f x)

    -- C: return the final result with the pieces of
    -- extra output from each computation combined together.
    return (y, w `mappend` w')

The last thing we need is the tell operation, which is the function we use to create our “extra output”:

tell :: (Monoid w, Monad m) => w -> WriterT w m ()
tell o = WriterT $ return ((), o)

A simple contrivted WriterT computation looks like this:

sample :: WriterT (Sum Int) Identity ()
sample = do
  tell (Sum 2)
  tell (Sum 3)
  tell (Sum 4)
  return ()

running this produces a return value of () as well as “extra output” equivalent to Sum 2 <> Sum 3 <> Sum 4 === Sum (2 + 3 + 4) === Sum 9. Sure enough:

>>> runIdentity $ runWriterT sample
((), Sum 9)

In Space Leaks, No-One Can Hear You Scream

Well, what's the problem? Let's look more closely at the definition of >>=. In particular, notice that in order to start evaluating the call to mappend in step C, we need to have the output from both steps A and B. ...except step B represents evaluating the entire rest of the computation, including an arbitrarily large number of other calls to >>=.

If we started evaluating the first call to >>= in runWriterT sample, then step A represents evaluating tell (Sum 2), and step B represents evaluating tell (Sum 3) >>= (\_ -> tell (Sum 4) >>= (\_ -> return ())). We get our output value w from the first one, and then we have to hold on to it while running the entire second computation in order to get the second extra output value w' before we can mappend them in step C. This problem appears with every call to >>=: we have to finish the entire subsequent chain of binds before we get the extra output to combine.

This is especially silly for sample, where I've chosen to use Sum Int as the extra output. It's just an accumulator! But in order to actually start adding those numbers together, we have to go through the entire chain of binds and produce each number first, each of which has to be kept around until we get to the final return, and only then can we go back and start adding the numbers we've generated together. In this case, it's not gonna kill our heap, but consider a computation like

largerSample :: WriterT (Sum Int) Identity ()
largerSample = sequence [ tell (Sum 1) | _ <- enumTo 1000000 ]

This computation will contain 1000000 calls to >>=, which means we will generate 1000000 instances of the number 1 first, and only then can it start adding them together. This can't be changed with strictness annotations or modifications to evaluation stategy: we'll need to rearrange the way that data depends on other data.

Alleviating the Space Leak

The problem solution is described in short by Gabriel Gonzalez here and here on the mailing lists, but I'll explain the same thing slightly more verbosely:

What we really want is for the call to mappend to happen earlier, which means moving around the way our intermediate values depend on each other.¹ We've written our WriterT so that the “extra output” is always returned from a computation, and never passed to a computation: that means a given computation doesn't “know” about the intermediate value of that value, and we can only run our mappend operation after we've finished it. Let's try writing an alternate WriterishT monad that differs by also taking the “extra output” from previous steps:

newtype WriterishT w m a =
  WriterishT { runWriterishT :: w -> m (a, w) }

The w on the left side of the arrow represents the intermediate value of the “extra output” that comes from previous steps. We can move the mappend step from the implementation of >>= into the tell function, which now combines the new value being “told” with the previous values:

tellish :: (Monoid w, Monad m) => w -> WriterishT w m ()
tellish w = WriterishT $ \w' -> return ((), w <> w')

The implementation of return used to return mempty, but now it's taking an intermediate value it might need to combine with the 'new state', so it would look like this:

return x = WriterishT $ \w -> (x, w <> mempty)

Luckily, the Monoid laws tell us that w <> mempty === w, so we can simplify that definition down a fair amount. This ends up removing all mention of the Monoidal nature of our data in the Monad instance, so we can omit the Monoid w constraint:

instance (Monad m) => Monad (WriterishT w m) where
  -- the motivation for this implementation is explained
  -- up above...
  return x = WriterishT $ \w -> (x, w)

  -- The bind instance looks pretty similar, but again, we
  -- need to take the current state of our accumulator:
  m >>= f = WriterishT $ \w -> do
    -- A: we pass that on to the first computation...
    (x, w')  <- runWriterishT m w
    -- B: and pass that on to the second computation...
    (y, w'') <- runWriterishT (f x) w'
    -- C: and return just the second state, because the
    -- call to 'mappend' was taken care of inside one
    -- of these.
    return (y, w'')

Now, the call to mappend have all the data they need as soon as tellish happens. Step C only relies on the “extra output” from B, which itself only relies on the “extra output” from A. That means that we've already run mappend before step B, and can throw away the older intermediate value.

...this is a little bit dishonest, though: the type that we've made is significantly more powerful than just a WriterT. One feature of WriterT is that there's no way for a computation to peek at or rely on the “extra output” from previous steps. However, if we aren't careful about the interface to our WriterishT monad—-in particular, if we don't hide the constructor—-a user could write code like this

getCurrentOutput :: WriterishT w m w
getCurrentOutput = WriterishT $ \w -> return (w, w)

poorlyBehaved :: WriterishT (Sum Int) Identity String
poorlyBehaved = do
  Sum n <- getCurrentOutput
  if n == 0
    then return "zero"
    else return "nonzero"

which would be impossible in WriterT! (If you can't see why, it's worth trying to write it and seeing what walls you come up against.) This is because, in point of fact, what I've been calling WriterishT is literally just StateT by a different name! That makes it much more powerful than WriterT, but accordingly it removes some of the guarantees you get by using a WriterT, as well.

So in summary, the WriterishT or StateT can alleviate the space-leak problems with WriterT, but at the cost of some of the desirable properties of WriterT. In most cases, the space leaks from WriterT won't turn out to be a huge problem, but it's good to know what's happening and why it comes about!

One current pain point for certain Haskell programs is Cabal's data-files feature. This feature is a little bit awkward and weird: it involves depending on a generated file but also filling in a default implementation for that file, and there are some obscure and unclear edge cases in its use. One difficult edge case is that, while most uses of data files are in applications, it's nonetheless possible for libraries to depend on data files, in which case it's very difficult to induce Cabal to produce final relocatable bundles that contain both executables and the data files on which they depend.

I was musing on a hypothetical future way of solving this problem: once the lightweight module system Backpack is fully implemented in Haskell, we could build a data-files-like mechanism in a more convenient way by modifying the current design to use module-level mixins. The rest of this post will sketch out what that design might look like.

I should stress that I'm describing a possible solution, and not the solution. I'm by no means indicating that this is the best way of solving present problems with data files, and I have absolutely no indication that anyone else would want to solve the problem like this. That said, I think this is an interesting and motivated design, and I'd be happy to discuss its strengths and weaknesses, as well as other possible design choices that address the same issues.

Right now, I'm using Edward Yang's blog post A Taste Of Cabalized Backpack as my primary guide to Backpack-in-practice. I don't have a Backpack-enabled GHC and Cabal on hand, and so I haven't actually run any of this: this should right now be treated effectively as pseudocode. I also assume familiarity with Cabal's data files support; if you're in need of an introduction or a refresher, you should read the post Adding Data Files Using Cabal.

An Abstract Signature for Data Files

In our hypothetical Backpack-enabled-data-files-support future, we start by creating a signature that corresponds to the generated Paths_whatever module. To this end, we can create an .hsig file with a declaration like this:

module Dist.DataFiles (getDataFileName) where
  getDataFileName :: FilePath -> IO FilePath

This defines an abstract module called Dist.DataFiles that exposes a single function, getDataFileName, with no actual implementation. We can expose this signature by creating a package, data-files-sig, that exposes only this signature:

    name:               data-files-sig
    version:            1.0
    indefinite:         True
    build-depends:      base
    exposed-signatures: Dist.DataFiles

This would be a standard package—maybe even part of base—that can be consistently and universally relied on by libraries that require some kind of data file support.

Creating A Library With Data Files

Now, let's create a library that needs a data file. In this case, the library will do nothing but read and return the contents of that data file:

module Sample.Library (getSampleFile) where

import Dist.DataFiles (getDataFileName)

getSampleFile :: IO String
getSampleFile = getDataFileName "sample-file" >>= readFile

Now we need to create a corresponding .cabal file for this library. Because we're using Dist.DataFiles, we need to import that signature from the data-files-sig module. Importantly, we still don't have an implementation for getDataFileName. Because of that, our package is still abstract, or in Backpack-speak, indefinite:

    name:            sample-library
    indefinite:      True
    build-depends:   base, data-files-sig
    exposed-modules: Sample.Library

Depending On A Library With Data Files

In order to write an application that uses sample-library, we need to give it a module that's a concrete implementation of the Dist.DataFiles signature. In this case, let's create an implementation manually as part of our application.

First, let's write a small application that uses sample-library:

module Main where

import Sample.Library (getSampleFile)

main :: IO ()
main = getSampleFile >>= putStrLn

We still don't have that concrete implementation for getDataFileName, though, so let's write a simple module that exports the same name with the same type:

module MyDataFilesImpl (getDataFileName) where

import System.FilePath ((</>))

getDataFileName :: FilePath -> IO FilePath
getDataFileName path = pure
  ("/opt/sample-application" </> path)

Now, when we write our .cabal file for this application, we also need to specify we want to use MyDataFilesImpl as the concrete implementation of Dist.DataFiles for sample-library. That means our .cabal file will look like this:

    name: sample-application
    build-depends:
      base,
      filepath,
      sample-library (MyDataFilesImpl as Dist.DataFiles)

Now, all our abstract signatures are filled in, so this application is no longer indefinite, and we as developers have a convenient way of telling sample-library where we want it to look for its data files. In fact, one advantage of this system for data files is that we could import two libraries that both depend on the Dist.DataFiles signature but tell them to look in two different places for their data files, like this:

    name: other-application
    build-depends:
      base,
      lib-one (OneDataFilesImpl as Dist.DataFiles),
      lib-two (AnotherDataFilesImpl as Dist.DataFiles)

If there are reasonable default implementations for Dist.DataFiles, we could also put those on Hackage and reuse them in much the same way.

A Final Sprinkling Of Magic

In this case, I'm still missing a major part of Cabal's data-files support: namely, we want to shunt the responsibility from the developer to Cabal, so that we have support for things like relocatable builds. So in a final bit of handwaving, let's stipulate that our tooling in this hypothetical future has a special case to deal with applications that expose an indefinite Dist.DataFiles signature: Cabal could notice this situation, and fill those signagutres in with sensible implementations based on the commands and configurations we're using.

For example, if my .cabal file for sample-application above didn't supply a concrete implementation for Dist.DataFiles, then a default one could be chosen for development that's equivalent to:

-- as automatically generated by cabal
module Dist.DataFiles (getDataFileName) where

getDataFileName :: FilePath -> IO FilePath
getDataFileName = pure

That is, the application will just look for the file in the current directory.

If the developer started preparing the package for release, and changed the configuration appropriately, then the automatically generated getDataFileName could be modified to reflect that, replacing the automatically generated code with something more like

-- as automatically generated by cabal
module Dist.DataFiles (getDataFileName) where

import System.FilePath ((</>))

getDataFileName :: FilePath -> IO FilePath
getDataFileName path =
  pure ("/usr/share/sample-application" </> path)

This would be admittedly a little bit “magical”, but it would be a small and easy-to-explain bit of magic, and it would have the advantage of affording a kind of flexibility that the current approach to data files lacks.

Is This How It's Actually Gonna Work?

Probably not! Backpack is still a ways out, and this would require opt-in from many parts of the Haskell ecosystem, and the problem it solves could probably also be solved in numerous other ways I haven't considered. But this post describes a point in the design space that I think is at least worth weighing!

I buy a fair number of comic books. Often I buy them as standalone graphic novels or as collected trade paperbacks, but if I really like an ongoing series¹ I'll buy individual issues as they come out.

This poses a problem for me: I'm not collecting them, so I'm not really interested in keeping them in plastic sleeves in special boxes, but I do want to keep them in reasonable, readable condition and have them on-hand and organized. Some people will bind their comics into volumes, which is really cool, but not exactly what I want.

I leaned towards something like a slipcase for some number of issues. Some of these exist, but when I looked they were expensive (around \$20 per case) and kind of boring-looking, so I opted to make my own. I made some prototypes by hand, but I wasn't quite happy with the quality of my worksmanship on them, so: I finally got around to creating one via laser-cutting instead.

The Design

The basic design is obvious: a box, tall and wide enough for a comic issue and deep enough for some number of them. For the prototype, I chose five deep², and did some measurements of a stack of five comics: I had to accomodate a volume of roughly 6.75 in × 10.25 in × 0.375 in. The only bits of the design I wasn't sure about were the edges and the front and back panels. The edges I wanted to have a cut-away tab so one could easily pull the comics out, but I figured I could use a shape that was more interesting and unusual than just a half-circle. The front and back would be bland blank: I considered engraving an image into them, or leaving them blank for later painting, but ended up deciding to cut a window into them so you could see glimpses of the front and back covers of the comics inside. Despite not knowing the exact shapes of either of those features, I went ahead with designing.

The Process

I created the blueprint as a Haskell program using the diagrams package. The code was reasonably straightforward: as I wanted to experiment with the pull-tab shape and the window shape, I represented those as arguments to a function comicBox which drew the rest of the slipcase, allowing me to easily create several variations on the details as I went.

I already decided to use Ponoko to cut the box, so I also included some utility functions that simply colored lines the appropriate color for cutting or scoring according to Ponoko's guidelines—-0x0000ff lines for cutting, and 0x00ff00 for scoring.

The code is actually not all that long:

import Diagrams.Prelude
import Diagrams.Backend.SVG.CmdLine

-- some helpers
toLine :: [(Double, Double)] -> Diagram B
toLine ls = fromOffsets (map r2 ls) # strokeLine

cut :: Diagram B -> Diagram B
cut x = x # lc (sRGB 0.0 0.0 1.0)

crease :: Diagram B -> Diagram B
crease x = x # lc (sRGB 0.0 1.0 0.0)

-- width and height of space for comics
cW, cH :: Double
cW = 6.75
cH = 10.25

-- a slipcase parameterized by a depth, and a window and edge shape
comicBox :: Double -> Diagram B -> Diagram B -> Diagram B
comicBox cD window edge = reflectX fullS ||| spine ||| fullS
  where spine = rect cD cH # explodeTrail
                           # zipWith ($) [crease,cut,crease,cut]
                           # mconcat
        side = (translate (r2(3.375,5.125)) $ (sShape # crease)
                 <> (edge # cut))
                 <> (window # cut)
        sShape = toLine [(-cW,0), (0,-cH), (cW,0)]
        top = toLine [(0,cD), (cW,0), (0,-cD)] # cut # centerXY
        fullS = beside unitY side top === reflectY top

-- The window shape is a bunch of squares, and the tab shape is
-- a kind of anglular \__/ thing.
main :: IO ()
main = mainWith (comicBox 0.375 windowShape edgeShape)
  where windowShape = let row = hsep 0.5 (replicate 3 (square 1))
                      in  centerXY (vsep 0.5 (replicate 4 row))
        edgeShape =
          let offs = [ (0,    -0.35)
                     , (-0.1, -0.1)
                     , (0,    -0.1)
                     , (0.1,  -0.1)
                     , (0,    -0.35)
                     ]
          in toLine offs # scaleX cW # scaleY cH

I decided on a simple array of grid squares for the window shape, and an angular kind of tab shape, which you can see below.

This produced a nice clean image, but not one that fit all the specifications for Ponoko plans—-it needed to be a specific size, and lines for cutting needed to be a specific thickness. Instead of finding the right functions to get my program to emit the correct line thicknesses and image size, I decided to just clean it up in Inkscape and copy it onto the templates for cutting that Ponoko supplied. I might go back and rewrite the code to spit out a valid uploadable image at some point, but it wasn't a priority.

I opted for cardboard as a material: it's not as thick as the chipboard I'd prefer, but it means I could fold (and not have to assemble) the box, and it's relatively cheap. I considered bamboo or some kind of thin wood, but for the first prototype, at least, cardboard seemed like a simpler choice: I can always try other materials later.

I used some of the excess space on the board for an unrelated experiment that involved a lot of engraving, so it was more expensive than it would have been had I simply opted for the cutting and scoring. When I get more made, I won't use that excess space for engraving-heavy things, so the price should be much cheaper.

After cleaning it up the design in Inkscape, I was ready to upload it and wait about a week for it to arrive!

The Result

I'm pretty happy with the final result, which is shown here containing five issues of a comic. I didn't think to take a photo of the raw cardboard sheet before punching it out and gluing it together, but you can easily extrapolate what it must have looked like.

Reflections and Next Steps ==========================

The biggest problem is that the slipcase is too snug—-something I anticipated, but I wanted to see exactly how snug it would be before I scaled up. The next iteration will have some more breathing room, which will make it easier to put comics in and take them out.

The next iteration will also have the comic name engraved on the spine of the case: this will make it take slightly longer to engrave, but should be negligible overall.

I also am going to modify the windows on the front and back and the tab on the side in a thematically appropriate way: I am already experimenting with various motifs I can use for particular comics. For example, I could create a slip-case for storing issues of Bitch Planet that has a window on the front and back in the shape of the Non-Compliant emblem.

My only real annoyance during the project is that the diagrams library has some weird corners and odd API design choices³. It is also a truly massive library. At one point, I deleted my sandbox, started rebuilding, walked to a nearby café⁴, had a coffee and sat for a bit, walked back, and found it still compiling.

Still, for the most part, it all worked without a hitch. And it was a lot of fun: creating a useful physical object⁵ from a screenful of code is a pretty cool feeling!