[Haskell-cafe] Re: How Albus Dumbledore would sell Haskell

[DavidA]

Simon Peyton-Jones <simonpj <at> microsoft.com> writes:

> But, just to remind you all: I'm particularly interested in
> 
>   concrete examples (pref running code) of programs that are
>        * small
>        * useful
>        * demonstrate Haskell's power
>        * preferably something that might be a bit
>                tricky in another language

I have something that I think nearly fits the bill. Unfortunately, I don't 
think it quite works because it's a bit specialised. However, I think it 
suggests a possible area to look, which I'll mention at the end.

It's a theorem prover for intuitionistic propositional logic:
http://www.polyomino.f2s.com/david/haskell/gentzen.html

It's much shorter in Haskell than it would be in other languages. (It's even 
shorter than the ML that I based it on, because of some shortcuts I can take 
using lazy evaluation.)

Strengths of Haskell that it demonstrates are:
* How easy it is to define datatypes (eg trees), and manipulate them using 
pattern matching, with constructors, Eq, Show coming for free.
* How lazy evaluation reduces code length by letting you write code that looks 
like it would do too much, and then lazy evaluate it (in the "proof" function)
* The ability to extend the syntax with new symbolic operators
* Use of higher order functions to simplify code (the (+++) operator)

The problem is that I think Gentzen systems are a bit obscure. But I think you 
could probably show most of the same strengths of Haskell in something 
similar: game search, eg alpha-beta algorithm. Another advantage of doing game 
search would be that you'd get to show off persistent data structures (so that 
when you make a move in lookahead, you don't need to make a copy of the game 
state, because when you update the game state the old state still persists).