Definición de estructuras de datos recursivas

Estoy tratando de aprender Haskell, pensando que sería el lenguaje perfecto para implementar Combinatorial Game Theory. He hecho esto hasta cierto punto en Python para enseñarme los principios de OOP y la sobrecarga de operadores, pero Haskell me atrae porque me parece más matemática en su sintaxis, y tener un conocimiento matemático me gusta mucho. Además, la implementación perezosa de listas infinitas es bastante sorprendente.Definición de estructuras de datos recursivas

De todos modos, lo que tengo hasta ahora es una estructura de datos que compila pero la primera función que he escrito usando Me da:

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.

Aquí está mi código ...

--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)

Me doy cuenta de que un juego es algo así como un árbol como se discutió en el Wikibook, pero tienen restricciones adicionales.

una posición (pariente de un nodo de árbol) puede tener muchos movimientos posibles
una posición única puede contener otros juegos
hay un juego especial, cero, que no tiene movimientos posibles.
Todos los juegos se crean utilizando Zero.

Así que cuando me escribió putL me dicen: "Tome un juego a y otro juego b y contras a en la primera parte de b, y dejar la segunda parte de b solos, volviendo a la posición (que es una tipo de juego) ". Al menos, eso es lo que intento hacer. En cambio, Haskell está pensando que el tipo que estoy devolviendo es ([Game], b0) y no sé por qué.

¡Gracias! Aprecio tu ayuda.

Fuente

2012-10-02 rev_s

No puede usar las funciones fst y snd en algo del tipo Game. Como no ha declarado nombres para sus campos en sus constructores de datos Zero y Position, la única manera de acceder realmente a ellos es a través de la coincidencia de patrones. (Tenga en cuenta que también me quita la tupla innecesario en el Position constructor)

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

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

Ahora, obviamente, no sé lo que quiere que suceda para el Zero constructor, por lo que tendrá que rellenar los ??? ' s usted mismo.

Fuente

2012-10-02 12:49:49 dflemstr

en realidad, el juego de cero ya está representado por 'Puesto [] []' lo que no hay necesidad de un constructor extra por ello . – hammar

Ya veo. Utilicé una tupla porque solo quería tener dos conjuntos de posiciones, pero eso es innecesario porque las dos listas están definidas en la estructura de datos. Y para la función, puede definir qué tipo entra como una posición, devolviendo lo que quería. –

La respuesta de dflemstr es correcta. Voy a explicar el mensaje de error que tienes.

a : fst b debe tener el tipo [Game] --- de acuerdo, ¿sí?
por lo tanto a debe tener un tipo Game ... (y lo hace, hurra)
... y fst b debe tener un tipo [Game]
fst toma un par como entrada, y produce el primer elemento del par, entonces ...
...b debe tener un tipo ([Game], b0) (por algún tipo b0 que no hemos resuelto aún) (este es el tipo espera)
esto es un problema porque de acuerdo a la firma tipo para putL, b debe tener un tipo Game (este es el tipo real ) --- no puede ser un par

Fuente

2012-10-02 13:24:58 dave4420

¡Gracias, eso se hace mucho más claro! –

Definición de estructuras de datos recursivas

Respuesta

Cuestiones relacionadas