Tuesday, March 25, 2014

Introductions to advanced Haskell topics

Many people bemoan the sharp divide between experts and beginning Haskell programmers. One thing I've noticed is that "advanced" Haskell topics all have one thing in common: there exists only one good tutorial on that topic and only the experts have found it. This post is a collection of links to what I consider to be the definitive tutorials on these topics.

Monads

Monads are technically not an advanced Haskell topic, but I include this topic in the list because the vast majority of monad tutorials are terrible and/or misleading. In my opinion, the best monad tutorial (Titled: "You could have invented monads") was written 8 years ago by Dan Piponi and nobody has ever improved on it since.

Monad Transformers

One thing that perpetually boggles me is that the blogosphere has almost no posts explaining how to use monad transformers. In fact, the only good explanation I know of is a very simple paper by Martin Grabmuller (Titled: "Monad Transformers - Step by Step"). Most beginners will skip over an academic paper like this when searching for tutorials since most people don't associate the word "academic" with beginner-friendly. However, don't let that fool you: this paper is very well written and easy to read.

Parsing

Outsiders comment that monads only exist to paper over Haskell's weaknesses until they discover monadic parsers. The truly mind-blowing moment is when you learn how simple they are to implement when you read Hutton and Meijer's functional pearl on monadic parsing (Titled: "Monadic Parsing in Haskell"). They walk through how to implement a backtracking parser, how to implement the Monad type class for this parser, and how to define several parsing primitives and chain them together into more sophisticated functionality. After you read this functional pearl you will never doubt the significance of monads ever again.

You also want to understand parser combinators for another reason: Haskell parser combinator libraries are light-years ahead of Haskell regular expression libraries. This confuses many people who come to Haskell from a language that uses regular expressions heavily (such as Python or Perl) and they wonder why regular expression support is so bad in Haskell. The reason is that nearly all Haskell programmers use parser combinator libraries such as parsec or attoparsec.

Free Monads

This is the only case where I will plug a post of my own. I wrote a tutorial on free monads (Titled: "Why free monads matter") because back when I was trying to understand free monads I could not find any beginner-friendly explanation. Everything on this subject was written for a target audience of mathematicians and would motivate their use cases using mathematical examples.

I wanted to explain the motivation behind free monads in terms that a programmer would understand and my post explains the topic in terms of creating a syntax tree and interpreting that syntax tree. Understanding free monads will greatly improve your understanding for how to build monadic domain-specific languages within Haskell. Also, many people comment that understanding free monads greatly improves their mental model for Haskell IO as well.

Coroutines

Haskell coroutine libraries (like pipes/conduit/machines) have what appear to be impenetrable implementations ... until you read Mario Blazevic's article on coroutines in issue 19 of The Monad Reader (Titled: Coroutine Pipelines").

In that article he introduces the Coroutine type (which is now more commonly known as the free monad transformer) which unifies every coroutine implementation into a single pattern. Once you understand his article, you will understand the internals of coroutine libraries and you will be able to easily write a streaming library of your own.

Lenses

Lens tutorials are the new monad tutorials, and the one mistake that all lens tutorials make is that none of them clearly explain how lenses work. The only post that ever got this right was the original post by Twan van Laarhoven that first introduced the modern formulation of lenses (Titled: "CPS Functional references"). The problem is that post is incredibly hard to find even through a dedicated Google search for lens tutorials because the title is obscure and the post only has a single mention of the word "lens". I actually had trouble finding this post even by browsing his blog archive because I didn't recognize the title.

Honorable mention: The lens-family-core library is the only lens library that actually hews closely to Twan's original presentation, so I highly recommend that you study its source code to further improve your understanding.

Church encoding

I still can't find a good blog post on Church encoding, so I will not link to anything. However, once you learn how to Church encode a data type you will suddenly see this pattern everywhere.

Equally important, many high-performance Haskell libraries (like attoparsec) use Church encoding for efficiency reasons and understanding Church encoding will allow you to understand their internal implementations.

