Random thoughts on Haskell January 15, 2009 | 12:37 am

So I’ve been programming in Haskell a lot recently, and thought I’d just share some of the random observations I’ve had about the language. The book Real World Haskell was what really pushed Haskell over the top for me, from “a language I should probably learn someday” to “a language I am learning and writing real code in”. Seriously, if you’re interested in Haskell, get this book.

There’s no over-arching theme or structure here, just a collection of random asides, none of them really worthy of blog posts by themselves. So if you’re looking at the end of the post and going “is that it?”, yup, that’s it.

Haskell is a big language. Java is also a big language, but it’s a big language in a different way. Java is big like west Texas is big. There’s a lot of it, but there is something of a dreary sameness to it. Haskell is big in the way that Manhattan is big- which is to say that it’s actually smaller than it looks, but there is just so much going on, all right on top of each other, that it feels bigger than it is in an absolute, west Texas sort of way. In west Texas, you can travel hundreds of miles and still not really have gone much of anywhere- in Manhattan, cross a street and you’ve gone from (Little) Italy to China (town). Walk a couple of blocks that-a-way and suddenly you’re in SoHo. It’s an information-density thing.

Haskell is about code combinatorics, making lots of little things that can be combined together into bigger interesting things. Monads, and variations on monads and extensions to monads and operations on monads are the primary way Haskell combines code- but the core idea is combining code. Which is why Haskell has a Manhattan-like super-dense nature- just a few lines of code can create, not just a whole new combination, but a whole new way to combine code. Which then heterodynes with all the other ways of combining code. And which changes, not only what exists, but what can exist (or at least, your perception of what can exist).

Haskell and Lisp are really opposite ends of a spectrum. In Lisp, all code is data. A function is nothing more than a list of operations to perform. This leads naturally to the concept of macros- code that inspects and modifies a list of operations just like you would for any other list. In Haskell, it’s the other way around- all data is code. Part of this is lazy evaluation, you don’t have an int, for example, what you actually have is a closure, a hunk of code, that when executed, will produce an int. But this philosophy goes deeper than that- Haskell is constantly blurring the distinction between data and code.

An example of what I mean here is difference lists, which may be common in Haskell but I didn’t know of them before (thanks, RWH). Appending to the end of a list is expensive, even with lazy evaluation- you end up having to reallocate the whole list, just later in time than in Ocaml. A difference list allows us to append cheaply. The public API might look something like:

type Difflist a
empty :: Difflist a
append :: Difflist a -> a -> Difflist a
toList :: Difflist a -> [ a ]

It’s a Difflist holding some type a, I can start with an empty Difflist, append elements to my hearts content, and when I’m done, convert the whole thing to a list. Looks like a data structure to me. Acts like one too. But what it actually is, you might have guessed from context, is a function- specifically, it’s a function that, given the tail of the list, prepends all the earlier elements onto the tail. When we say “append this element”, we really just update the function to prepend the new element. The code makes this (somewhat) more clear:

type Difflist a = [a] -> [a]
 
empty :: Difflist a
empty = id
 
append :: Difflist a -> a -> Difflist a
append lst x = \tail -> lst (x : tail)
 
toList :: Difflist a -> [ a ]
toList lst = lst []

The key trick is in append- we are creating a new function which first prepends the given element onto the tail of the list before calling the original function to prepend all the other elements.

Yeah, there are probably better ways to do it- for example:

type Difflist a = [ a ]
empty = []
append lst x = x : lst
toList lst = rev lst

But the important point is the blurry line in Haskell between data and code, in that even data structures can really be code under the hood. This leads inevitably to monads, the ultimate (or at least ur-) data structure and/or code block. This, of course, leads to a lot of confusion around monads, as people keep trying to figure out is code or is it data, when it’s both.

