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.

A Position (kin to a tree node) can have many possible moves
A Position may only contain other Games
There is a special Game, Zero, that has no possible moves.
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.

dflemstr · Accepted Answer · 2012-10-02 12:49:49Z

10

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.

answered Oct 2, 2012 at 12:49

dflemstr

26.3k5 gold badges74 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

hammar Over a year ago

Actually, the zero game is already represented by Position [] [] so there is no need for an extra constructor for it.

rev_s Over a year ago

I see. I used a tuple because I only wanted to have two sets of positions, but that is unnecessary because the two lists are defined in the data structure. And for the function, you can define what type goes in as a position, returning what I wanted.

dave4420 · Accepted Answer · 2012-10-02 13:24:58Z

6

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

answered Oct 2, 2012 at 13:24

dave4420

47.2k6 gold badges121 silver badges153 bronze badges

Collectives™ on Stack Overflow

Defining recursive data structures

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related