Gibt es eine Verallgemeinerung dieser Free-ähnlichen Konstruktionen?

Question

Ich spiele mit Frei wie Ideen um und fand diese:

{-# LANGUAGE RankNTypes #-} 

data Monoid m = Monoid { mempty :: m, mappend :: m -> m -> m } 
data Generator a m = Generator { monoid :: Monoid m, singleton :: a -> m } 

newtype Free f = Free { getFree :: forall s. f s -> s } 

mkMonoid :: (forall s. f s -> Monoid s) -> Monoid (Free f) 
mkMonoid f = Monoid { 
    mempty = Free (mempty . f), 
    mappend = \a b -> Free $ \s -> mappend (f s) (getFree a s) (getFree b s) 
} 

freeMonoid :: Monoid (Free Monoid) 
freeMonoid = mkMonoid id 

mkGenerator :: (forall s. f s -> Generator a s) -> Generator a (Free f) 
mkGenerator f = Generator { 
    monoid = mkMonoid (monoid . f), 
    singleton = \x -> Free $ \s -> singleton (f s) x 
} 

freeGenerator :: Generator a (Free (Generator a)) 
freeGenerator = mkGenerator id 

Ich mag die Bedingungen finden, unter denen ich einen funcion schreiben konnte:

mkFree :: (??? f) => f (Free f) 

aber ich habe nicht in der Lage gewesen, um eine sinnvolle Struktur für f zu finden (eine andere als die triviale, in der mkFree eine Methode von ??? ist), die es ermöglichen würde, diese Funktion zu schreiben. Insbesondere würde mein ästhetischer Sinn bevorzugen, wenn diese Struktur den Free Typ nicht erwähnt.

Hat jemand so etwas schon mal gesehen? Ist diese Verallgemeinerung möglich? Gibt es eine bekannte Verallgemeinerung in eine Richtung, an die ich noch nicht gedacht habe?

Answer 1

Die Verbindung zur universellen Algebra war ein guter Ausgangspunkt, und nachdem wir etwas darüber gelesen hatten, passte alles zusammen. Was wir suchen ist ein F-Algebra:

type Alg f x = f x -> x 

für jede (endo) Funktors f. Zum Beispiel für eine Monoid Algebra des Funktor ist:

data MonoidF m = MEmpty | MAppend m m deriving Functor 

Für Monoid Beispiel gibt es die offensichtliche Monoid Algebra:

monoidAlg :: Monoid m => Alg MonoidF m 
monoidAlg MEmpty = mempty 
monoidAlg (MAppend a b) = mappend a b 

Jetzt können wir die freie Funktors Definition von dem Frei functors Paket nehmen, und ersetzen Sie die Klasse Constraint mit dem f-Algebra:

newtype Free f a = Free { runFree :: forall b. Alg f b -> (a -> b) -> b } 

der freie Funktors in gewissem Sinne ist der beste Weg, sich keine weiterführende Haftung a in ein al drehen gebra. Dies ist, wie:

unit :: a -> Free f a 
unit a = Free $ \_ k -> k a 

Es ist der beste Weg ist, weil für jede andere Art und Weise a in eine Algebra b drehen wir eine Funktion aus der freien Algebra b geben kann:

rightAdjunct :: Functor f => Alg f b -> (a -> b) -> Free f a -> b 
rightAdjunct alg k (Free f) = f alg k 

Was ist links ist, zeigen tatsächlich, dass der freie Funktors einen f-Algebra erzeugt (und das ist das, was Sie gefragt):

freeAlg :: Functor f => Alg f (Free f a) 
freeAlg ff = Free $ \alg k -> alg (fmap (rightAdjunct alg k) ff) 

ein wenig zu erklären: ff ist vom Typ f (Free f a) und wir müssen eine Free f a bauen. Wir können das tun, wenn wir eine b, gegeben alg :: f b -> b und k :: a -> b bilden können. So können wir alg auf ff anwenden, wenn wir jede Free f a, die es enthält, auf eine b abbilden können, aber das ist genau das, was rightAdjunct mit alg und k tut.

Wie Sie vielleicht schon erraten haben, diese Free f ist das kostenlose Monade auf dem Funktors f

instance Functor f => Monad (Free f) where 
    return = unit 
    m >>= f = rightAdjunct freeAlg f m