Typeclass d'un type paramétré

... quelle syntaxe ?

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Salut,

J'essaye de faire l'algorithme A* en Haskell pour m'entraîner. Dans cet algorithme on a "besoin" de piles. Du coup, je fais un mini module qui implémente celles ci en Haskell. Le souci c'est que mes types sont paramétrés (e.g. PriorityQueue Int ou FIFOQueue String, etc…) et que je bloque un peu sur la syntaxe des instances de ma typeclass Queue. Voici le code (complet):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
module Data.Queue (
    Queue,
    FIFOQueue,
    LIFOQueue,
    Deque,
    PriorityQueue
) where

import Data.List (maximumBy)

class Queue q where
    get :: q a -> a
    put :: a -> q a -> q a

data FIFOQueue     a = FIFOQueue     [a]          deriving (Show, Eq)
data LIFOQueue     a = LIFOQueue     [a]          deriving (Show, Eq)
data Deque         a = Deque         [a]          deriving (Show, Eq)
data PriorityQueue a = PriorityQueue [(a, Float)] deriving (Show, Eq)

instance Queue (FIFOQueue a) where
    get (FIFOQueue xs) = FIFOQueue $ head xs
    put elt (FIFOQueue xs) = FIFOQueue $ elt : xs

instance Queue (LIFOQueue a) where
    get (LIFOQueue xs) = LIFOQueue $ head xs
    put elt (LIFOQueue xs) = LIFOQueue $ xs ++ [elt]

instance Queue (Deque a) where
    get = popLast
    put elt (Deque xs) = Deque $ elt : xs

popLast, popFirst :: Deque a -> a
popLast (Deque xs) = Deque $ init xs
popFirst (Deque xs) = Deque $ tail xs

instance Queue (PriorityQueue a) where
    get (PriorityQueue xs) = maximumBy $ (compare . snd) xs
    put elt (PriorityQueue xs) = PriorityQueue $ elt : xs

