Tuesday, April 17, 2012

LTMT Part 2: Monads

In part 1 of this tutorial we talked about types and kinds. Knowledge of kinds will help to orient yourself in today's discussion of monads.

What is a monad? When you type "monad" into Hayoo the first result takes you to the documentation for the type class Monad. If you don't already have a basic familiarity with type classes, you can think of a type class as roughly equivalent to a Java interface. A type class defines a set of functions involving a certain data type. When a data type defines all the functions required by the type class, we say that it is an instance of that type class. When a type Foo is an instance of the Monad type class, you'll commonly hear people say "Foo is a monad". Here is a version of the Monad type class.

class Monad m where
    return :: a -> m a
    (=<<) :: (a -> m b) -> m a -> m b

(Note: If you're the untrusting type and looked up the real definition to verify that mine is accurate, you'll find that my version is slightly different. Don't worry about that right now. I did it intentionally, and there is a method to my madness.)

This basically says that in order for a data type to be an instance of the Monad type class, it has to define the two functions return and (=<<) (pronounced "bind") that have the above type signatures. What do these type signatures tell us? Let's look at return first. We see that it returns a value of type m a. This tells us that m has the kind signature m :: * -> *. So whenever we hear someone say "Foo is a monad" we immediately know that Foo :: * -> *.

In part 1, you probably got tired of me emphasizing that a type is a context. When we look at return and bind, this starts to make more sense. The type m a is just the type a in the context m. The type signature return :: a -> m a tells us that the return function takes a plain value a and puts that value into the context m. So when we say something is a monad, we immediately know that we have a function called return that lets us put arbitrary other values into that context.

Now, what about bind? It looks much more complicated and scary, but it's really pretty simple. To see this, let's get rid of all the m's in the type signature. Here's the before and after.

before :: (a -> m b) -> m a -> m b
after  :: (a -> b) -> a -> b

The type signature for after might look familiar. It's exactly the same as the type signature for the ($) function! If you're not familiar with it, Haskell's $ function is just syntax sugar for function application. (f $ a) is exactly the same as (f a). It applies the function f to its argument a. It is useful because it has very low precedence and is right associative, so it is a nice syntax sugar that allows us to eliminate parenthesis in certain situations. When you realize that (=<<) is roughly analogous to the concept of function application (modulo the addition of a context m), it suddenly makes a lot more sense.

So now what happens when we look at bind's type signature with the m's back in? (f =<< k) applies the function f to the value k. However, the crucial point is that k is a value wrapped in the context m, but f's parameter is an unwrapped value a. From this we see that the bind function's main purpose is to pull a value out of the context m and apply the function f, which does some computation, and returns the result back in the context m again.

The monad type class does not provide any mechanism for unconditionally pulling a value out of the context. The only way to get access to the unwrapped value is with the bind function, but bind does this in a controlled way and requires the function to wrap things up again before the result is returned. This behavior, enabled by Haskell's strong static type system, provides complete control over side effects and mutability.

Some monads do provide a way to get a value out of the context, but the choice of whether to do so is completely up to the author of said monad. It is not something inherent in the concept of a monad.

Monads wouldn't be very fun to use if all you had was return, bind, and derived functions. To make them more usable, Haskell has a special syntax called "do notation". The basic idea behind do notation is that there's a bind between every line, and you can do a <- func to unwrap the return value of func and make it available to later lines with the identifier 'a'.

You can find a more detailed treatment of do notation elsewhere. I hear that Learn You a Haskell and Real World Haskell are good.

In summary, a monad is a certain type of context that provides two things: a way to put things into the context, and function application within the context. There is no way to get things out. To get things out, you have to use bind to take yourself into the context. Once you have these two operations, there are lots of other more complicated operations built on the basic primitives that are provided by the API. Much of this is provided in Control.Monad. You probably won't learn all this stuff in a day. Just dive in and use these concepts in real code. Eventually you'll find that the patterns are sinking in and becoming clearer.

Monday, April 16, 2012

The Less Travelled Monad Tutorial: Understanding Kinds

This is part 1 of a monad tutorial (but as we will see, it's more than your average monad tutorial). If you already have a strong grasp of types, kinds, monads, and monad transformers, and type signatures like newtype RST r s m a = RST { runRST :: r -> s -> m (a, s) } don't make your eyes glaze over, then reading this won't change your life. If you don't, then maybe it will.

More seriously, when I was learning Haskell I got the impression that some topics were "more advanced" and should wait until later. Now, a few years in, I feel that understanding some of these topics earlier would have significantly sped up the learning process for me. If there are other people out there whose brains work somewhat like mine, then maybe they will be able to benefit from this tutorial. I can't say that everything I say here will be new, but I haven't seen these concepts organized in this way before.

This tutorial is not for absolute beginners. It assumes a basic knowledge of Haskell including the basics of data types, type signatures, and type classes. If you've been programming Haskell for a little bit, but are getting stuck on monads or monad transformers, then you might find some help here.

data Distance = Dist Double
data Mass = Mass Double

This code defines data types called Distance and Mass. The name on the left side of the equals sign is called a type constructor (or sometimes shortened to just type). The Haskell compiler automatically creates functions from the names just to the right of the equals sign. These functions are called data constructors because they construct the types Distance and Mass. Since they are functions, they are also first-class values, which means they have types as seen in the following ghci session.

$ ghci ltmt.hs
GHCi, version 7.0.3: http://www.haskell.org/ghc/  :? for helpghci> :t Dist
Dist :: Double -> Distance
ghci> :t Mass
Mass :: Double -> Mass
ghci> :t Distance
<interactive>:1:1: Not in scope: data constructor `Distance'

We see here that Dist and Mass are functions that return the types Distance and Mass respectively. Frequently you'll encounter code where the type and the constructor have the same name (as we have here with Mass). Distance, however, illustrates that these are really two separate entities. Distance is the type and Dist is the constructor. Types don't have types, so the ":t" command fails for Distance.

Now, we need to pause for a moment and think about the meaning of these things. What is the Distance type? Well, when we look at the constructor, we can see that a value of type Distance contains a single Double. The constructor function doesn't actually do anything to the Double value in the process of constructing the Distance value. All it does is create a new context for thinking about a Double, specifically the context of a Double that we intend to represent a distance quantity. (Well, that's not completely true, but for the purposes of this tutorial we'll ignore those details.) Let me repeat that. A type is just a context. This probably seems so obvious that you're starting to wonder about me. But I'm saying it because I think that keeping it in mind will help when talking about monads later.

Now let's look at another data declaration.

data Pair a = MkPair a a

This one is more interesting. The type constructor Pair takes an argument. The argument is some other type a and that is used in some part of the data constructor. When we look to the right side, we see that the data constructor is called MkPair and it constructs a value of type "Pair a" from two values of type "a".

MkPair :: a -> a -> Pair a

The same thing we said for the above types Distance and Mass applies here. The type constructor Pair represents a context. It's a context representing a pair of values. The type Pair Int represents a pair of Ints. The type Pair String represents a pair of strings. And on and on for whatever concrete type we use in the place of a.

Again, this is all very straightforward. But there is a significant distinction between the two type constructors Pair and Distance. Pair requires a type parameter, while Distance does not. This brings us to the topic of kinds. (Most people postpone this topic until later, but it's not hard to understand and I think it helps to clarify things later.) You know those analogy questions they use on standardized tests? Here's a completed one for you:

values : types    ::   types : kinds

Just as we categorize values by type, we categorize type constructors by kind. GHCi lets us look up a type constructor's kind with the ":k" command.

ghci> :k Distance
Distance :: *
ghci> :k Mass
Mass :: *
ghci> :k Dist
<interactive>:1:1: Not in scope: type constructor or class `Dist'
ghci> :k Pair
Pair :: * -> *
ghci> :k Pair Mass
Pair Mass :: *

In English we would say "Distance has kind *", and "Pair has kind * -> *". Kind signatures look similar to type signatures because they are. When we use Mass as Pair's first type argument, the result has kind *. The Haskell report defines kind signatures with the following two rules.

  • The symbol * represents the kind of all nullary type constructors (constructors that don't take any parameters).
  • If k1 and k2 are kinds, then k1->k2 is the kind of types that take one parameter that is a type of kind k1 and return a type of kind k2.

As an exercise, see if you can work out the kind signatures for the following type constructors. You can check your work with GHCi.

data Tuple a b = Tuple a b
data HardA a = HardA (a Int)
data HardB a b c = HardB (a b) (c a Int)

Before reading further, I suggest attempting to figure out the kind signatures for HardA and HardB because they involve a key pattern that will come up later.


Welcome back. The first example is just a simple extension of what we've already seen. The type constructor Tuple has two arguments, so it's kind signature is Tuple :: * -> * -> *. Also if you try :t you'll see that the data constructor's type signature is Tuple :: a -> b -> Tuple a b.

In the case of the last two types, it may be a little less obvious. But they build on each other in fairly small, manageable steps. For HardA, in the part to the left of the equals sign we see that there is one type parameter 'a'. From this, we can deduce that HardA's kind signature is something of the form ? -> *, but we don't know exactly what to put at the question mark. On the right side, all the individual arguments to the data constructor must have kind *. If (a Int) :: *, then the type 'a' must be a type constructor that takes one parameter. That is, it has kind * -> *, which is what we must substitute for the question mark. Therefore, we get the final kind signature HardA :: (* -> *) -> *.

HardB is a very contrived and much more complex case that exercises all the above simple principles. From HardB a b c we see that HardB has three type parameters, so it's kind signature has the form HardB :: a -> b -> c -> *. On the right side the (a b) tells us that b :: * and a :: * -> *. The second part (c a Int) means that c is a type constructor with two parameters where its first parameter is a, which has the type signature we described above. So this gives us c :: (* -> *) -> * -> *. Now, substituting all these in, we get HardB :: (* -> *) -> * -> ((* -> *) -> * -> *) -> *.

The point of all this is to show that when you see juxtaposition of type constructors (something of the form (a b) in a type signature), it is telling you that the context a is a non-nullary type constructor and b is its first parameter.

Continue on to Part 2 of the Less Travelled Monad Tutorial

Sunday, April 15, 2012

Four Tips for New Haskell Programmers

The Haskell programming language is widely considered to have a fairly steep learning curve--at least compared with mainstream languages.  In my experience with Haskell and specifically helping newcomers I've noticed a few common issues that seem to come up again and again.  Some of these issues might be more avoidable if the Haskell community did a better job communicating them.  Four points I have noticed are:
  1. Read Haddock API docs
  2. Pay attention to type class instances
  3. Learn about kinds
  4. Learn monad transformers

Read Haddock API Docs

I mention this point at the risk of stating the obvious.  If you are going to become a proficient Haskell programmer, it's absolutely essential that you get used to reading the API docs for the packages you use.  I often hear newcomers ask for tutorials demonstrating how to use packages.  Our community would definitely be better off with tutorials for every package, but it would also be better if newcomers would pay more attention to the API docs.  Now I know you're probably thinking, "yeah, but most packages are poorly documented."  That is true, but Haskell's type signatures tell you a lot more about a function than other languages.  For instance, consider the following example:

readChan :: Chan a -> IO a

A Chan is essentially a queue.  You can put values in and get them out in FIFO order.  When you are trying to understand the above function, one of the first things you might wonder about it is whether it blocks or not.  But if you think about it a little more, you'll realize that this function has to block.  If it didn't block, then there might not be a value and there would be no way to return something of type a (because Haskell has no null pointers).  A non-blocking version would have to have a type signature like this:

tryReadChan :: Chan -> IO (Maybe a)

So even with no prose documentation added at all, you can still learn a lot from the type signatures.  This is more significant in Haskell than other languages because of Haskell's purity and its strong type system.  Also, I would recommend that you bookmark the url "http://hackage.haskell.org/package/".  Actually, better yet, type it into your web browser frequently so it is the first thing given to you by the autocorrect when you start typing "hack...".  Once you auto-complete that url, you can just type the name of the package you are looking for and you'll immediately get to the most recent API docs for that package.  It's way faster than hitting control-f and searching through the package list on that page.

Also, bookmark http://www.haskell.org/ghc/docs/latest/html/libraries/index.html because it has links to documentation for the core libraries.

Pay Attention to Type Class Instances

I can't emphasize this point enough.  One of the most common questions I get from beginners is how to run an IO function in some random monad.  This information is trivially visible in the API docs, but for some reason beginners never seem to notice.  Take for example the Snap monad.  Go ahead, click that link and look at the documentation.  The clue that you can run IO actions inside that monad is tucked away near the end of the "Instances" block.  It's one little innocuous line MonadIO Snap.  Newcomers might not be familiar with MonadIO, but if they click the link they'll see that it defines one function liftIO :: IO a -> m a that converts any function in the IO monad to a function in the current m monad.  Those instance lines contain a treasure trove of information.  Don't neglect them.

Learn About Kinds

In Haskell all values have a type.  Analogously, all types have a kind.  This topic is often not brought up until later, but I feel that understanding kinds gives beginners a big advantage in understanding type signatures.  I'm not going to go into it in detail here, but I think it's an important concept that is too often ignored.

Learn About Monad Transformers

This is another one of those topics that is often put off until later.  When I was learning monads, I distinctly remember getting the impression that monad transformers were a much more complicated beast and that I didn't need to learn about them at that time.  But when I finally did learn about monad transformers a lot of things became clearer for me.  Also, monad transformers are used all the time in real world applications.  Transformers are a much simpler concept than monads, especially if you know about kinds.  There's no reason not to learn them at the same time.

Tuesday, April 10, 2012

A Hopefully Fair and Useful Comparison of Haskell Web Frameworks

Recently there has been a lot of discussion and questions about the differences between the big three Haskell web frameworks: Happstack, Yesod, and Snap. Different pieces of the answer have been discussed in a number of places. In this post, I'd like to try to give a more complete comparison. Hopefully it will be relatively unbiased, but without being too watered down to be useful. I've succeeded if you can't tell which framework I'm a major contributor to based solely on the text of this post.

Happstack

First, up is Happstack, the oldest of the three with original commit history as early as February, 2005. Happstack used to be called HAppS. It was primarily composed of a web server based on lazy IO, a fairly radical (for the time) in-memory persistence approach for storing and versioning native Haskell data types, and a library called IxSet for making it easier to use this state system with relational data access patterns. I've heard a number of people describe HAppS (and Happstack) as being synonymous with this unconventional state system, but today the state system has been completely rewritten and rebranded as a standalone persistence system called acid-state.

Of the three frameworks, Happstack is probably the least monolithic and exists mostly as a loose collection of libraries that can be mixed and matched to suit one's needs. A quick search for "happstack" on hackage will reveal a large number of libraries providing a diverse range of functionality. This includes support for at least four template systems: Hamlet, Heist, HSP, and StringTemplate. The main Happstack maintainer also maintains a type-safe URL called web-routes which, if carefully used, provides compile-time guarantees that your site won't have broken internal links.

While Happstack includes support for the widest range of choices, its most visible members do seem to favor a few in particular. Based on the current Happstack Crash Course, I would guess that the canonical libraries[1] for Happstack probably include BlazeHtml and HSX/HSP for templating, web-routes for routing, and acid-state for persistence. Acid-state and its all-haskell persistence philosophy combine with the type-safe routing and templates to create a set of libraries for web development where Haskell's expressive type system is king.

Yesod

The next of the big three to hit the scene was Yesod, which released in March of 2010. While Happstack (and later Snap) applications only worked as standalone binaries that were their own web server, Yesod provided FastCGI support which enabled Yesod applications to run on shared hosting where running a standalone web server was not an option. Perhaps Yesod's defining characteristic is its strong emphasis on static type checking for all aspects of the web app enabled by a number of custom DSLs used in different areas. In January 2011, the Yesod team released a new modern web server called Warp sporting the fastest benchmark numbers of any Haskell web server, a title still held today.

Yesod's type safety starts with the Hamlet compile time template language with syntax derived from HAML, a markup language that is lighter than (X)HTML. Hamlet's syntax makes it really simple to put dynamic data in templates while remaining strongly typed. This fits really well with Yesod's type-safe routing DSL that generates links for you. The paradigm is very similar to using Happstack with HSX/HSP and web-routes, but with a custom DSL that is more compact. Yesod has taken things a step further though with their Shakespearean template system which they have used to create Cassius and Julius, two strongly typed compile-time DSLs for generating CSS and Javascript.

In working with this paradigm, Yesod developers observed that some amount of boilerplate code was usually required to accomplish all this type safety. Leveraging the power of TemplateHaskell and quasiquoting, Yesod provides small domain-specific languages with syntax customized to each unique purpose that let you specify your site with very little unnecessary cruft.

Additionally, Yesod created a generalized database library called persistent, which uses these same design patterns to create a DSL for specifying your site's data model and lets you easily use MySQL, PostgreSQL, SQLite, or MongoDB to store your data and interact with it in a type safe manner.

This week Yesod released 1.0 milestone, communicating that they have reached a point where they will be maintaining longer-term API stability and support.

Snap

Snap is the youngest of the three frameworks. It went public in May of 2010, two months after Yesod. Its initial release featured a template system called Heist, and the first web server implementation to use the new modern concept of left-fold enumerators, a technique for achieving more predictable space usage than lazy IO. The web server API provides a set of combinators that provides a flexible framework for creating both simple and complex routes. This API is essentially a slimmed down and simplified version of the API that Happstack has been using since the early days of HAppS, and as such it should be fairly straightforward to port applications and libraries between the two.

The Heist template system differs from Hamlet and HSP in that it reads templates at runtime rather than compile-time, essentially thinking of templates as data rather than code. This means that it can't do truly type-safe URLs like the other two, but it enforces a much stronger division between code and view.  It also makes it possible for templates to be reloaded without recompiling the application. Aside from the fact that it allows you to define your own tags dynamically, Heist's template syntax is valid HTML.

More recently, Snap released a component system called Snaplets which is designed to allow web apps to be built from self-contained modular components. The Snaplets API provides a composable way to handle things like built-in filesystem resources and installation, config file support, and in-memory state. Since the release of the Snaplets API, the Snap team and third-party developers have released a number of snaplets providing support for sessions, authentication, database integration, etc. Yesod provides something called subsites that looks similar, and based on Happstack's roadmap it sounds like they will be working on another take on this problem in the future.

Snap's canonical libraries appear to be just Snap and Heist. The Snap web server is actually split out into two separate libraries snap-core and snap-server while the Snaplet API is the umbrella project. Other than that, the Snap team hasn't pledged allegiance to any particular database library so you should be free to use anything.

Conclusion

Each of the three frameworks has their own unique perspective. They make different tradeoffs, and have different senses of code aesthetic. There's the tradeoff of static, type-safe, and determined at compile-time versus less type-safe, more flexible, and determined at run-time. There's also the tradeoff of concise custom DSLs versus expressive and powerful combinator libraries. Do you go with a generalized database library that provides unified and necessarily watered-down interface to a number of different backends or tie yourself to a single specific database and leverage its full power? These are not always binary choices either. Each of these tradeoffs may be an axis on which there are several or a continuum of valid points to choose from.

Keep in mind that in most cases, different components of the above frameworks can be mixed and matched to suit your needs.  Hopefully this post paints a clearer picture of the landscape and helps you find the framework (or combination of frameworks) that fits your needs and preferences best.

[1] When I use the term "canonical libraries" in this article I'm talking about what I infer is probably the preference used by the main developers maintaining each web framework, and this is likely to be the direction the framework as a whole moves in with a more holistic solution if it chooses to do so.