Визуализация свободной монады

Ответ 1

Прямо сейчас, я просто думаю о [свободной монаде] как о наиболее общем абстрактном синтаксическом дереве, которое вы можете себе представить. Это по существу это? Или я упрощаю это?

Вы упрощаете его:

• "Свободная монада" сокращена для "свободной монады по конкретному функтору" или типа данных Free f a, которая на самом деле является другой свободной монадой для каждого выбора f.
• Существует не одна общая структура, в которой есть все свободные монады. Их структура распадается на:
  • Что внесен сам Free
  • Что способствуют разные варианты для f

Но возьмем другой подход. Я изучил свободные монады, сначала изучив тесно связанную оперативную монаду, которая имеет более однородную, более простую в визуализации структуру. Я настоятельно рекомендую вам изучить это из самой ссылки.

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

{-# LANGUAGE GADTs #-}

data Program instr a where
  Return :: a -> Program instr a
  Bind :: instr x                  -- an "instruction" with result type `x`
       -> (x -> Program instr a)   -- function that computes rest of program
       -> Program instr a          -- a program with result type `a`

... где параметр instr представляет собой тип "инструкции" монады, обычно GADT. Например (взято из ссылки):

data StackInstruction a where
    Pop  :: StackInstruction Int
    Push :: Int -> StackInstruction ()

Итак, a Program в оперативной монаде, неофициально, я представляю ее как "динамический список" инструкций, где результат, созданный выполнением любой команды, используется в качестве входных данных для функции, которая решает, что "хвост" из "списка инструкций". Конструктор Bind объединяет команду с функцией "tail chooser".

Многие свободные монады также могут быть визуализированы в сходных терминах - вы можете сказать, что функтор, выбранный для данной свободной монады, служит в качестве "набора команд". Но со свободными монадами "хвосты" или "дети" "инструкции" управляются самим Functor. Итак, простой пример (взятый из Gabriel González популярной записи в блоге по теме):

data Free f r = Free (f (Free f r)) | Pure r

-- The `next` parameter represents the "tails" of the computation.
data Toy b next =
    Output b next
  | Bell next
  | Done

instance Functor (Toy b) where
  fmap f (Output b next) = Output b (f next)
  fmap f (Bell next) = Bell (f next)
  fmap _ Done = Done

В операционной монаде функция, используемая для генерации "хвоста", относится к типу Program (в конструкторе Bind), а в свободных монадах хвосты относятся к типу "команда" /Functor. Это дает возможность "инструкциям" свободной монады (аналог, который сейчас разрушается) иметь один "хвост" (например, Output или Bell), нулевые хвосты (например, Done) или несколько хвостов, если вы так выбрали к. Или, в другой общей схеме, параметр next может быть результатом типа встроенной функции:

data Terminal a next = 
    PutStrLn String next
  | GetLine (String -> next)  -- can't access the next "instruction" unless
                              -- you supply a `String`.

instance Functor Terminal where
    fmap f (PutStrLn str next) = PutStrLn str (f next)
    fmap f (GetLine g) = GetLine (fmap f g)

Это, кстати, это возражение, которое я давно имел для людей, которые ссылаются на свободные или операционные монады как на "синтаксические деревья" - для их практического использования требуется, чтобы "дети" из node были непрозрачно скрыты внутри функции, Обычно вы не можете полностью проверить это "дерево"!

Итак, когда вы приступите к нему, то, как визуализировать свободную монаду, полностью сводится к структуре Functor, которую вы используете для параметризации. Некоторые выглядят как списки, некоторые похожи на деревья, а некоторые похожи на "непрозрачные деревья" с функциями в качестве узлов. (Кто-то однажды ответил на мое возражение выше с помощью строки типа "функция - это дерево node с таким количеством детей, сколько возможных аргументов." )

Ответ 2

Возможно, вы слышали

Монада является моноидом в категории эндофунторов

И вы уже упоминали, что моноиды - это просто списки. Итак, вы здесь.

Развернувшись на этом немного:

data Free f a = Pure a
              | Free (f (Free f a))

Это не обычный список a, а список, в котором хвост заключен внутри f. Вы увидите это, если вы напишете структуру значений нескольких вложенных привязок:

pure x >>= f >>= g >>= h :: Free m a

может привести к

Free $ m1 $ Free $ m2 $ Free $ m3 $ Pure x
  where m1, m2, m3 :: a -> m a -- Some underlying functor "constructors"

Если m в приведенном выше примере является типом суммы:

data Sum a = Inl a | Inr a
  deriving Functor

Затем список фактически является деревом, так как у каждого конструктора мы можем разветвляться влево или вправо.

Возможно, вы слышали, что

Аппликативный является моноидом в категории эндофунторов

... категория просто другая. Есть хорошие визуализации различных бесплатных аппликативных кодировок в Романном блоге Cheplyaka.

Таким образом, свободный Applicative также является списком. Я представляю это как гетерогенный список значений f a и одну функцию:

 x :: FreeA f a
 x = FreeA g [ s, t, u, v]
    where g :: b -> c -> d -> e -> a
          s :: f b
          t :: f c
          u :: f d
          v :: f e

В этом случае сам хвост не завернут в f, но каждый элемент отдельно. Это может или не поможет понять разницу между Applicative и Monad.

Обратите внимание, что f не должно быть Functor, чтобы сделать Applicative (FreeA f a), обратным к монаде Free выше.

Существует также бесплатный Functor

data Coyoneda f a = Coyoneda :: (b -> a) -> f b -> Coyoneda f a  

который делает любой тип * -> * Functor. Сравните это со свободным Applicative выше. В прикладном случае у нас был гетерогенный список длины n значений f a и n-арная функция, объединяющая их. Койонеда - это 1-частый частный случай выше.

Мы можем объединить Coyoneda и Free, чтобы сделать свободную монаду Operational. И как говорится в другом ответе, этот человек выносливо мыслим как дерево, так как есть функции. OTOH вы можете представить эти продолжения как разные магические стрелки в вашей картине:)