Что такое свободные монады?

вот еще более простой ответ: монада-это то, что" вычисляет", когда монадический контекст свернут join :: m (m a) -> m a (ссылаясь, что >>= можно определить как (join .) . flip fmap). Вот как монады переносят контекст через последовательную цепочку вычислений: потому что в каждой точке серии контекст из предыдущего вызова сворачивается со следующим.

A свободные монады удовлетворяет всем законам монады, но не рушится (т. е. расчет). Это просто создает вложенный ряд контекстов. Пользователь, который создает такое свободное монадическое значение, отвечает за выполнение чего-то с этими вложенными контекстами, так что смысл такая композиция может быть отложена до тех пор, пока не будет создано монадическое значение.

свободный фу оказывается самой простой вещью, которая удовлетворяет всем законам "фу". То есть он точно удовлетворяет законам, необходимым для того, чтобы быть foo и ничего лишнего.

забывчивый функтор-это тот, который" забывает " часть структуры, когда она переходит из одной категории в другую.

учитывая функторы F : D -> C и G : C -> D, мы говорим F -| G,F слева примыкает к G или G справа примыкает к F всякий раз, когда forall a, b:F a -> b is изоморфно a -> G b, где стрелки приходят из соответствующих категорий.

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

Свободный Моноид

начнем с более простого примера, свободного моноида.

возьмите моноид, который определяется некоторым набором носителей T, двоичная функция для смешивания пары элементов вместе f :: T → T → T и unit :: T, таких, что у вас есть ассоциативный закон и закон тождества: f(unit,x) = x = f(x,unit).

вы можете сделать функтор U из категории моноидов (где стрелки - моноидные гомоморфизмы, то есть они гарантируют, что они отображают unit до unit на другом моноиде, и что вы можете составить до или после отображения на другой моноид без изменения значения) в категорию наборов (где стрелки - это просто стрелки функций), которые "забывают" об операции и unit и просто дает вам перевозчика набор.

тогда вы можете определить функтор F из категории множеств обратно в категорию моноидов, которая остается сопряженной с этим функтором. Этот функтор является функтором, который отображает множество a в моноиде [a], где unit = [] и mappend = (++).

Итак, чтобы рассмотреть наш пример до сих пор, в псевдо-Haskell:

U : Mon → Set -- is our forgetful functor
U (a,mappend,mempty) = a

F : Set → Mon -- is our free functor
F a = ([a],(++),[])

показать F свободен, нужно продемонстрировать, что он слева сопряжен с U, забывчивый функтор, то есть, как мы упомянуто выше, мы должны показать, что

F a → b изоморфна a → U b

теперь запомните цель F в категории Mon из моноидов, где стрелки моноидом гомоморфизмы, поэтому нам нужно показать, что моноидом гомоморфизм [a] → b может быть точно описана функцией от a → b.

в Хаскелле мы называем сторону этого, которая живет в Set (РП, Hask, категория типов Haskell, которые мы притворяемся Комплект), просто foldMap, который при специализации от Data.Foldable к спискам имеет тип Monoid m => (a → m) → [a] → m.

есть последствия, которые вытекают из того, что это примыкание. Примечательно, что если вы забудете, то создадите free, а затем снова забудете, так же, как вы забыли один раз, и мы можем использовать это для создания монадического соединения. так как UFUF~ U(FUF)~ UF, и мы можем перейти в тождественный моноидный гомоморфизм от [a] до [a] через изоморфизм, который определяет наши примыкание, получить, что список изоморфизм от [a] → [a] является функцией типа a -> [a], и это просто возвращение для списков.

вы можете составить все это более непосредственно, описав список в этих терминах с помощью:

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

Свободная Монада

что это Свободные Монады?

Ну, мы делаем то же самое, что и раньше, мы начинаем с забывчивого функтора U из категории монад, где стрелки-это гомоморфизмы монад к категории эндофункторов, где стрелки являются естественными преобразованиями, и мы ищем функтор, который остается сопряженным с этим.

Итак, как это соотносится с понятием свободной монады, как оно обычно используется?

зная, что нечто является свободной монадой,Free f, говорит вам, что дает гомоморфизм монады от Free f -> m, это то же самое (изоморфно), что и естественное преобразование (гомоморфизм функтора) из f -> m. Помните F a -> b должно быть изоморфно a -> U b чтобы F оставалось сопряженным с U. U здесь отображенные монады на функторы.

F по крайней мере изоморфно Free тип я использую в своей free пакет на hackage.

мы также могли бы построить его в более жесткой аналогии с кодом выше для свободного списка, определив

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

Cofree Comonads

мы можем построить что-то подобное, глядя справа примыкает к забывчивому функтору, предполагая, что он существует. Свободный функтор просто / прямо сопряжен/ с забывчивым функтором, и по симметрии, зная, что что-то является свободным комонадом, это то же самое, что знать, что дает гомоморфизм комонады из w -> Cofree f это то же самое, что дать естественное преобразование из w -> f.

Свободная Монада (структура данных) относится к монаде (классу), как список (структура данных) к Моноиду (классу): это тривиальная реализация, где вы можете впоследствии решить, как будет объединено содержимое.

---

вы, наверное, знаете, что такое Монада и что каждая Монада нуждается в конкретной (Монада-законопослушный) реализации либо fmap + join + return или bind + return.

предположим, что у вас есть функтор (реализация fmap) но остальное зависит от значений и выбора, сделанных во время выполнения, что означает, что вы хотите иметь возможность использовать свойства монады, но хотите выбрать функции монады после этого.

это можно сделать с помощью свободной монады (структуры данных), которая обертывает функтор (тип) таким образом, что join - это скорее укладка этих функторов, чем сокращение.

реальный return и join вы хотите использовать, теперь можно задать в качестве параметров функция сокращения foldFree:

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

чтобы объяснить типы, мы можем заменить Functor f С Monad m и b С (m a):

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)

свободная монада Хаскелла-это список функторов. Сравните:

data List a   = Nil    | Cons  a (List a  )

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

Pure аналогично Nil и Free аналогично Cons. Свободная монада хранит список функторов вместо списка значений. Технически вы можете реализовать свободные монады, используя другой тип данных, но любая реализация должна быть изоморфна вышеупомянутой.

вы используете свободные монады всякий раз, когда вам нужно абстрактное синтаксическое дерево. Базовый функтор свободной монады-это форма каждого шага синтаксического дерева.

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

я думаю, что простой конкретный пример поможет. Предположим, что у нас есть функтор

data F a = One a | Two a a | Two' a a | Three Int a a a

с явными fmap. Тогда Free F a Это тип деревьев, листья которых имеют тип a и чьи узлы помечены One,Two,Two' и Three. One-узлы имеют одного ребенка, Two и Two'-узлы имеют двух детей и Three-узлы имеют три и также с меткой Int.

Free F - это монада. return карты x к дереву, которое является просто листом со значением x. t >>= f смотрит на каждый из листьев и заменяет их деревьями. Когда лист имеет значение y он заменяет этот лист деревом f y.

диаграмма делает это более ясным, но у меня нет средств для легкого рисования!