Объединение бесплатных типов

Ответ 1

Это ответ, основанный на тексте Типы данных à la carte, за исключением классов типов. Я рекомендую прочитать эту статью.

Хитрость заключается в том, что вместо написания интерпретаторов для Bells и Whistles вы определяете интерпретаторы для своих шагов одного функтора, BellsF и WhistlesF, например:

playBellsF :: BellsF (IO a) -> IO a
playBellsF (Ring  io) = putStrLn "RingRing!"  >> io
playBellsF (Chime io) = putStr   "Ding-dong!" >> io

playWhistlesF :: WhistelsF (IO a) -> IO a
playWhistlesF (PeaWhistle   io) = putStrLn "Preeeet!"   >> io
playWhistlesF (SteamWhistle io) = putStrLn "choo-choo!" >> io

Если вы решили не комбинировать их, вы можете просто передать их на Control.Monad.Free.iterM, чтобы вернуть свои исходные функции воспроизведения:

playBells    :: Bells a    -> IO a
playBells    = iterM playBell

playWhistles :: Whistles a -> IO a
playWhistles = iterM playWhistlesF

... однако, поскольку они имеют дело с отдельными шагами, их можно объединить более легко. Вы можете определить новую объединенную свободную монаду следующим образом:

data BellsAndWhistlesF a = L (BellsF a) | R (WhistlesF a)

Затем превратите это в свободную монаду:

type BellsAndWhistles = Free BellsAndWhistlesF

Затем вы пишете интерпретатор для одного шага BellsAndWhistlesF в терминах двух суб-интерпретаторов:

playBellsAndWhistlesF :: BellsAndWhistlesF (IO a) -> IO a
playBellsAndWhistlesF (L bs) = playBellsF    bs
playBellsAndWhistlesF (R ws) = playWhistlesF ws

... и затем вы получите интерпретатор для свободной монады, просто передав это iterM:

playBellsAndWhistles :: BellsAndWhistles a -> IO a
playBellsAndWhistles = iterM playBellsAndWhistlesF

Таким образом, ответ на ваш вопрос заключается в том, что трюк для объединения свободных монадов состоит в том, чтобы сохранять больше информации, определяя промежуточные интерпретаторы для отдельных шагов функтора ( "алгебры" ). Эти "алгебры" гораздо более поддаются комбинации, чем переводчики для свободных монад.

Ответ 2

Ответ Габриэля на месте, но я думаю, что стоит выделить немного больше, что заставляет все это работать, а именно, что сумма двух Functor также является Functor

-- | Data type to encode the sum of two 'Functor @[email protected] and @[email protected]
data Sum f g a = InL (f a) | InR (g a)

-- | The 'Sum' of two 'Functor is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Sum f g) where
    fmap f (InL fa) = InL (fmap f fa)
    fmap f (InR ga) = InR (fmap f ga)

-- | Elimination rule for the 'Sum' type.
elimSum :: (f a -> r) -> (g a -> r) -> Sum f g a -> r
elimSum f _ (InL fa) = f fa
elimSum _ g (InR ga) = g ga

(У библиотек Эдварда Кеммета это Data.Functor.Coproduct.)

Итак, если Functor являются "наборами инструкций" для монадов Free, то:

• Компонентные функции дают вам союзы таких наборов команд и, следовательно, соответствующие объединенные свободные монады
• Функция elimSum является основным правилом, которое позволяет вам построить интерпретатор Sum f g из интерпретатора для f и один для g.

Методы "Типы данных по выбору" - это то, что вы получаете, когда разрабатываете это понимание, - это стоит того, чтобы просто разобраться в этом.

Этот тип алгебры Functor является ценной вещью для изучения. Например:

data Product f g a = Product (f a) (g a)

-- | The 'Product' of two 'Functor is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Product f g) where
   fmap f (Product fa ga) = Product (fmap f fa) (fmap f ga)

-- | The 'Product' of two 'Applicative is also an 'Applicative'.
instance (Applicative f, Applicative g) => Applicative (Product f g) where
   pure x = Product (pure x) (pure x)
   Product ff gf <*> Product fa ga = Product (ff <*> fa) (gf <*> ga)


-- | 'Compose' is to 'Applicative' what monad transformers are to 'Monad'.
-- If your problem domain doesn't need the full power of the 'Monad' class, 
-- then applicative composition might be a good alternative on how to combine
-- effects.
data Compose f g a = Compose (f (g a))

-- | The composition of two 'Functor is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
   fmap f (Compose fga) = Compose (fmap (fmap f) fga)

-- | The composition of two 'Applicative is also an 'Applicative'.
instance (Applicative f, Applicative g) => Applicative (Compose f g) where
   pure = Compose . pure . pure
   Compose fgf <*> Compose fga = Compose ((<*>) <$> fgf <*> fga)

Запись в блоге Gershom Bazerman "Тестирование с помощью Applicative s" раскрывает эти моменты о Applicative s, и очень хорошо стоит прочитать.

EDIT:. Последнее замечание: когда люди создают свой собственный Functor для своих свободных монадов, на самом деле, неявно они используют именно эти методы. Я приведу два примера из Габриэля "Почему нужны свободные монады" :

data Toy b next =
    Output b next
  | Bell next
  | Done

data Interaction next =
    Look Direction (Image -> next)
  | Fire Direction next
  | ReadLine (String -> next)
  | WriteLine String (Bool -> next)

Все это можно проанализировать в некоторой комбинации функций Product, Sum, Compose, (->) и следующих трех:

-- | Provided by "Control.Applicative"
newtype Const b a = Const b

instance Functor (Const b) where
    fmap _ (Const b) = Const b


-- | Provided by "Data.Functor.Identity"
newtype Identity a = Identity a

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)


-- | Near-isomorphic to @Const ()@
data VoidF a = VoidF

instance Functor VoidF where
    fmap _ VoidF = VoidF

Поэтому для краткости используйте синонимы следующего типа:

{-# LANGUAGE TypeOperators #-}

type f :+: g = Sum f g
type f :*: g = Product f g
type f :.: g = Compose f g

infixr 6 :+:
infixr 7 :*:
infixr 9 :.:

... мы можем переписать такие функторы, как это:

type Toy b = Const b :*: Identity :+: Identity :+: VoidF

type Interaction = Const Direction :*: ((->) Image :.: Identity)
               :+: Const Direction :*: Identity
               :+: (->) String :.: Identity
               :+: Const String :*: ((->) Bool :.: Identity)