Conclusion

I'm really disappointed that so many critical Haskell topics only have a single source of truth that is difficult to find. I hypothesize that the problem is that Haskell is rooted in computer science academia, which discourages duplicate publications on the same topic. If you want to prove me wrong, then please take the time to increase the number of high quality Haskell tutorials on these and other key topics.

Another troubling trend is that tendency for people to bandwagon on particular tutorial topics that are sexy (first monads, now lenses). I wish people would spend more time diversifying coverage on more mundane topics, like how to apply well-established libraries to architect various types of applications.

14 comments:

  1. "I'm really disappointed that so many critical Haskell topics only have a single source of truth that is difficult to find."

    Agreed; I have long thought that Haskell's biggest weakness generally is that there aren't very many good books about it. Most documentation is scattered through random papers and blog posts. Even library Haddocks often have references to papers--some of which are hard to find.

    "Lens tutorials are the new monad tutorials"

    Laughed when I read this because I've been thinking it for awhile. This is part of why I have been avoiding lenses. They seem like a huge grab bag of concepts tossed into one nasty stew.

    "they wonder why regular expression support is so bad in Haskell."

    Actually I'd say that Haskell regex support is just as good as Python's. Just like Python, Haskell requires you to load up a library to get regexps. There is a confusing smattering of libraries (the heavily overloaded interface of regex-base does beginners no favors) but pcre-light is easy to grasp and benefits from the exhaustive documentation of the pcre library.

    But Haskell's parser combinator libraries do shine, so I typically avoid regexps for anything static (sometimes regexps are handy if you want to allow the user to specify search strings at runtime.)

    ReplyDelete
    Replies
    1. Yeah, I should change my regex statement because you're right that `pcre-light` is decent and has okay tutorials. I will try to rephrase that section.

      Delete
  2. These posts has some introduction to Church encodings that's pretty alright, might be worth linking to.

    http://jozefg.bitbucket.org/posts/2014-03-06-church.html

    ReplyDelete
  3. About lenses, I found that talk by Simon Peyton Jones is really clear:

    https://skillsmatter.com/skillscasts/4251-lenses-compositional-data-access-and-manipulation

    ReplyDelete
  4. Very nice write-up. Do you have any recommended materials for FRP? It often feels similarly fragmented and I'd love to hear your recommendations on the topic.

    ReplyDelete
    Replies
    1. Elm is probably the best starting point. The FRP field is fragmented, but I think Evan Czaplicki (the author of Elm) has put far more thought into the issue of how to provide a simple interface while sacrificing as little power as possible.

      Delete
  5. The best article I've found that really explains church encodings is this one: http://matt.might.net/articles/compiling-up-to-lambda-calculus/
    It's done in a subset of Scheme, though, not Haskell.

    ReplyDelete
  6. As for me, recently I found 2 really good prerequisite lenses articles: "Implement semantic editor combinators" by Javrania and "From Zipper to Lens" at SOH.

    ReplyDelete
  7. Gabriel, do you know where to find a good tutorial on quasi quoting and template haskell?

    ReplyDelete
    Replies
    1. I haven't done very much Template Haskell, but this seems like a quick introduction:

      https://www.fpcomplete.com/user/marcin/template-haskell-101

      This page has lots of links to Template Haskell papers and articles that you might be interested in:

      https://www.haskell.org/haskellwiki/Template_Haskell

      Delete
  8. thanks for the great leads. there is definitely an open niche for a non-academic book on advanced haskell, imho.

    ReplyDelete
  9. The monad transformer link is broken

    ReplyDelete
    Replies
    1. Thanks for pointing that out! I fixed the link

      Delete
    2. since this page came up when I was looking for the Monad Transformer paper, I thought I'd add the link I found here, too:
      https://github.com/mgrabmueller/TransformersStepByStep

      I hope this is useful, and not spammy.

      Delete