Что такое бесплатные монады?
Я видел, как термин " Свободная монада" появлялся время от времени в течение некоторого времени, но все, кажется, просто используют / обсуждают их, не объясняя, что они собой представляют. Итак: что такое бесплатные монады? (Я бы сказал, что я знаком с монадами и основами Хаскелла, но имею только очень грубые знания теории категорий.)
6 ответов
Ответ Эдварда Кметта, очевидно, великолепен. Но это немного технический. Вот, пожалуй, более доступное объяснение.
Свободные монады - это просто общий способ превращения функторов в монады. То есть с учетом любого функтора fFree f это монада Это было бы не очень полезно, если бы вы не получили пару функций
liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r
первый из них позволяет вам "войти" в вашу монаду, а второй - как "выйти" из нее.
В более общем смысле, если X - это Y с некоторыми дополнительными элементами P, то "свободный X" - это способ перехода от Y к X без получения чего-либо дополнительного.
Примеры: моноид (X) - это набор (Y) с дополнительной структурой (P), который в основном говорит, что у него есть операции (вы можете думать о сложении) и некоторая идентичность (например, ноль).
так
class Monoid m where
mempty :: m
mappend :: m -> m -> m
теперь мы все знаем списки
data [a] = [] | a : [a]
хорошо, учитывая любой тип t мы знаем это [t] это моноид
instance Monoid [t] where
mempty = []
mappend = (++)
и поэтому списки являются "свободным моноидом" над множествами (или в типах Haskell).
Итак, бесплатные монады - это та же идея. Мы берем функтор и возвращаем монаду. Фактически, поскольку монады можно рассматривать как моноиды в категории эндофункторов, определение списка
data [a] = [] | a : [a]
очень похоже на определение свободных монад
data Free f a = Pure a | Roll (f (Free f a))
и экземпляр Monad имеет сходство с экземпляром Monoid для списков
--it needs to be a functor
instance Functor f => Functor (Free f) where
fmap f (Pure a) = Pure (f a)
fmap f (Roll x) = Roll (fmap (fmap f) x)
--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)
instance Functor f => Monad (Free f) where
return = Pure -- just like []
x >>= f = concatFree (fmap f x) --this is the standard concatMap definition of bind
теперь мы получаем две наши операции
-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)
-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)
Вот еще более простой ответ: Монада - это то, что "вычисляется", когда монадический контекст разрушается join :: m (m a) -> m a (напоминая, что >>= можно определить как (join .) . flip fmap). Вот как монады переносят контекст через последовательную цепочку вычислений: потому что в каждой точке ряда контекст предыдущего вызова свернут со следующим.
Свободная монада удовлетворяет всем законам монады, но не делает никаких коллапсов (то есть вычислений). Он просто создает вложенную серию контекстов. Пользователь, который создает такое бесплатное монадическое значение, отвечает за то, чтобы что-то делать с этими вложенными контекстами, так что значение такой композиции может быть отложено до тех пор, пока монадическое значение не будет создано.
Случайно, что бесплатный foo - это самая простая вещь, которая удовлетворяет всем законам "foo". То есть он полностью соответствует законам, необходимым для того, чтобы быть обманщиком, и ничего лишнего.
Забывчивый функтор - это тот, который "забывает" часть структуры при переходе из одной категории в другую.
Данные функторы F : D -> C, а также G : C -> D, мы говорим F -| G, F оставлен присоединенным к G, или же G правильно присоединен к F всякий раз, когда за, б: F a -> b изоморфен 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, которую мы притворяемся, это Set), просто foldMapкоторый, когда специализируется от Data.Foldable Спискам имеет тип Monoid m => (a → m) → [a] → m,
Из этого следствия вытекают последствия. Примечательно, что если вы забудете, то создайте бесплатно, а затем снова забудете, это так же, как вы однажды забыли, и мы можем использовать это для создания монадического соединения. поскольку 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 пакет на взлом.
Мы могли бы также построить его в более тесной аналогии с приведенным выше кодом для свободного списка, определив
class Algebra f x where
phi :: f x -> x
newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)
Кофейные Комонады
Мы можем построить нечто подобное, взглянув на правое сопряжение с забывчивым функтором, предполагая, что оно существует. Свободный функтор просто / прямо присоединен / к забывчивому функтору, и симметрично знать, что что-то является свободной комонадой, - это то же самое, что знать, что придание гомоморфизму комонады из w -> Cofree f это то же самое, что дать естественную трансформацию из w -> f,
Свободная монада (структура данных) относится к монаде (классу), как список (структура данных) к моноиду (классу): это тривиальная реализация, где вы можете впоследствии решить, как будет комбинироваться контент.
Вы, вероятно, знаете, что такое Монада и что каждая Монада нуждается в конкретной (монадной законопослушной) реализации любого из них. fmap + join + return или же bind + return,
Предположим, у вас есть Functor (реализация fmap), но остальное зависит от значений и выбора, сделанных во время выполнения, что означает, что вы хотите иметь возможность использовать свойства Monad, но потом хотите выбирать функции Monad.
Это можно сделать с помощью Free Monad (структура данных), которая оборачивает Functor (тип) таким образом, чтобы 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)
Бесплатная монада Haskell - это список функторов. Для сравнения:
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,
Диаграмма проясняет это, но у меня нет возможности легко нарисовать ее!
Попытка найти ответ "мостик" между очень простыми ответами здесь и полным ответом.
Итак, "свободные монады" создают "монаду" из любого "функтора", поэтому давайте рассмотрим их по порядку.
Подробно о функторах
Некоторые вещи являются прилагательными на уровне типа, что означает, что они берут существительное типа, такое как "целые числа", и возвращают вам существительное другого типа, например, "списки целых чисел" или "пары строк с целыми числами", или даже "функции, создающие строки из целые числа. " Для обозначения произвольного прилагательного позвольте мне использовать заменяющее слово "синий".
Но затем мы замечаем закономерность, согласно которой некоторые из этих прилагательных являются входными или выходными в существительном, которое они модифицируют. Например, "функции, создающие строки из __" - это не то, что вводится, а "функции, превращающие строки в __" - это вывод. Правило здесь включает меня имеющий функцию X → Y, некоторые прилагательное "синий" является outputtish, или функтор, если я могу использовать такую функцию, чтобы превратить синий X в синий Y. Подумайте о "пожарном шланге, распыляющем X s", затем вы включаете эту функцию X → Y, и теперь ваш пожарный шланг распыляет Y s. Или это вводный или контравариантный если это наоборот, пылесос сосать Y s и, когда я ввернуть это на I получить вакуум сосать Xs. Некоторые вещи нельзя ни выводить, ни вкладывать. И то и другое оказывается фантомом: они не имеют абсолютно ничего общего с существительными, которые они описывают, в том смысле, что вы можете определить функцию "принуждение", которая берет синий X и создает синий Y, но * не зная детали типов X или Y", даже не требуя наличия функции между ними.
Так что "списки __" является outputtish, можно отобразить X → Y над списком X s, чтобы получить список Y s. Точно так же "пара строки и __" выводится. Между тем "функция от __ к себе" не является ни выводом, ни вводом ", в то время как" строка и список точно из нуля __s "могут быть" фантомным "случаем.
Но да, это все, что есть о функторах в программировании, это просто объекты, которые можно отображать. Если что-то является функтором, то это однозначно функтор, существует только один способ обобщенного отображения функции на структуру данных.
Монады
Монада является функтором, что в дополнение одновременно
- Универсально применимо, при любом X я могу построить синий X,
- Можно повторять без особого изменения смысла. Таким образом, синяя- голубая X в некотором смысле то же самое, только голубой X.
Это означает, что существует каноническая функция, сворачивающая любой синий-blue __ только в синий __. (И мы, конечно, добавляем законы, чтобы сделать все разумным: если один из слоев синего цвета был получен из универсального приложения, то мы хотим просто стереть это универсальное приложение; кроме того, если мы сведем сине-синий-синий X вниз до синий X, не должно иметь значения, сворачиваем ли мы первые два синих s первыми или вторыми двумя первыми.)
Первый пример - "__, допускающий значение NULL". Итак, если я дам вам int, допускающий значение NULL, в некотором смысле я не дал вам ничего больше, чем int, допускающий значение NULL. Или "список списков целых чисел", если речь идет только о том, чтобы иметь их 0 или более, тогда "список целых чисел" работает нормально, и правильное сворачивание объединяет все списки вместе в один суперсписок.
Монады стали популярными в Haskell, потому что Haskell нуждался в подходе, позволяющем делать вещи в реальном мире, не нарушая его математически чистый мир, в котором на самом деле ничего не происходит. Решение заключалось в том, чтобы добавить своего рода разбавленную форму метапрограммирования, в которой мы вводим прилагательное "программа, которая производит __". Итак, как мне получить текущую дату? Ну, Haskell не может сделать это напрямую без
unsafePerformIOно это позволит вам описать и составить программу, которая выдает текущую дату. В этом видении вы должны описать программу, которая не производит ничего под названием "Main.main", а компилятор должен взять ваше описание и передать вам эту программу в виде двоичного исполняемого файла, который вы можете запускать, когда захотите.
В любом случае "программа, которая создает программу, которая производит int", мало что покупает по сравнению с "программой, которая производит int", так что это оказывается монадой.
Бесплатные монады
В отличие от функторов, монады - это не однозначные монады. Для данного функтора существует не только один экземпляр монады. Так, например, "пара int и __", что вы делаете с этим int? Вы можете добавить это, вы можете умножить это. Если вы сделаете его int, допускающим значение NULL, вы можете оставить минимальный ненулевой или максимальный ненулевой, или крайний левый ненулевой, или крайний правый ненулевой.
Свободная монада для данного функтора - самая "скучная" конструкция, это просто "Свободный синий X - это синийn X для любого n = 0, 1, 2,...".
Она универсальна, поскольку blue⁰ X является только Х. И свободный синий свободный синий X является синимим синегон X, который только синием+п X. Он реализует "коллапс", поэтому, вообще не реализуя коллапс, внутренне "синие" вложены произвольно.
Это также означает, что вы можете отложить, какую именно монаду вы выбираете, на более поздний срок, позже вы можете определить функцию, которая уменьшает синий- синий X до синего X и свертывает все это до синего0,1 X, а затем другую функцию из X на синий X дает вам синий1 X во всем.