Intro

Stuck for a topic at Newcastle’s Ruby group, I attempted an off the cuff talk on what Haskell is about, and what Ruby programmers could learn from it.

I was hoping to tie this to a kata-style programming exercise: this would give a nice set of examples where we could compare code and approaches in a variety of languages. In the end, this didn’t get organised. (Hey, we need to send a spy to the Edinburgh and Glasgow Ruby groups to see how they manage it.)

This piece here is an attempt to summarise the key points.

So what is FP and Haskell?

It’s possible to spend ages arguing about what FP is and what it means. For me, there is one central idea behind everything that informs the language design and the programming style: FP is about *putting data structures first*.

I don’t often see this view in the tutorials or the textbooks. Sometimes, I fear that there’s generally too much focus on the syntax and semantics of the language(s) and not enough on the _pragmatics_. The latter includes the problem solving techniques and general approach, and is what you really need to grok to use the language well. The syntax etc will get you through small examples and exercises, but you need to absorb some deeper ideas
to make it really fly.

Digression

This reminds me of my second-favourite joke. An eminent professor was once asked what was the best programming language. He thought for a moment, and answered “graduate student”.

It’s a serious point, think about it. What language would you like to program in? You don’t have to use the ones everyone else does. In fact, you can do whatever you like! Languages are our tools, so let’s use the best tools we can get.

There’s an approach to programming which I shall call the “McBride method”. Obviously, this has been invented several times, and is the kind of thinking behind current popularity of (embedded) DSLs. This version comes from Prof. Fred McBride in the 1970s, around the time he implemented pattern matching in Lisp. It has three steps:

• write the program P you want to write
• write another program Q which runs P
• run P via Q.

Notice that this version is particularly pure: it’s not about fitting a DSL into one’s favourite language, instead more about first designing a good language for your problem – and then wondering about the implementation of it.

Notice that problem solving, and expressing a clear solution for the problem, always comes first. Be sure you know which end of the dog you are dealing with.

What do the languages provide?

So programming in FP (to me) is about focussing on the data structures in a problem domain, and on the transformations between the data. When problem-solving, you should work out what kinds of data you are manipulating and think about ways to transform the input to the output.

(Modern) Functional languages provide excellent tools for working in this way, and the good languages have rich collections of tools which work well together. The effect is greater freedom and flexibility to do complex programming.

Have you ever looked at some of your code and thought, there has to be a better way to do it? Or thought that the key details were getting lost under syntactic and language baggage? FP provides some of the tools you need. These tools include

• easy to create a range of data structures (not just objects, arrays, hashes)
• powerful tools for taking apart and manipulating data – pattern matching
• lots of flexibility to parametrize and reuse code
• powerful glue, typically via HOFs (higher order functions)

Some examples: data structures

1. Bool isn’t built in to Haskell, in the sense that it is in many other languages. Instead, we can just define it like any other (enumeration) type, say like days of the week, and then use the general mechanisms in the language. (We also get short-circuit evaluation of conditional expressions for free, but that’s another story.)
2. The same data type definition mechanism allows definition of records (structs), unions,
   polymorphic types, recursive types, and other stuff you’ve probably never even thought of
3. Eg “data Maybe a = Nothing | Just a” – is a polymorphic type which is very useful in FP. You might think of it as a box which is either empty or has a value in it. I’ll say more about it later.
4. Recursive types, like trees, eg “data BTree = BLeaf Int | BNode BTree BTree” for a simple binary tree with Ints at its leaves, or “data PTree a = PLeaf a | PNode (PTree a) (PTree a)” for the same but with anything at the leaves. And we can use these (parametric) polymorphic types with any types, eg “PTree String” for string leaves, or even “PTree [Ptree (IO ())]” for trees with trees of IO-actions at the leaves.
5. How about this? “data X c a = XLeaf a | XNode (c (X c a))” – notice how ‘c’ is being used. Effectively, we have something that is tree-like, but the kind of tree it is can be controlled by changing ‘c’. For example, if c is the type constructor for lists, then we get trees whose nodes have zero or more children. If (c a) is the type (DayOfWeek -> a), then we have a tree whose nodes have a child for each day of the week. Powerful stuff.

