[Haskell-cafe] Design in Haskell?

[Jason Dagit]

Hi Dan,

On Mon, May 25, 2009 at 1:22 AM, Dan <danielkcook at gmail.com> wrote:
> Hi,
>
> When I was learning to program in imperative languages like Java, there
> were plenty of resources to learn from about how to design large
> programs.   Ideas like the GoF Design Patterns gave useful models that
> one could then scale up.

I think GoF applies even in Haskell.

> Are there such resources for Haskell? As I'm learning the language, I'm
> finding it quite nice to write short programs (e.g. projecteuler,
> Haskell Road, etc.)  But when I try to write something a bit larger, I
> find I'm tripping over myself and having a hard time organizing the
> code coherently.

Many functional programming languages are actually multi-paradigm in
that they support object oriented designs very well.  There are a few
well known differences though.  For example, you won't find people
using the visitor pattern in Lisp/Haskell, but you will find them
using maps, folds, and "scrap your boilerplate" methods.

Even in Haskell I still find myself thinking a lot about the data
types I will use to represent the problem I'm solving; much like an
object oriented designer would.  One difference though, at this stage,
is that I think about the program as a series of transformations of
data.  I start with a representation of the input, think about how I
want to transform that, then define an intermediate representation.
This pairing of transformations and representations continues until
you have a suitable representation of the output, and then often you
just "show" it.

Think of type classes as interfaces in Java.  They even support a
restricted variation on subtyping if you chain them together.

One design pattern from the GoF book that works especially well with
Haskell is the interpreter pattern where you make a domain specific
language and solve your problems using that language.

At this point, we're just using a nice functional language the way we
program in other languages.  We can do more though.  The real deep and
interesting designs build on this space.

By exploiting laziness we can make primitives which are more
composable, so it pays to study the way laziness works.  Learn other
people's clever, lazy, solutions to those projecteuler problems. It
can help you write more orthogonal parts in your program so that more
of your program looks like a 'library' that you just happen to call.

The exploits of laziness don't stop there.  You can actually create
data structures which represent control flow abstractions due to
laziness.  Monads, especially the continuation monad, are strong
examples of this.  The beauty of representing control flow
abstractions with data structures in your language is that you can
pass them around, that is they become first class, and also you can
manipulate them.  Monad Transformers being a strong example of this.

In fact, many programs can be built by taking standard monads and
mixing them together, one for each "piece".  The easiest way to mix
monads together in this regard is to use monad transformers plus a
feature such as new type deriving.  This gives you a way to piece
together the features you want into a brand new type that hides or
renames the parts that don't make sense.  And the deriving makes it
that much easier, but is not strictly necessary.

Now, still ready to take your designs up a notch?  Well, enter type
system exploits.  There are essentially two directions you can go from
here, a) type classes b) gadts.  Oh, and now we have type families, so
three directions these days.  Using the above you can do all manner of
things, some of which can be turing complete or cause the type checker
to fail to terminate.  People tend to refer to type hackery in units
known as Olegs, with most of us doing just a millioleg design here and
there.  We applied gadt style type hackery in the darcs source code to
remove an entire class of bug, mainly the ones that result from
incorrectly manipulating a sequence of patches.  My thesis explains
the approach we took:
http://blog.codersbase.com/2009/03/25/type-correct-changes-a-safe-approach-to-version-control-implementation/

> Are there any suggestions of wikis, books or particularly
> well-architected and readable projects I could look at to about learn
> larger-scale design in Haskell?

The best advice I can give you, is read/participate on haskell-cafe
and #haskell on irc.freenode.net, and to read the proceedings from
ICFP.  Some really beautiful papers have come out of ICFP over the
years and most of them are quite easy to find on google if you just
look over the list of which papers were presented each year.

This paper is one that I highly recommend.  It teaches you, step by
step, how to stack monads (using transformers) to develop a nice fully
featured evaluator:
http://user.cs.tu-berlin.de/~magr/pub/Transformers.en.html

If you scroll down a bit this page links to all lists of papers
presented at each ICFP:
http://www.icfpconference.org/

Just go over that list and see what you can find on google.  It really
pays to read those papers because too few people have written haskell
books.  But, if you want a book, perhaps you should try Real-World
Haskell?  It is available online:
http://book.realworldhaskell.org/read/

Good luck!
Jason