Defining recursive data structures

Question

I'm trying to learn Haskell, thinking that it would be the perfect language to implement Combinatorial Game Theory. I've done this to some extent in Python to teach myself OOP principles and operator overloading, but Haskell attracts me because it seems more mathematical in its syntax, and having a math background I really like that. Also, having lazily implemented infinite lists is pretty amazing.

Anyway, what I have so far is a data structure that compiles but the first function I've written using it gives me:

Prelude> :l cgt
[1 of 1] Compiling Main             ( cgt.hs, interpreted )

cgt.hs:8:30:
    Couldn't match expected type `([Game], b0)' with actual type `Game'
    In the first argument of `fst', namely `b'
    In the second argument of `(:)', namely `(fst b)'
    In the expression: a : (fst b)
    Failed, modules loaded: none.

Here is my code...

--A game that is Zero (base case) is two empties
--Anything else must be two lists of games, a left list and a right list.

data Game = Zero
          | Position ([Game], [Game])

putL :: Game -> Game -> Game
putL a b = Position (a :(fst b), snd b)

I realize that a Game is somewhat like a Tree as discussed on the Wikibook , but they have additional restrictions.

1. A Position (kin to a tree node) can have many possible moves
2. A Position may only contain other Games
3. There is a special Game, Zero, that has no possible moves.
4. All games are built up using Zero.

So when I wrote putL I say, "Take a Game a and another Game b, and cons a into the first part of b, and leave the second part of b alone, returning a Position (which is a kind of Game)." At least, that is what I am trying to do. Instead Haskell is thinking the type I'm returning is ([Game], b0) and I don't know why.

Thank you! I appreciate your help.

Answer 1

dflemstr's answer is correct. I am going to explain the error message you got.

• a : fst b must have type [Game] --- agreed, yes?
• therefore a must have type Game... (and it does, hooray)
• ...and fst b must have type [Game]
• fst takes a pair as input, and yields the first element of the pair, so...
• ...b must have type ([Game], b0) (for some type b0 that we haven't worked out yet) (this is the expected type)
• this is a problem because according to the type signature for putL, b must have type Game (this is the actual type) --- it can't be a pair

Answer 2

You can't use the fst and snd functions on something of type Game. Since you haven't declared names for your fields in your data constructors Zero and Position, the only way to actually access them is via pattern matching. (Note that I also removed the unnecessary tuple in the Position constructor)

data Game
  = Zero
  | Position [Game] [Game]

putL :: Game -> Game -> Game
putL game Zero = ???
putL game (Position games1 games2) = Position (game : games1) games2

Now, I obviously don't know what you want to happen for the Zero constructor, so you'll have to fill in those ???'s yourself.