Haskell can also construct automatically various widgets for the types we define, such as standard equality tests, ordering tests, show functions, enumeration ranges (eg ‘[Monday .. Friday]’).

The key point here is freedom and flexibility – we can easily add new types to model parts of a problem domain, or reuse existing types to build the types we need. There’s less overhead than in other languages – a short, one-line definition does a lot of work.

Some examples: pattern matching

Doing stuff with values in the above types is easy: we just write clauses in our functions to deal with the various patterns we expect to see.

Example, mirror-reversing a tree. There’s two main cases, leaf or node, and each clause says what to do with the contents of the tree.

mirror :: PTree a -> PTree a
mirror (Leaf x) = Leaf x
mirror (PNode l r) = PNode (mirror r) (mirror l)

Notice that we’re covering all possible cases of tree here. A value which is of tree type is either a leaf or a node, and we provide code to handle both cases in full. We’ll never get a run-time error when an unexpected input is received. Some of the compilers track this ‘totality’ for us, and can give warnings when functions don’t cover all cases.

Also note, we don’t need if-statements so much now. Pattern matching does most of the checking work for us. We can still have boolean-conditional tests, eg “if 2 > 3 then ‘a’ else ‘b'”, or there’s a short-hand for combining these with the patterns above. We can also define something ourselves.

my_if :: Bool -> a -> a -> a
my_if False _ f = f
my_if True t _ = t

Finally, we can arbitrarily nest patterns for more complex conditions.

foo :: PTree Int -> PTree String
foo (Leaf x) | x > 10 = Leaf "big"
| otherwise = Leaf "small"
foo (PNode (Leaf x) r) = PNode (foo (Leaf x)) (foo r)
foo (PNode l (Leaf r)) = PNode (foo (Leaf r)) (foo l)
foo (PNode l r) = PNode (foo l) (foo r)

Some examples: parametrization & reuse

You’ve already seen some examples of this above, eg where we defined a general structure for binary trees and used it in a variety of ways. Tree mirroring doesn’t depend on what’s at the leaves, so we can use it to mirror any tree value (as long as it’s “PTree something”). The nonsense ‘foo’ function shows a conversion from a tree with one type of ‘payload’ to a tree with a different type.

Haskell also has a notion of ‘type class’, which is a bit like Java’s ‘interface’ feature but more powerful. With this, we can declare that certain types implement some interface (as a collection of functions), and then write polymorphic functions to work on all types that obey the interface. For example, showing a PTree:

show_ptree :: Show a => Ptree a -> String
show_ptree (PLeaf x) = show x
show_ptree (PNode l r) = "PNode (" ++ show_ptree l ++ ") (" ++ show_ptree r ++ ")"

We can use this to show a tree whose payload has a showable type. In fact, this kind of function is something Haskell can define for us automatically, so we’d rarely write the above. Notice also that Haskell will check that we’re using interfaces appropriately, and tell us when some interface use isn’t ok, eg if we’re trying to show a value in a type which has some non-showable component (and the compilers usually suggest what extra code we need).

Some examples: powerful glue

Functional programs tend to be a collection of small definitions, combined in various ways to solve the overall problem. We often refer to this facility as ‘glue’.

For example, we might have broken our problem solution into a series of linear steps, so we can imagine joining the steps together in a pipeline, with one stage feeding its output to the input of the next, eg ‘unwords $ map reverse $ words “foo bar”‘ (read this right to left first).

