Wie gebe ich eine Funktor-Instanz an einen Datentyp, der für allgemeine Rekursionssysteme erstellt wurde?

Question

Ich habe einen rekursiven Datentypen, die eine Functor Instanz hat:

data Expr1 a 
    = Val1 a 
    | Add1 (Expr1 a) (Expr1 a) 
    deriving (Eq, Show, Functor) 

Nun, ich habe Interesse an Änderung dieser Datentyp zu unterstützen allgemeine Rekursion-Schemata, wie sie beschrieben sind in this tutorial und this Hackage package. Ich schaffte es die catamorphism zur Arbeit zu kommen:

newtype Fix f = Fix {unFix :: f (Fix f)} 

data ExprF a r 
    = Val a 
    | Add r r 
    deriving (Eq, Show, Functor) 

type Expr2 a = Fix (ExprF a) 

cata :: Functor f => (f a -> a) -> Fix f -> a 
cata f = f . fmap (cata f) . unFix 

eval :: Expr2 Int -> Int 
eval = cata $ \case 
    Val n -> n 
    Add x y -> x + y 

main :: IO() 
main = 
    print $ eval 
    (Fix (Add (Fix (Val 1)) (Fix (Val 2)))) 

Aber jetzt kann ich nicht herausfinden, wie Expr2 das gleiche Funktors Beispiel zu geben, dass die ursprünglichen Expr hatte. Es scheint, es ist eine Art Nichtübereinstimmung ist beim Versuch, die Funktors Instanz zu definieren:

instance Functor (Fix (ExprF a)) where 
    fmap = undefined 

