[Haskell-cafe] Generating functions for games

[andy morris]

2009/4/4  <gwern0 at gmail.com>:
> 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.html#gadt