Ist dieser inkrementelle Parser ein Funktor, wenn ja, wie würde `fmap` implementiert?

Question

Ich hasse es wirklich, diese Art von Frage zu stellen, aber ich bin am Ende meiner Weisheit hier. Ich schreibe einen inkrementellen Parser, aber aus irgendeinem Grund kann ich einfach nicht herausfinden, wie man funktor-Instanz dafür implementiert. Hier ist der Code dump:

Eingang Datentyp

Eingangsdatentyp durch Parser an den Koroutine ergibt. Es enthält die aktuelle Liste der Eingangs Zeichen von Koroutine und Zeilenende Bedingung

data Input a = S [a] Bool deriving (Show) 

instance Functor Input where 
    fmap g (S as x) = S (g <$> as) x 

Ausgangsdatentyp betrieben werden Datentyp

Ausgabe von Koroutine zu Parser ergibt. Es ist entweder ein Fehler bei Nachricht, Fertig [b] oder Partial ([a] -> Ausgabe ab), wobei [a] der aktuelle Puffer zurück an den Parser übergeben wird

data Output a b = Fail String | Done [b] | Partial ([a] -> Output a b) 

instance Functor (Output a) where 
    fmap _ (Fail s) = Fail s 
    fmap g (Done bs) = Done $ g <$> bs 
    fmap g (Partial f) = Partial $ \as -> g <$> f as 

Der Parser

Der Parser nimmt [a] und ergibt einen Puffer [a] bis Koroutine, welcher Ausgang AB ergibt zurück

data ParserI a b = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b } 

Functor Implementation

Es scheint, wie alles, was ich zu tun haben, die Funktion g auf die Koroutine wird FMAP, wie folgt:

instance Functor (ParserI a) where 
    fmap g p = PP $ \as k -> runPi p as (\xs -> fmap g $ k xs) 

Aber es prüft jedoch nicht Typ:

Couldn't match type `a1' with `b' 
    `a1' is a rigid type variable bound by 
     the type signature for 
     fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b 
     at Tests.hs:723:9 
    `b' is a rigid type variable bound by 
     the type signature for 
     fmap :: (a1 -> b) -> ParserI a a1 -> ParserI a b 
     at Tests.hs:723:9 
Expected type: ParserI a b 
    Actual type: ParserI a a1 

Answer 1

Als Philip JF erklärt, ist es nicht möglich, eine instance Functor (ParserI a) zu haben. Der Beweis geht nach der Varianz der Funktoren - jeder (mathematische) Funktor muss für jedes seiner Argumente entweder kovariant oder kontravariant sein. Normale Haskell Functor s immer covariant sind, welche, warum ist

fmap :: (a -> b) -> (f a -> f b)` 

Haskell Contravariant functors die ähnliche

contramap :: (b -> a) -> (f a -> f b)` 

In Ihrem Fall haben die b Index in ParserI a b hätte sowohl kovarianten und kontra sein. Der schnelle Weg, dies herauszufinden, besteht darin, kovariante Positionen mit + und kontravariant mit - in Beziehung zu setzen und aus einigen Grundregeln zu bauen.

Kovariante Positionen sind Funktionsergebnisse, Kontravariante sind Funktionseingaben. So hat ein Typ Mapping wie type Func1 a b c = (a, b) -> ca ~ -, b ~ - und c ~ +. Wenn Sie in Ausgabepositionen Funktionen haben, multiplizieren Sie alle Argumentvarianzen durch +1. Wenn Sie Funktionen in Eingabe Positionen haben, multiplizieren Sie alle Abweichungen durch -1.So

type Func2 a b c = a -> (b -> c) 

hat die gleichen Varianzen wie Func1 aber

type Func3 a b c = (a -> b) -> c 

a ~ 1 hat, b ~ -1 und c ~ 1. Mit diesen Regeln können Sie sehr schnell sehen, dass Varianzen wie Output - + und dann ParserIOutput sowohl in negativen als auch positiven Positionen verwendet, so kann es nicht eine gerade Functor sein.

---

Aber es gibt Verallgemeinerungen wie Contravariant. Die besondere Verallgemeinerung von Interesse ist Profunctor (oder Difunctor s, die man manchmal sehen), die wie so geht

class Profunctor f where 
    promap :: (a' -> a) -> (b -> b') -> (f a b -> f a' b') 

das Beispiel für das Sein (->)

instance Profunctor (->) where 
    promap f g orig = g . orig . f 

heißt es „erweitert“ die Funktion sowohl nach (wie üblich Functor) und vorher. Profunctor s f sind somit immer mathematische Funktoren der Arity 2 mit Varianzsignatur f - +.

Also, indem Sie Ihre ParserI leicht verallgemeinern, lassen Sie dort einen zusätzlichen Parameter, um die Ausgabetypen in zwei Hälften zu teilen, können wir es zu einem Profunctor machen.

data ParserIC a b b' = PP { runPi :: [a] -> (Input a -> Output a b) -> Output a b' } 

instance Profunctor (ParserIC a) where 
    promap before after (PP pi) = 
    PP $ \as k -> fmap after $ pi as (fmap before . k) 

und dann können Sie es wickeln

type ParserI a b = ParserIC a b b 

und bieten eine etwas weniger bequem Abbildungsfunktion über b

mapPi :: (c -> b) -> (b -> c) -> ParserI a b -> ParserI a c 
mapPi = promap 

, die wirklich zu Hause die Last treibt, die die Varianzen beide gehen Wege --- Sie müssen bidirektionale Karten haben!