Benutzerdefinierte Functor Beispiel: Erwartete Art '* -> *', sondern 'AST' hat Art '*'

Question

Ich habe diese recht einfache ADT:

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

und dieses Functor Beispiel:

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 

Aber wenn ich versuche, es zu kompilieren ich diesen Fehler, die ich absolut nicht verstehen:

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

weiß jemand, warum dies geschieht? Ich kann im Internet keine Lösung finden.

Answer 1

A Funktors arbeitet auf Typkonstruktoren: Wenn Sie es ein AST geben, es zu sehen erwartet:

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

wir auch diese in der Definition der Functor Klasse sehen:

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

Beachten Sie, dass die f in der Spitze der Klasse hat „Art“ * -> * Dies bedeutet, dass fungiert als eine Art von Funktion, die einen anderen Typ (die erste *) und produziert einen Typ (die zweite *). Wie Sie sehen können fmap wird eine Funktion des Typs a -> b (wo wir nicht viel Kontrolle über was b ist) nehmen. In Ihrer Definition von fmap konnten wir nur eine String -> String Funktion bereitstellen.

Gerade jetzt macht es nicht viel Sinn, AST einen Funktor zu machen, da es kein Funktor ist.

Sie können jedoch leicht verallgemeinern Ihre AST in:

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

Wenn Sie mit dieser Art arbeiten, ein AST String für eine AST zu Ihrer alten Definition entspricht.

Das gleiche gilt für eine Liste [] (die auch eine Functor ist). Ein Pseudo -Definition einer Liste ist:

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

Wir definieren Functor über eine Liste wie:

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

daran, dass wir nicht Zustand Functor [a] tat, aber Functor [].

Answer 2

Funktoren müssen polymorph sein, dh . Das ist was "gut" in diesem Fall bedeutet. Es will AST nicht ein Typ sein, sondern eine Typ-Funktion, die einen Typ nimmt und einen Typ zurückgibt.