Есть ли обобщение этих Free-подобных конструкций?

Question

Я играл вокруг с свободной, как идеи, и нашел это:

{-# 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 

Я хотел бы найти условия, при которых я мог бы написать несильно:

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

, но я не смог найти значимую структуру для f (кроме тривиальной, в которой mkFree - это метод ???), который позволил бы записать эту функцию. В частности, мой эстетический смысл предпочел бы, если бы эта структура не упоминала тип Free.

Кто-нибудь видел что-то подобное раньше? Возможно ли это обобщение? Есть ли известное обобщение в том направлении, о котором я еще не думал?

Answer 1

Ссылка на универсальную алгебру была хорошей отправной точкой, и после прочтения ее немного все встало на свои места. Что мы ищем это F-алгебра:

type Alg f x = f x -> x 

для любого (эндо) функтора f. Например, для алгебры Monoid функтора:

data MonoidF m = MEmpty | MAppend m m deriving Functor 

Для любого Monoid экземпляра есть очевидная Моноид алгебра:

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

Теперь мы можем взять свободное определение функтора из пакета свободных функторов, и заменить ограничение класса с ф-алгеброй:

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

свободный функтор в некотором смысле лучшим способ превратить любое множество a в аль GEBRA. Это как:

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

Это самый лучший способ, потому что для любого другого способа превратить a в алгебру b, мы можем дать функцию из свободной алгебры b:

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

Что такое левый является на самом деле показать, что свободный функтор создает ф-алгебру (и это то, что вы просили):

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

чтобы объяснить немного: ff имеет тип f (Free f a), и нам нужно построить Free f a. Мы можем это сделать, если мы сможем построить b, данные alg :: f b -> b и k :: a -> b. Поэтому мы можем применить alg к ff, если мы сможем сопоставить все Free f a, он содержит b, но это именно то, что rightAdjunct делает с alg и k.

Как вы уже догадались, это Free f является свободной монадой на функторе f

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