Higher order functions, where functions receive or return other functions, is another kind of glue. Ruby programmers will know about map, filter/select, and inject. These are frequent in Haskell, the language makes it easy to use these. For example, you want to put two map operations together. In Ruby you’d write “list.map(&:foo).map(&:bar)” – but can you do this more directly? Haskell allows this: “map (bar.foo) list”. The dot between the functions is another important tool in Haskell – it is _function composition_, and it’s very useful for building pipelines. Returning to the example above, we can just write “unwords . map reverse . words” and get a new function from the pieces. There’s nothing special about ‘.’ either – it’s not baked into the language, but another thing we can write in vanilla Haskell, and could even redefine if we so wished – eg. to give reverse composition or even an OO-like left-to-right kind of chaining.

Some thoughts

So, a different style of language, which promotes thinking about data structures first and provides many tools to make this work. Flexibility with function types is also an important point. Sometimes, the best design for something is as a function, and the associated DSL will effectively be building a more complex function.

This flexibility does change your style of programming, and maybe can help to bring us closer to “code with obviously no defects” (Hoare). Program like you mean it!

Side effects and the real world

Some cynics may say that the real world is not about data structures, and that FP has its limits. Sorry, but everything is a piece of data; it’s a case of recognising what kind of data and finding good ways to interact with it.

Pure FP doesn’t have a notion of mutable state, but what is state? what does it mean to change state? How about this: change of state is a bit like a functional operation, mapping ‘before’ to ‘after’; and it turns out we can get a nice account of many real world ideas by wrapping up this function in an abstract interface and allowing only certain operations on it. In particular, we want precise control over the order of side effects – and this is provided by the ‘monad’ functionality in Haskell.

What do you need to know about monads? Basically, we distinguish between simple values (like those of type Int) and _actions_ or _computations_ which eventually yield some values, eg values of type “IO Int” for a side-effecting computation which produces an Int at some time. We can glue such actions together in sequences, and arrange for the output from one stage to be fed to the input of the next. Apart from this, we can use them like any other kind of value in the language, like build HOFs for them or put them in trees. We can also have different monads for state (without IO), or pure IO, or IPC, or concurrency, …

To cut a long story short, a nice bit of abstraction allows programming with side effects in a flexible yet powerful way, without it looking like a dog’s dinner. Plus, the type system helps us keep pure code and the dodgier side-effecting stuff separated.

It’s worth adding too: with a more powerful language, there’s less need for side effects. For example, most loops can be re-cast as a combination of mapping, filtering, and folding, so can be implemented with HOFs instead of nested loops and index variables. You might be surprised by how much of your code can be expressed without side-effects.

Web stuff

Again, no limits. There’s several frameworks for doing web programming in Haskell, including Yesod and HAppStack, plus libraries for individual aspects like Html processing or database interfaces. (An OReilly book on Yesod has just been released.) Some of these libraries adopt conventional approaches, kind of like a monadic veneer on top of conventional libraries, whereas others explore other approaches to web programming inside a functional setting. For example, the rack level can be programmed as a function from request to response if no side effects are needed, else as a function in some monad if various side effects are needed. Generating Html docs is easy via a Haml-like library, which is actually an embedded DSL and so can be freely mixed with other code.

OO aspects?

I’ll save this for another time. Depends what you understand by OO, and of its strengths and weaknesses. We can model a lot of the features inside FP (albeit with a bit of syntactic baggage) – objects are just another kind of data structure with a particular kind of interface. But overall, I rarely find that I need many OO features when programming in Haskell.

So what’s useful for Ruby programmers?

I think the main benefit is to be aware of the data structures that your program is manipulating, and try to write your code to bring this more to the fore; then you’ll see more functional ideas appearing quite naturally in your code.

It also helps to think about the strengths and weaknesses of your existing tools, to use their strengths and to avoid getting caught by their weaknesses.

Similar comments apply to those working with Coffeescript or similar. It does some functional stuff, but still lacks a few useful features. Anyone looked at Roy yet? It’s more Haskell-ish. (But I still want more: watch this space.)