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

Я видел, как термин « Свободная Монада» появляется время от времени, но все просто используют / обсуждают их, не объясняя, что они собой представляют. Итак: что такое свободные монады? (Я бы сказал, что я знаком с монадами и основами Хаскелла, но имею только очень грубое знание теории категорий.)

    Ответ Эдварда Кметта, очевидно, велик. Но это немного технично. Вот, возможно, более доступное объяснение.

    Свободные монады – всего лишь общий способ превращения функторов в монады. То есть, при любом функторе f Free f является монадой. Это было бы не очень полезно, за исключением того, что вы получаете пару функций

     liftFree :: Functor f => fa -> Free fa foldFree :: Functor f => (fr -> r) -> Free fr -> r 

    первая из них позволяет вам «войти» в свою монаду, а вторая дает вам способ «выйти» из нее.

    В более общем плане, если X является Y с некоторым дополнительным материалом P, тогда «свободный X» является способом перехода от Y к X без получения чего-либо дополнительного.

    Примеры: monoид (X) представляет собой набор (Y) с дополнительной структурой (P), который в основном говорит, что он имеет операции (вы можете думать о добавлении) и некоторую идентичность (например, нуль).

    так

     class Monoid m where mempty :: m mappend :: m -> m -> m 

    теперь мы все знаем списки

     data [a] = [] | a : [a] 

    хорошо, учитывая любой тип t мы знаем, что [t] является monoидом

     instance Monoid [t] where mempty = [] mappend = (++) 

    и поэтому списки – это «свободный monoид» над наборами (или в типах Haskell).

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

     data [a] = [] | a : [a] 

    очень похоже на определение свободных монад

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

    и экземпляр Monad имеет сходство с экземпляром Monoid для списков

     --it needs to be a functor instance Functor f => Functor (Free f) where fmap f (Pure a) = Pure (fa) fmap f (Roll x) = Roll (fmap (fmap f) x) --this is the same thing as (++) basically concatFree :: Functor f => Free f (Free fa) -> Free fa 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 fx) --this is the standard concatMap definition of bind 

    теперь мы получаем две операции

     -- this is essentially the same as \x -> [x] liftFree :: Functor f => fa -> Free fa liftFree x = Roll (fmap Pure x) -- this is essentially the same as folding a list foldFree :: Functor f => (fr -> r) -> Free fr -> r foldFree _ (Pure a) = a foldFree f (Roll x) = f (fmap (foldFree f) x) 

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

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

    Свободное foo – это самая простая вещь, которая удовлетворяет всем законам «foo». То есть он удовлетворяет точно законам, необходимым для того, чтобы быть foo и ничего лишним.

    Забывающий функтор – это тот, который «забывает» часть структуры, поскольку она идет от одной категории к другой.

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

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

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

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

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

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

    Тогда вы можете определить функтор F из категории множеств обратно в категорию monoидов, которые слева сопряжены с этим функтором. Этот функтор является функтором, который отображает множество a в monoид [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 monoидов, где стрелки являются monoидными гомоморфизмами, поэтому нам нужно a показать, что monoидный гомоморфизм из [a] → b может быть точно описан функцией из a → b .

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

    Из этого вытекают вытекающие из этого последствия. Примечательно, что если вы забудете, тогда созидайте со свободным, тогда забудьте еще раз, это точно так же, как вы забыли один раз, и мы можем использовать это, чтобы создать монадическое соединение. так как UFUF ~ U(FUF) ~ UF , и мы можем перейти в тождественный monoидный гомоморфизм из [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 здесь отображает monoды в функторы.

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

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

     class Algebra fx where phi :: fx -> x newtype Free fa = Free (forall x. Algebra fx => (a -> x) -> x) 

    Cofree Comonads

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

    Free Monad (структура данных) относится к Monad (classу), подобному списку (структуре данных) для Monoid (class): это тривиальная реализация, в которой вы можете потом решить, как будет комбинироваться контент.


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

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

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

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

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

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

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

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

     data List a = Nil | Cons a (List a ) data Free fr = Pure r | Free (f (Free fr)) 

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

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

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

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

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

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

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

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

    Interesting Posts

    Виртуальная машина хранится почти полностью, но Windows C диск говорит 29 ГБ бесплатно

    Как правильно использовать D3 в Node.js?

    Работа с neuralnet в R в первый раз: get “требует числовых / сложных матричных / векторных аргументов”

    Создание экземпляра вложенного classа в XAML

    try / catch с InputMismatchException создает бесконечный цикл

    Есть ли какая-либо реализация LRU для IDRU?

    Изменение прокрутки колеса мыши самопроизвольно изменяется

    Как (де) создавать кадры данных в WebSockets hybi 08+?

    отключить nganimate для некоторых элементов

    Сбой метода generate_series () в Redshift

    Есть ли расширение Google Chrome, которое действует как закладки быстрого поиска ключевых слов Firefox?

    Как проверить в Git по дате?

    Express: Как передать приложение-пример маршрутам из другого файла?

    Как создать метод println / print для пользовательского classа

    Как отключить индексирование в определенном каталоге на нескольких платформах?

    Давайте будем гением компьютера.