2009/4/4 :

So some time ago I saw mentioned the game of Zendo https://secure.wikimedia.org/wikipedia/en/wiki/Zendo_(game) as a good game for programmers to play (and not just by Okasaki). The basic idea of Zendo is that another player is creating arrangements of little colored plastic shapes and you have to guess what rule they satisfy. I thought it'd be fun to play, but not knowing anyone who has it, I figured a Haskell version would be best.

3D graphics and that sort of geometry is a bit complex, though. Better to start with a simplified version to get the fundamentals right. Why not sequences of numbers? For example: [2, 4, 6] could satisfy quite a few rules - the rule could be all evens, or it could be ascending evens, or it could be incrementing by 2, or it could just be ascending period.

Now, being in the position of the player who created the rule is no good. A good guesser is basically AI, which is a bit far afield. But it seems reasonable to have the program create a rule and provide examples. Have a few basic rules, some ways to combine them (perhaps a QuickCheck generator), and bob's your uncle.

So I set off creating a dataype. The user could type in their guessed rules and then read could be used to compare.  I got up to something like 'data Function = Not | Add' and began writing a 'translate' function, along the lines of 'translate Not = not\ntranslate Add = (+)', at which point I realized that translate was returning different types and this is a Bad Thing in Haskell. After trying out a few approaches, I decided the basic idea was flawed and sought help.

Someone in #haskell suggested GADTs, which I've never used. Before I plunge into the abyss, I was wondering: does anyone know of any existing examples of this sort of thing or alternative approachs? I'd much rather crib than create. :)

-- gwern

A simple example for this using GADTs might be: data Function a where Not :: Function (Bool -> Bool) Add :: Function (Int -> Int -> Int) ... -- BTW, type signatures are mandatory if you're using GADTs translate :: Function a -> a translate Not = not translate Add = (+) ... The important part here is the parameter to Function, and how it's made more specific in the constructors: even though you're returning values of different types from translate, it's always the same as the type the argument is parametrised over. Not to be all RTFM, but I found the example in the GHC docs quite helpful as well: http://www.haskell.org/ghc/docs/latest/html/users_guide/data-type-extensions...