One thing that does annoy me about Haskell- naming. Say you’ve noticed a common pattern, a lot of data structures are similar to the difference list I described above, in that they have an empty state and the ability to append things onto the end. Now, for various reasons, you want to give this pattern a name using on Haskell’s tools for expressing common idioms as general patterns (type classes, in this case). What name do you give it? I’d be inclined to call it something like “Appendable”. But no, Haskell calls this pattern a “Monoid”. Yep, that’s all a monoid is- something with an empty state and the ability to append things to the end. Well, it’s a little more general than that, but not much. Simon Peyton Jones once commented that the biggest mistake Haskell made was to call them “monads” instead of “warm, fluffy things”. Well, Haskell is exacerbating that mistake. Haskell developers, stop letting the category theorists name things. Please. I beg of you.

If you’re not a category theorists, and you’re learning (or thinking of learning) Haskell, don’t get scared off by names like “monoid” or “functor”. And ignore anyone who starts their explanation with references to category theory- you don’t need to know category theory, and I don’t think it helps.

I’m becoming very, very fond of lazy evaluation. Lazy evaluation is actually very common in the computer world, even outside of Haskell, people just don’t recognize it as such. Any time you’re writing code to produce some complicated structure on an as-needed basis, or short-circuiting a calculation or stopping a calculation early when some condition is met, you’re doing lazy evaluation. You’re just reimplementing what Haskell gives you for free.

Yes, lazy evaluation does lead to space leaks, but most every other language has problems just as bad, so if you’re using that as an excuse to write off Haskell, then also write off Java, C++, Ruby, etc. You disagree that, say, Java doesn’t have a problem that bad? Try null pointer exceptions. The difference is that Haskell is collecting a large tool set to address the issue of memory leaks, to help the programmer find and fix them. Real World Haskell has a whole chapter on the issue, how to profile your code and get at least some hints of where things are going wrong.

A while back I published a short screed saying that we needed both unit testing and static typing, and probably documentation as well, to produce correct, changeable (aka maintainable) code. Haskell is going a long way to proving me correct. First of all, Haskell has introduced (at least as far as I know) an interesting idea into the world of unit testing, which is quickcheck (although since then, the idea has been copied elsewhere). The idea is simple: define a generic way (using monads, natch) to generate random instances of some data structure, which you can then test various properties of. For example, you might test that, for all instances of a data structure, printing the data structure out (converting it to a string) and reading it back in again results in the same data structure. Automated code can then go through and generate a whole bunch of random structures and test to make sure the property holds. Static typing gets you a long way on the cheap, but it doesn’t do everything. The quickcheck infrastructure also documents the invariants that should hold, and thus are an aid for maintainers down the road.

Documentation is another interesting area in Haskell. In the above post, I talk about the importance of documentation to maintainability, and how I often even use documenting as a debugging technique. Well, Haskell is the first language I’ve used where literate programming makes sense. In normal programming, comments are marked out as special, maybe by a /* or — or some other character combination that says “the following isn’t code, it’s comment”. Everything not marked as comment is assumed to be code. With literate programming, it’s the other way around- it’s code that is marked out special (generally by putting a > sign at the beginning of lines of code), and anything not marked as code is assumed to comments. Generally, not just ordinary plain-text comments either, generally literate code comments are assumed to be latex.

Ignoring whether you like to dislike latex (and I happen to like it), the problem I’ve had with literate programming in other languages is that the comment to code ratio wasn’t high enough to make it worth it. Marking parts of the file as special, however you do it, is overhead. You should be marking the exception parts, not the majority parts. If the file is 70% one thing and 30% the other, you should be marking the 30%, not the 70%. In the other languages I’ve used, 70% or more the program files were code, not comment. In Haskell, it’s the other way around- 60/40 comments/code, if not more. At which point you’ve crossed a great divide, and downhill is the other way- it’s cheaper and easier to mark the code rather than the comments.

Toss in your standard xunit style unit testing, and you’ve got the trifecta of solid code- static type gaurantees, unit testing, plus strong documentation.

I’m not sure I’m on board yet with the whitespace being significant yet. It’s not as annoying as I thought it would be, however, having only really bitten me in one way (for some reason, if I have an if statement in a do block, the else needs to be indented- annoying). But I suspect this is mainly because I’m only one developer, and I’ve turned tabs off in vim (set expandtab). In a larger development group, this could be more of an issue.

Other than allowing the category theorists to name things, the main problem with Haskell being a “research language” that I see is the weak module system. Everything keeps wanting to get dumped into the same name space, so names tend to include the module. So it’s not TMVar.read, it’s readTMVar. Or, if you’re like me, and you tend to qualify your includes, it’s TMVar.readTMVar. Which is annoyingly repetitious, and repeatedly annoying.

A language being able to parse yourself is a huge advantage. It reclaims some of the ground lost to Lisp, and makes it easy to write tools to do various things with code.

  • http://naleid.com/blog Ted Naleid

    Thanks for highlighting some of the things you’ve found interesting about Haskell. I’ve just started working my way through RWH (bought the hard copy, but find using the book’s website (which is awesome) easier to use). I don’t have a ton of FP experience, but I really like what I see so far.

    Haskell feels like a much clearer, more pure vision of something that I’ve seen hints of in other tools that I’ve used in the past (XSLT, some of jQuery, closures in groovy, blocks in ruby, dependency injection, etc).

  • hydo

    “If you’re not a category theorists, and you’re learning (or thinking of learning) Haskell, don’t get scared off by names like “monoid” or “functor”. And ignore anyone who starts their explanation with references to category theory- you don’t need to know category theory, and I don’t think it helps.”

    YES! Please, if you take nothing else (well, there’s a lot of good here and I’m just picking one thing) from this take that Haskell is really really really simple. The hard part is not picking up the syntax, the hard part is training yourself to not assume _anything_ when you are learning it especially if you are coming from something like perl/python/c/etc. Type signatures look like absolute witchcraft the first few times you see them, but they make complete sense. Ugh, yes, and monads… I don’t think you could pick a more unfortunate name. Well… maybe “Sacksmashers”.

    Also, Yea, it’s dreary, dusty, and hot, but I can’t help but miss it. Especially when it’s raining for the thousandth day in a row in Seattle. Midland rep-ruh-sent.

  • Matt

    > Yep, that’s all a monoid is- something with an empty state and the ability to append things to the end.

    What you’re describing is closer to the idea of a “free monoid”, a specific type of monoid. A monoid is a very general concept, and there probably is no friendly intuitive name like “appendable” that would be any more enlightening.

    It might be fairer to fault Haskell for choosing to base some of its abstractions in mathematics; use of the mathematical terminology is just a consequence of that choice.

  • augustss

    I don’t understand the fear of existing words that mean exactly what you want to say. Why fear the word Monoid and invent Appendable? Monoid has a very special meaning, and it’s exact, and it’s what we want. Appendable is a new word and its exact meaning can only be guessed.

    Imagine writing a cook book where some of the dishes are going to be Indian. They will need to use ghee. Ghee has a very well defined meaning: melted, unsalted butter where the fat has been separated from the protein. So when writing this cook book it’s convenient to use the word ghee when we want ghee (there might be an explanation what ghee is in an appendix, but it’s also on Wikipedia). It’s well defined, and some people already know what it is. We could also invent a new word liquidbutter, but then nobody knows what it is. You can guess, but you don’t know exactly.

    Monoid is the same way, it’s a type with a binary operator that is associative and there is a value (empty) that is the left and right unit of the operator. The meaning is exact. Some people know what it means, if you don’t, you can look it up on Wikipedia. You can also invent a new word for the same thing. A word that nobody uses.

    Again, what’s wrong with using existing words that have an exact meaning?

  • http://www.ifany.org jonas

    Thank you for a very nice article. Interesting and well written. It makes me want to get on the haskell wagon once again. I wish life didn’t have so many other things coming in the way.

  • Saizan

    One of the problems with warm fuzzy names is that they can mean anything, while names from math (monoid really comes from abstract algebra) have a precise meaning, which in this case you didn’t get quite right, in fact your append wouldn’t qualify as an implementation of mappend for Difflist.
    mappend :: Monoid m => m -> m -> m

    Another useful thing about using such names is that they carry a theory with them, so e.g. you don’t have to rediscover useful properties from scratch.

  • Gour

    Well, Haskell is the first language I’ve used where literate programming makes sense.

    I wonder if Leo (http://webpages.charter.net/edreamleo/front.html) can be used as editor for literate programming in Haskell?

    Sincerely,
    Gour

  • http://comonad.com/ Edward Kmett

    Bah. Letting the category theorists name things isn’t a problem. Er… That is, if you’re a category theorist. ;)

  • Brian

    Saizan: You’re a category theorist, right? Or at least have studied Category Theory. I can tell :-).

    Seriously, the term “monoid” meant nothing to me when I first encountered it. Because I, like so many other programmers, haven’t studied category theory. I’m unusual enough that I’ve done a little abstract algebra, but not enough to be familiar with the term monoid. So the fact that the name has precise meaning in math doesn’t help me- any more than if the name had precise meaning in Navajo. “Oh, this term makes perfect sense, once you learn to speak Navajo…”

    What terms like monad, monoid, and functor do is scare off the newbies.

  • http://ro-che.info/ Roman Cheplyaka

    Brian: that’s very strange indeed that you’ve done abstract algebra and haven’t met monoids. It’s general algebra term (like group or field) and I met it far before I’ve even heard about haskell or category theory.

  • apfelmus

    I’m glad you like Haskell, and I’d like to clarify a few things.

    “Monads, and variations on monads and extensions to monads and operations on monads are the primary way Haskell combines code.”

    You will probably notice every occurrence of monads because they are novel to you, but that doesn’t mean that they are the most fundamental building block. The primary way to combine code is still good old functions and function composition. I’d like to recommend Richard Bird’s book Introduction to Functional Programming using Haskell for more along these lines.

    The “code as data” thing you noticed has nothing to do with monads either and it’s called “higher order functions”. It just means that functions may take other functions as arguments and return them as results (“closures”), i.e. they are treated like normal data.

    Also, while sounding similar, “monad” and “monoid” are different things, the latter being essentially a group without inverse elements. Monoids are usually introduced in the “Automata and Languages” course of a good CS curriculum.

  • immanuel

    Functor terminology is also used in c++, ML. The meanings there are different from those in Haskell.
    Monoid does not come from category theory, it comes from group theory — a set with a associative operation and a neutral element. I’ll ask my 14 year old nephew what this means, he’ll know, he gets good grades in maths.
    Summing up: if you learn new things, you will have to learn new words that will stand for concepts. It is important to learn the word for communication and clear writing and it is important to learn the concept. Sometimes the words are not new, but their meaning is. Sometimes the words are new, and the concept is not. Sometimes both are new, and in a *very* limited number of case the same word is used for the same concept you already knew.
    Immanuel
    P.S. I must admit I do *sometimes* use the internet to search for explanations of things I don’t understand but I’m trying to give that up.

    http://www.newty.de/fpt/functor.html
    http://www.smlnj.org/sml.html
    http://en.wikipedia.org/wiki/Monoid

  • http://pozorvlak.livejournal.com pozorvlak

    You can’t blame us for “monoid”, it was part of standard mathematical terminology long before category theory was invented. And it is at least easy to Google for. It’s also the only sensible name I’m aware of for “set equipped with an associative binary operation with a unit”

    I’m not sure that learning category theory is no help when learning Haskell – I found Haskell’s monads much easier to grasp once I had a handle on the use of monads in universal algebra. However, Haskell isn’t much help when you’re learning category theory :-)

  • http://procrastiblog.com Chris Conway

    In Haskell, it’s the other way around- all data is code.

    Isn’t this just another way of saying that Haskell is close in spirit to the lambda calculus? The first steep hill to climb in lambda calculus (at least for me) is wrapping your head around the representation of data as lambdas. DiffList looks a lot like the Church encoding of numerals.

  • http://procrastiblog.com Chris Conway

    > Yep, that’s all a monoid is- something with an empty state and the ability to append things to the end.

    What you’re describing is closer to the idea of a “free monoid”, a specific type of monoid. A monoid is a very general concept, and there probably is no friendly intuitive name like “appendable” that would be any more enlightening.

    Which actually just proves Brian’s point. The Haskell Monoid type class really is just an Appendable interface, with the added (unenforced) expectation that an instance will behave like a monoid.

  • Ryan Ingram

    Difference lists have more operations than just “cons at end”; they have O(1) operations to add elements at the beginning and end of a list, as well as to connect two lists together:

    append :: DList a -> DList a -> DList a
    append f g = \tail -> f (g tail)

    They’re really useful. If you were to represent them as a data structure directly, it would be a tree with lists at the leaves; “append” represents creating a branch that connects the two lists.

  • Matt

    @Brian
    >”the fact that the name has precise meaning in math doesn’t help me…What terms like monad, monoid, and functor do is scare off the newbies.”

    Would you then prefer it if Haskell used a name that suggested something to beginners, and gave them an immediate intuition about the concept, but that intuition was wrong or incomplete (like “appendable”)? Or some novel word which has no prior meaning? To me, it seems preferable to have people use a word which, while perhaps unfamiliar, already exists and has a clear and unambiguous meaning.

    I don’t disagree that maths terminology puts people off, but I don’t see any better alternative other than avoiding maths concepts altogether.

  • Anders

    The reason that DList is made of functions, instead of just having toList = reverse, is that you can have O(1) prepend and append on the same list. In your case, you have fast appends, at the cost of slower prepends.

  • http://all-are-wonders.blogspot.com Larry Coleman

    Speaking as a Haskell newbie, I would rather have it called “monoid” than “Appendable,” because that way I’d know that I don’t know what it means and that I have to look it up. If I wanted to be able to just guess what everything is and just code without learning anything, I’ll still be coding in VB. :P

    Give us newbies some credit. The type of newbie that would be scared off by the term “monad” doesn’t really want Haskell anyway.

  • http://comonad.com/ Edward Kmett

    “Monoid” has the advantage that you can clack it into google and get a nice definition from pretty much any of the first dozen results, more than half of them having nothing to do with Haskell. Er.. and to nitpick, a monoid is a concept from algebra not a category theory. ;)

    A large part of the standard library exhibits trade-offs between mathematical precision and understandable vocabulary. Haskell uses the warm fuzzy name “Num” to describe stuff that acts like a number. A purist or mathematician would probably argue in favor of break Num up into a Ring class and some other constraints, etc.

    But in the end, no matter which way you decide the issue, some part of your user base gets annoyed at the chosen convention.

    I will agree that Functors and Monads _are_ scary, if only because they are always in your face. You’re stepping into unfamiliar territory with the language in the first place and then wham all of a sudden you have to deal with all of these abstract concepts just to write “Hello World” or manipulate lists. This is further exacerbated by the fact that Haskell Functors and Monads are just a subset of the mathematical notion of functors and monads; for the pedantic they are endofunctors and monads over the category of Haskell types. This makes the connection to the mathematical definitions even harder to see at first glance and adds to their mystique and steepens the startup curve.

    On the other hand, Haskell monads have a ton of properties that they need to provide to meet the definition that go above and beyond the properties provided by their type signatures, so you have to call them something.

    One counter argument to the ‘just choose a descriptive name’ argument, is that descriptive is relative. Monads _have_ had a lot of names over the years in the mathematical community.

    In the mathematics community, they have been called triples (a REALLY bad idea, because then a lot of things were defined as a “triple whatevers”, even when there weren’t three things involved) and called standard constructions (er.. try to google THAT!).

    In the programming community, F# has tried to construct something similar with a warm fuzzy name — “Workflows”. One could argue that that is a less terrifying term than Monad, but again you run into the “how to google it” problem. That and workflows have much uglier semantics than monads, because they need to work around the constraints of a strict language.

    As a final point, in choosing the warm fuzzy name you lose history. Monads, then called standard constructions, popped into use in the category theory community in 1958, predating even the birth of _LISP_ in programming language circles. That is a lot of history to toss aside just because of a strange name.

  • Daniel

    @Brian: Really? Monoids are one of the first things you should hear about in abstract Algebra/group theory. We had this term in many Lectures at my University (linear algebra, abstract algebra, the first lecture in computer science etc.), but I doubt that more than a handful of the students have ever heard anything of category theory. ;-)

  • http://shimweasel.com Mark Wotton

    I think that DiffList implementation sort of misses the point – the idea is to make adding at both ends cheap. Your implementation only offers the append operation, there’s no real benefit over using a list that you reverse at the end (as in your second example…)

  • Ravi

    We’re fixing the do-block indentation thing (see: http://hackage.haskell.org/trac/haskell-prime/wiki/DoAndIfThenElse ).

    Last I checked the tweak hasn’t made any Haskell compiler I use, sadly, but I am waiting with bated breath…

  • Tim

    What indentation et al files do you use for Haskell in vim? I found one or two online, but neither seems real great at it.

  • Eugene Kirpichov

    Thanks, overall the post is great!

    However one thing I don’t understand is why you put so much stress on the monads: namely, these phrases:

    > Monads, and variations on monads and extensions to monads and operations on monads are the primary way Haskell combines code- but the core idea is combining code.

    > even data structures can really be code under the hood. This leads inevitably to monads, the ultimate (or at least ur-) data structure and/or code block. This, of course, leads to a lot of confusion around monads, as people keep trying to figure out is code or is it data, when it’s both.

    Monads are *not* the primary way Haskell combines code; no more than, for example, is the Strategy pattern Java’s primary way to implement polymorphism.

    Monads are a way to abstract one particular pattern of code/data flow: namely, the pattern where you want a user-defined way of *sequencing* computations; monads are essentially an overrided semicolon.
    Although they are ubiquitous in Haskell and they happen to allow expressing a whole lot of things, like, computations with multiple results (List monad), computations with state (State) or side effects (IO), continuations (Cont), computations which may return an error (Error or Maybe) etc., they are certainly not the primary way to combine code, and you don’t need them at all to use higher-order functions, use code as data, create your control structures etc; they are completely unrelated, only in the sense that actual implementations of particular monads of course do use Haskell’s combination features.

  • http://vcolin.com Colin Ross

    When I use if-then-else, I have got into the habit of formatting it like so:

    if condition
    …then expression1
    …else expression2

    which I find helps to maintain the distinction between the condition and the expressions as well as preventing any annoying parse errors.

  • http://all-are-wonders.blogspot.com Larry Coleman

    @Tim:

    I also use vim and Haskell. I ended up settling for just using autoindent, and setting shiftwidth to 2. Not pretty, but it works.

  • Pingback: On keeping category theory and abstract algebra alive in Haskell « Integer Overflow

  • Ashley Yakeley

    The whole point of Haskell is precision. A Monoid is not just an “appendable”. A correct instance of the Monoid class must follow the Monoid laws:

    mappend mempty a = a
    mappend a mempty = a
    mappend a (mappend b c) = mappend (mappend a b) c

    Haskell aims to discourage programmers from slapping something together that “just works” but is incorrect.

  • Pingback: Enfranchised Mind » How Should I Burn My Free Time?

  • Ron Wolf

    Right. Having a new name encourages people to _think_ of it as something new; reusing old names makes people think they already understand it (for example, the naming of `return`).