Kind mis-match 
    The first argument of `Functor' should have kind `* -> *', 
    but `Fix (ExprF a)' has kind `*' 
    In the instance declaration for `Functor (Fix (ExprF a))' 

Wie schreibe ich eine Functor Instanz für Expr2?

Ich dachte über Ausdr2 in einem newtype mit newtype Expr2 a = Expr2 (Fix (ExprF a)) Einwickeln aber dann muss diese newtype ausgepackt werden, um cata weitergegeben werden, was ich nicht sehr gut gefällt. Ich weiß auch nicht, ob es möglich wäre, die Funktorinstanz Expr2 automatisch so abzuleiten, wie ich es mit Expr1 gemacht habe.

Answer 1

Ich frage mich, ob Sie vielleicht besser dran mit dem Free Typ:

data Free f a 
    = Pure a 
    | Wrap (f (Free f a)) 
deriving Functor 

data ExprF r 
    = Add r r 
deriving Functor 

Dies hat den zusätzlichen Vorteil, dass es durchaus ein paar Bibliotheken, die bereits auf freien Monaden arbeiten, vielleicht werden sie dich retten etwas Arbeit.

Answer 2

Das Schlüsselwort Typ nur als Synonym eines bestehenden Typs verwendet wird, vielleicht ist es das, was Sie suchen

newtype Expr2 a r = In { out :: (ExprF a r)} deriving Functor 

Answer 3

Dies ist eine alte Wunde für mich. Der entscheidende Punkt ist, dass Ihre ExprF ist in seine Parameter functorial ist. Wenn wir also

class Bifunctor b where 
    bimap :: (x1 -> y1) -> (x2 -> y2) -> b x1 x2 -> b y1 y2 

hatte dann könnte man definieren (oder eine Maschine für Sie definieren sich vorstellen)

instance Bifunctor ExprF where 
    bimap k1 k2 (Val a) = Val (k1 a) 
    bimap k1 k2 (Add x y) = Add (k2 x) (k2 y) 

und jetzt können Sie

newtype Fix2 b a = MkFix2 (b a (Fix2 b a)) 

von

map1cata2 :: Bifunctor b => (a -> a') -> (b a' t -> t) -> Fix2 b a -> t 
map1cata2 e f (MkFix2 bar) = f (bimap e (map1cata2 e f) bar) 

begleitet haben

was wiederum gibt Ihnen das w hen Sie in einem der Parameter ein Fixpunkt nehmen, was noch übrig bleibt, ist funktoriellen in der anderen

instance Bifunctor b => Functor (Fix2 b) where 
    fmap k = map1cata2 k MkFix2 

und sortieren Sie von dem, was man wollte. Aber Ihre Bifunctor Instanz wird nicht durch Magie gebaut werden. Und es ist ein bisschen nervig, dass Sie einen anderen Fixpunktoperator und eine ganz neue Art von Funktor benötigen. Das Problem ist, dass Sie jetzt zwei Arten von Substruktur haben: "Werte" und "Teilausdrücke".

Und hier ist die Wende. Es gibt eine Vorstellung von Funktor, der unter Fixpoints geschlossen ist.Schalten Sie die Küchenspüle (insbesondere DataKinds) und

type s :-> t = forall x. s x -> t x 

class FunctorIx (f :: (i -> *) -> (o -> *)) where 
    mapIx :: (s :-> t) -> f s :-> f t 

Beachten Sie, dass „Elemente“ kommen in einer Art indiziert über i und „Strukturen“ in einer Art über einen anderen o indiziert. Wir nehmen i -Erhalt Funktionen auf Elemente zu o Erhaltung Funktionen auf Strukturen. Entscheidend ist, dass i und o unterschiedlich sein können.

Die magischen Worte sind "1, 2, 4, 8, Zeit zu potenzieren!". Eine Art von Art * kann leicht in eine trivial indexierte GADT der Art () -> * umgewandelt werden. Und zwei Arten können zusammengerollt werden, um eine GADT der Art Either()() -> * zu bilden. Das bedeutet, dass wir beide Arten von Unterstrukturen zusammen rollen können. In der Regel haben wir eine Art von Typ either.

data Case :: (a -> *) -> (b -> *) -> Either a b -> * where 
    CL :: f a -> Case f g (Left a) 
    CR :: g b -> Case f g (Right b) 

mit seinem Begriff der "Karte" ausgestattet

mapCase :: (f :-> f') -> (g :-> g') -> Case f g :-> Case f' g' 
mapCase ff gg (CL fx) = CL (ff fx) 
mapCase ff gg (CR gx) = CR (gg gx) 

So können wir unsere bifactors refunctor als EitherFunctorIx Instanzen -indexed.

Und jetzt können wir den Fixpunkt von jeder Knotenstruktur f nehmen, die Plätze für entweder Elemente oder Unterknoten hat. Es ist genau der gleiche Deal, den wir oben hatten.

newtype FixIx (f :: (Either i o -> *) -> (o -> *)) 
       (p :: i -> *) 
       (b :: o) 
    = MkFixIx (f (Case p (FixIx f p)) b) 

mapCata :: forall f p q t. FunctorIx f => 
    (p :-> q) -> (f (Case q t) :-> t) -> FixIx f p :-> t 
mapCata e f (MkFixIx node) = f (mapIx (mapCase e (mapCata e f)) node) 

Aber jetzt bekommen wir die Tatsache, dass FunctorIx unter FixIx geschlossen ist.

instance FunctorIx f => FunctorIx (FixIx f) where 
    mapIx f = mapCata f MkFixIx 

Funktoren auf indizierte Sätzen (mit der zusätzlichen Freiheit, den Index zu variieren) kann sehr präzise sein und sehr mächtig. Sie genießen viel bequemere Verschlusseigenschaften als Functor s tun. Ich nehme nicht an, dass sie es verstehen.

Answer 4

Nichts falsch mit pigworker Antwort, aber vielleicht können Sie eine einfachere als Sprungbrett verwenden:

{-# LANGUAGE DeriveFunctor, ScopedTypeVariables #-} 

import Prelude hiding (map) 

newtype Fix f = Fix { unFix :: f (Fix f) } 

-- This is the catamorphism function you hopefully know and love 
-- already. Generalizes 'foldr'. 
cata :: Functor f => (f r -> r) -> Fix f -> r 
cata phi = phi . fmap (cata phi) . unFix 

-- The 'Bifunctor' class. You can find this in Hackage, so if you 
-- want to use this just use it from there. 
-- 
-- Minimal definition: either 'bimap' or both 'first' and 'second'. 
class Bifunctor f where 
    bimap :: (a -> c) -> (b -> d) -> f a b -> f c d 
    bimap f g = first f . second g 

    first :: (a -> c) -> f a b -> f c b 
    first f = bimap f id 

    second :: (b -> d) -> f a b -> f a d 
    second g = bimap id g 

-- The generic map function. I wrote this out with 
-- ScopedTypeVariables to make it easier to read... 
map :: forall f a b. (Functor (f a), Bifunctor f) => 
     (a -> b) -> Fix (f a) -> Fix (f b) 
map f = cata phi 
    where phi :: f a (Fix (f b)) -> Fix (f b) 
      phi = Fix . first f 

Jetzt arbeitet Ihre Ausdruckssprache wie folgt aus:

-- This is the base (bi)functor for your expression type. 
data ExprF a r = Val a 
       | Add r r 
       deriving (Eq, Show, Functor) 

instance Bifunctor ExprF where 
    bimap f g (Val a) = Val (f a) 
    bimap f g (Add l r) = Add (g l) (g r) 

newtype Expr a = Expr (Fix (ExprF a)) 

instance Functor Expr where 
    fmap f (Expr exprF) = Expr (map f exprF) 

EDIT: Hier ist ein Link zu der bifunctors package in Hackage.