A Haskell Journey

Lately, partially as an exercise and partially to get a project of mine going the way I'd like to see it going, I've been working with the State monad directly. Using the state monad is trivial. Understanding how the state monad does its thing is slightly less trivial, but just a matter of following along the definitions and doing the appropriate substitutions. Understanding where the state monad came from and how to modify it to do what I want... now that's starting to get tricky.

I blundered around for a bit trying to reconstruct the state monad without actually looking at it and came to the conclusion it wasn't possible. Except that it clearly is possible because it's part of the standard library. The problem was that it had never really occurred to me to put a function in the type signature itself, the way the state monad does, and despite how simple it looks it has really hit home that I don't really grok the thing yet. I do not mean to overmystify; like I said I follow the thing perfectly well, a minimal and perfectly functional definition of the thing is like 10 rather simple lines and there's an upper limit to how confusing 10 lines can get, but... if you can't modify something you certainly don't grok it.

Yesterday night I realized I have felt this way before, but it had been such a long time that I hadn't instantly recalled it. I felt this way when I learned about pointers. My first language was Commodore 64 BASIC and I suffered the Dijkstra brain damage, but I got better. I never had the freakout that some people have with pointers, I got the base mechanics right away, no problem. But it took me a while to grok them, and in particular what they are good for. To come to the level of understanding that I might plausibly convince myself that I could come up with the Tortoise and the Hare linked list cycle detection algorithm on my own, or to come to the point where I could comfortably deal with pointers to pointers to functions that take pointers to functions that take an int and return another int without flipping out.

Or another example, I fell right into this: http://lukepalmer.wordpress.com/2010/01/24/haskell-antipatte... . Same reason, BTW; I wanted to write a "concrete datatype" when what I really needed was functions right there in my datatype. It really strikes me as the same sort of problem you can run into in C or C++ if you try too hard to avoid pointers; you end up with crazy ass designs that end up copying too much stuff around, and are ever stuck with being able to not really quite use the language to its fullest.

I'm feeling the way I did when I learned about pointers, and I recognize that I've got a ways to go before I'm comfortable with this sort of thing. (And I get the same results now when I diddle around with the state monad that I remember getting when I tried to modify pointer code before I really understood what I was doing, except the "segfaults" occur at compile time instead of runtime. Progress!)

(Perhaps ironically, I'm finding it's making me better with OO, too. Expressing responsibilities in terms of methods that take closures, rather than simply "concrete methods" that take parameters that aren't closures, can be a remarkably powerful way to approach OO interfaces.)

I hope this doesn't sound mystical, because I don't really mean it to be. I suspect (and my gut says) that in the end this will not be particularly different than learning about pointers, and few people (though not zero!) consider learning about pointers a mystical experience today. But that learning takes time, and I've only begun. At something like ~12 years of serious experience, finding a paradigm like this that has left me feeling like a total newb again has been a bit of a shocker. I find it invigorating and interesting, but I have slightly greater understanding for those who feel like after that long they should be allowed to avoid stepping into the areas that make them feel like newbs...

(And also, for those who may read this who are considering Haskell, let me again emphasize that you can do a lot of work in Haskell without giving thought one to the issues I raise here. Just as you can be a pretty decent programmer without really getting into assembler, and pulling the state monad out of the library and using it is trivial. It's just that if you want to go in really deep and really understand what's going on, there's definitely different stuff going on. It's not just C, C++, or Perl writ different like most languages today.)

I largely agree with what you (jrockway) say, but differ in some nuances. These "concepts + laws" seem to be best understood as mathematical constructs (like say functions or sets) than analogies. What I think is happening now is people are trying to understand Sets by studying say java.util.HashSet, or even worse, analogies to java.util.HashSet.

"Functors are containers that can apply a function ("fmap") to their contents."

This is true enough, but it is hard to understand the ((->) r) functor (for example) as a container. You can do it but you have to stretch a bit. I have seen people struggle with understanding IO as a container.

Wheras if you know that a functor maps (or transforms) objects (in the cCategory Theory sense, not in the OO sense) to objects ,and morphisms to morphisms, subject to 3 laws, then it makes perfect sense that ((->) r) is a functor. Likewise with IO.

The key this is to understand the Hask category where types are objects and functions are morphisms.

For a Haskell functor, the type constructor takes care of the "objects to objects" (or type to type) mapping and the first order function (map for lists for example, or compose for the ((-> r) and so on) take care of the morphism to morphism (here, functions to functions) mapping.

And it is not even very hairy math. The definition of a category is hardly half a page of prose, much easier to understand than some specs we programmers work off of.

@jrockway, do you want to write that book? :-)

Argh! Pet peeve time. Functors are not containers and calling them that makes it harder to understand how something like IO, ((->) a), or a Parsec parser qualify; also, some container types aren't (and can't be) Functors because they aren't polymorphic in the contained type (IntSet or ByteString, for instance).

Likewise, calling the Monoid operation "append" is needlessly confusing (and yes, the names the standard library uses are terrible). It's an associative binary operation with an identity value and no semantics whatsoever beyond that. Appending data structures is likely to form a monoid, but so can merging them (union and intersection both work). Any instance of Ord forms monoids under min and max. Functions are a monoid under composition. Even () forms a (trivial) monoid.

I'm pretty sure none of that is news to you, but I think using descriptions like "container" and "append" invoke too many preconceived ideas for people new to Haskell and creates barriers to understanding more than it helps. Most of this stuff is actually quite simple, but it's almost painfully abstract, and using concrete metaphors of familiar things obscures the full generality.

It's particularly a problem with Monoid, because the concept is both utterly trivial and broadly useful, but calling it "append" leads to people complaining about Haskell using a needlessly cryptic term for "appendable things" while simultaneously missing the entire point of the type class.

So anyway, just start programming, and you'll see why these abstractions are useful. You'll also see why "easy to understand" abstractions like "foldable" and "traversable" are useful too, even though there is not much category theory there.

For what it's worth, from a mathy perspective, I think Traversable represents some sort of distributive law between Functors (e.g., lets you do something that looks like "f (g a) -> g (f a)").

In categorical terms Foldable is related to "catamorphisms", though to my understanding the relevant bits of category theory were first explored by, and remain of interest mostly to, programming language theorists. Look at http://knol.google.com/k/edward-kmett/catamorphisms if you're brave enough...

Really the biggest step is, as jrockway says, to realize that Monad is (kind of) a verb. "Here's a list and here's how you can monad it."