personnalisé par exemple Functor: type attendu '* -> *', mais 'AST' a en quelque sorte '*'

Question

Je cette ADT assez simple:

data AST = Node String [AST] 
    | Leaf String 
    | Empty 
    deriving (Show) 

et cette instance Functor:

instance Functor AST where 
    fmap f (Node s l) = Node (f s) (fmap f l) 
    fmap f (Leaf s) = Leaf (f s) 
    fmap f Empty  = Empty 

Mais lorsque je tente de compiler je reçois cette erreur que je ne comprends pas tout à fait:

Expected kind ‘* -> *’, but ‘AST’ has kind ‘*’ 
    • In the first argument of ‘Functor’, namely ‘AST’ 
    In the instance declaration for ‘Functor AST’ 

Est-ce que quelqu'un sait pourquoi cela se produit? Je ne peux pas trouver une solution sur Internet.

Answer 1

Un foncteur travaille sur constructeurs de type: si vous donnez un AST, il attend de voir:

data AST a = ... 
--  ^type parameter

On peut aussi voir dans la définition de la classe Functor:

class Functor (f :: * -> *) where 
    fmap :: (a -> b) -> f a -> f b

Notez que le f dans la tête de la classe a "kind" * -> * cela signifie qu'il agit comme une sorte de fonction qui prend un autre type (le premier *) et produit un type (le second *). Comme vous pouvez le voir fmap prendra une fonction de type a -> b (où nous n'avons pas beaucoup de contrôle sur ce que b est). Dans votre définition de fmap, nous pouvions seulement fournir une fonction String -> String.

À l'heure actuelle, cela n'a pas beaucoup de sens de faire de AST un foncteur, puisqu'il ne s'agit pas d'un foncteur.

Vous pouvez cependant facilement votre AST généralisez dans:

data AST a = Node a [AST a] 
    | Leaf a 
    | Empty 
    deriving (Show)

Si vous travaillez avec ce type, un AST String est équivalent à votre ancienne définition pour un AST. Il en va de même pour la liste [] (qui est également Functor). Un pseudo -définition d'une liste est la suivante:

data [] a = [] | a : [a] 

Nous définissons Functor sur une liste comme:

instance Functor [] where 
    fmap _ [] = [] 
    fmap f (x:xs) = (f x) : (fmap f xs)

esprit que nous avons fait pas état Functor [a], mais Functor [].

Answer 2

Les foncteurs doivent être polymorphes, c'est-à-dire data AST a = .... C'est ce que "genre" signifie dans ce cas. Il veut AST ne pas être un type, mais une fonction de type, en prenant un type et en retournant un type.