… et voici l'erreur du compilateur:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
Data\Queue.hs:20:17:
    The first argument of `Queue' should have kind `* -> *',
      but `FIFOQueue a' has kind `*'
    In the instance declaration for `Queue (FIFOQueue a)'

Data\Queue.hs:24:17:
    The first argument of `Queue' should have kind `* -> *',
      but `LIFOQueue a' has kind `*'
    In the instance declaration for `Queue (LIFOQueue a)'

Data\Queue.hs:28:17:
    The first argument of `Queue' should have kind `* -> *',
      but `Deque a' has kind `*'
    In the instance declaration for `Queue (Deque a)'

Data\Queue.hs:36:17:
    The first argument of `Queue' should have kind `* -> *',
      but `PriorityQueue a' has kind `*'
    In the instance declaration for `Queue (PriorityQueue a)'

Quelle syntaxe devrai-je écrire ?

Merci d'avance,

AZ.

PS: ça n'a rien à voir, mais je viens de terminer un 2048 en mode console, j'aimerais le porter en mode graphique. Vous me conseillez quelle librairie graphique ?

Édité par felko

Anciennement AlphaZeta

+0 -0

Cette réponse a aidé l'auteur du sujet

Comme tu as écrit class Queue q, tout type appartenant à la classe de types Queue est un type qui prend un autre type "en paramètre", autrement dit, c'est un type de kind * -> *(vois ça comme pour les signatures de fonctions, un type qui prend un type et qui retourne un type). GHC couine parce que par exemple, FIFOQueue aest de kind * alors que pour appartenir à la classe de types Queue, il faut avoir un kind de *-> *.
La solution est donc d'écrire:

1
2
3
instance Queue FIFOQueue where
    get (FIFOQueue xs) = FIFOQueue $ head xs
    put elt (FIFOQueue xs) = FIFOQueue $ elt : xs
+1 -0

Cette réponse a aidé l'auteur du sujet

EDIT : Grimur a répondu à peu près pareil, mais j'envoie quand même.

Alors, si je ne dis pas de bêtise, il y a deux problèmes.

Premièrement, quand tu définis ta classe…

1
2
3
class Queue q where
    get :: q a -> a
    put :: a -> q a -> q a

q est un type paramétré, puisqu'il admet d'être précisé en q a. En revanche, lorsque tu définis tes instances, comme dans…

1
instance Queue (FIFOQueue a) where

…tu fournis au constructeur d'instance un type concret. Pour régler ce problème, il faut supprimer le a de toutes tes déclarations d'instances.

Mais alors, tu vas rencontrer une deuxième batterie d'erreurs, et c'est mon deuxièmement. Prenons ta première instance, mais c'est valable pour toutes.

1
2
3
instance Queue (FIFOQueue) where
    get = head
    put = (:)

D'après la définition de la classe de types, get est de type FIFOQueue a -> a. Mais head est de type [a] -> a, donc GHC gueule. Pour régler ce problème, il faut que tu définisses tes fonctions d'accès et d'ajout de manière à pouvoir accéder à la liste qui est à l'intérieur de chacune de tes QueueQQCH a. Pour ça, il te faudra définir des fonctions qui permettent de faire QueueQQCH a -> [a] et [a] -> QueueQQCH a, sinon, ça ne peut pas marcher.

Je t'invite à lire un bon article sur les monades pour mieux comprendre ce deuxième point.

#JeSuisGrimur #OnVautMieuxQueÇa

+1 -0

Ah oui, bien vu pour le second point Dominus, j'avais pas fait attention.

EDIT: tu recommandes de lire un guide sur les monades parce que Monad est un type d'ordre supérieur, c'est ça ? Ou parce que le type liste est une monade ?

Édité par anonyme

+0 -0
Auteur du sujet

D'après la définition de la classe de types, get est de type FIFOQueue a -> a. Mais head est de type [a] -> a, donc GHC gueule. Pour régler ce problème, il faut que tu définisses tes fonctions d'accès et d'ajout de manière à pouvoir accéder à la liste qui est à l'intérieur de chacune de tes QueueQQCH a. Pour ça, il te faudra définir des fonctions qui permettent de faire QueueQQCH a -> [a] et [a] -> QueueQQCH a, sinon, ça ne peut pas marcher.

Dominus Carnufex

Merci pour ta réponse, quand j'ai écris mon premier post, je me suis rendu compte que c'était n'importe quoi, donc j'ai édité mais tu as été plus rapide que moi :)

Comme tu as écrit class Queue q, tout type appartenant à la classe de types Queue est un type qui prend un autre type "en paramètre", autrement dit, c'est un type de kind * -> *(vois ça comme pour les signatures de fonctions, un type qui prend un type et qui retourne un type). GHC couine parce que par exemple, FIFOQueue aest de kind * alors que pour appartenir à la classe de types Queue, il faut avoir un kind de *-> *.
La solution est donc d'écrire:

1
2
3
instance Queue FIFOQueue where
    get (FIFOQueue xs) = FIFOQueue $ head xs
    put elt (FIFOQueue xs) = FIFOQueue $ elt : xs

Grimur

Merci beacoup Grimur, il n'y a plus l'erreur. Cependant une autre est levée par GHC, j'étudie le truc et je vous tiens au courant

Merci à vous pour vos réponses <3

Anciennement AlphaZeta

+0 -0
Auteur du sujet

Salut,

Désolé de ne pas avoir répondu plus tôt, la nouvelle erreur était facile à régler et n'avait aucun rapport avec mon problème. Finalement je n'ai pas utilisé le code mais ça m'a permis de progresser. Étant encore au début de mon apprentissage de Haskell, je n'ai pas encore lu de tutoriel sur les monades, mais je vois bien que c'est une notion importante.

Sinon vous avez des recommandations pour une librairie graphique de préférence réactive (j'ai entendu parler de la FRP et de Yampa) ? Je passe tout de même le sujet en résolu, merci encore.

Anciennement AlphaZeta

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte