Какие монады могут быть выражены как свободные над некоторым функтором?

Ответ 1

Почти все из них (до вопросов, связанных с циклом и mfix), но не Cont.

Рассмотрим State monad

newtype State s a = State (s -> (a,s))

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

get :: m s --or equivalently (s -> m a) -> m a
set :: s -> m () --or (s,m a) -> m a
runState :: m a -> s -> (a,s)

мы можем создать свободную монаду с этим интерфейсом, указав операции как конструкторы

data StateF s a
  = Get (s -> a) | Set s a deriving Functor

то имеем

type State s a = Free (StateF s) a

с

get = Impure (Get Pure)
set x = Impure (Set x (Pure ())

и нам просто нужен способ его использования

runState (Pure a) s = (a,s)
runState (Impure (Get f)) s = runState (f s) s
runState (Impure (Set s next)) _ = runState next s

вы можете сделать эту конструкцию с большинством монад. Подобно монадии, возможно,/частичной, определяется

stop :: m a
maybe :: b -> (a -> b) -> m a -> b

это правило, мы рассматриваем каждую из функций, которые заканчиваются на m x для некоторого x как конструктора в функторе, а другие функции - это способы запуска полученной свободной монады. В этом случае

data StopF a = StopF deriving Functor

maybe _ f (Pure a)      = f a
maybe b _ (Impure Stop) = b

почему это круто? Ну, несколько вещей

• Свободная монада дает вам кусочек данных, который вы можете представить как АСТ для монадического кода. Вы можете писать функции, которые работают с этими данными, что действительно полезно для DSL.
• Компоненты Functors, что означает разбиение ваших монад, как это делает их полуразлагаемыми. В частности, с учетом двух функторов, которые разделяют алгебру (алгебра является по существу просто функцией f a -> a для некоторого a, когда f является функтором), композиция также имеет эту алгебру.

Состав functor - это просто Мы можем комбинировать функторы несколькими способами, большинство из которых сохраняют эту алгебру. В этом случае мы хотим не состав функторов (f (g (x))), а функторный копродукт. Функторы добавить

data f :+: g a = Inl (f a) | Inr (g a) 

instance (Functor f, Functor g) => Functor (f :+: g) where
  fmap f (Inl x) = Inl (fmap f x)
  fmap f (Inr x) = Inr (fmap f x)

compAlg :: (f a -> a) -> (g a -> a) -> f :+: g a -> a
compAlg f _ (Inl x) = f x
compAlf _ g (Inr x) = g x

также свободные монады сохраняют алгебры

freeAlg :: (f a -> a) -> Free f a -> a
freeAlg _ (Pure a) = a
freeAlg f (Impure x) = f $ fmap (freeAlg f) x

В знаменитой бумаге Wouter Swierstra Типы данных A La Carte это используется для большого эффекта. Простым примером этого документа является калькулятор. Который мы возьмем монадический призыв к новому в этот пост. Для алгебры

class Calculator f where
 eval :: f Integer -> Integer

мы можем думать о различных случаях

data Mult a = Mult a a deriving Functor
instance Calculator Mult where
  eval (Mult a b) = a*b

data Add a = Add a a deriving Functor
instance Calculator Add where
  eval (Add a b) = a+b

data Neg a = Neg a deriving Functor
instance Calculator Neg where
  eval (Neg a) = negate a

instance Calculator (Const Integer) where
  eval (Const a) = a

data Signum a = Signum a deriving Functor
instance Calculator Signum where
  eval (Signum a) = signum a

data Abs a = Abs a deriving Functor
instance Calculator Abs where
  eval (Abs a) = abs a

и наиболее важные

instance (Calculator f, Calculator g) => Calculator (f :+: g) where
   eval = compAlg eval

вы можете определить числовую монаду

newtype Numerical a = Numerical (
        Free (Mult 
        :+: Add 
        :+: Neg 
        :+: Const Integer 
        :+: Signum
        :+: Abs) a deriving (Functor, Monad)

и затем вы можете определить

 instance Num (Numerical a)

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

 class Pretty f where
    pretty :: f String -> String

 instance Pretty Mult where
    pretty (Mult a b) = a ++ "*" ++ b

и аналогичный для всех остальных.

Это полезная дизайн-стратегия: укажите, что вы хотите сделать своей монаде == > определить функторы для каждой операции == > выяснить, какие некоторые из ее алгебр должны быть == > определить эти функторы для каждой операции == > сделайте это быстро.

Делать это быстро сложно, но у нас есть некоторые трюки. Trick 1 - просто обернуть свою свободную монаду в Codensity (кнопка "идти быстрее" ), но когда это не сработает, вы хотите избавиться от свободного представления. Помните, когда мы

runState (Pure a) s = (a,s)
runState (Impure (Get f)) s = runState (f s) s
runState (Impure (Set s next)) _ = runState next s

Ну, это функция от Free StateF a до s -> (a,s), просто используя тип результата, поскольку наше определение состояния кажется разумным... но как мы определяем операции? В этом случае вы знаете ответ, но одним из способов его получения было бы думать о том, что Коналл Эллиотт называет морфизмами типа класса. Вы хотите

runState (return a) = return a
runState (x >>= f) = (runState x) >>= (runState f)
runState (set x) = set x
runState get = get

что делает его довольно легким

runState (return a) = (Pure a) = \s -> (a,s)

runState (set x) 
   = runState (Impure (Set x (Pure ()))) 
   = \_ -> runState (Pure ()) x
   = \_ -> (\s -> (a,s)) x
   = \_ -> (a,x)

runState get
  = runState (Impure (Get Pure))
  = \s -> runState (Pure s) s
  = \s -> (s,s)

который довольно полезен. Вывод >>= таким образом может быть жестким, и я не буду включать его здесь, но остальные из них - это точно определения, которые вы ожидаете.

Ответ 2

Чтобы ответить на вопрос, как говорится, большинство знакомых монадов, о которых вы не упоминали в вопросе, не являются самими свободными монадами. Ответ Филиппа Дж. Намекает на то, как вы можете связать данную монаду с новой, свободной монадой, но новая монада будет "больше": она имеет более четкие значения, чем оригинальная монада. Например, реальная монада State s удовлетворяет get >>= put = return (), но свободной монады на StateF нет. Как свободная монада, она не удовлетворяет дополнительным уравнениям по определению; это само понятие свободы.

Я покажу, что монады Reader r, Writer w и State s не являются бесплатными, за исключением особых условий на r/w/s.

Позвольте мне ввести некоторую терминологию. Если m является монадой, тогда мы вызываем любое значение типа m a an (m -). Мы называем m-действием тривиальным, если для некоторого x оно равно return x; иначе мы называем это нетривиальным.

Если m = Free f - любая свободная монада на функторе f, то m допускает гомоморфизм монады к Maybe. Это связано с тем, что Free является функториальным в своем аргументе f и Maybe = Free (Const ()), где Const () - конечный объект в категории функторов. Конкретно этот гомоморфизм можно записать

toMaybe :: Free f a -> Maybe a
toMaybe (Pure a) = Just a
toMaybe (Impure _) = Nothing

Поскольку toMaybe является гомоморфизмом монады, он, в частности, удовлетворяет toMaybe (v >> w) = toMaybe v >> toMaybe w для любых m -действий v и w. Теперь заметим, что toMaybe отправляет тривиальные m -действия в тривиальные операции Maybe и нетривиальные m -действия к нетривиальному Maybe -action Nothing. Теперь Maybe обладает тем свойством, что >> с нетривиальным действием с любым действием в любом порядке дает нетривиальное действие (Nothing >> w = v >> Nothing = Nothing); так же верно и для m, так как toMaybe является монодальным монадом, сохраняющим (не) тривиальность.

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

Чтобы показать, что конкретная монада m не изоморфна любой свободной монаде, то достаточно найти m -акций v и w таких, что хотя бы один из v и w нетривиально, но v >> w тривиально.

Reader r удовлетворяет v >> w = w, поэтому нам просто нужно выбрать w = return () и любое нетривиальное действие v, которое существует до тех пор, пока r имеет по крайней мере два значения (тогда ask является непостоянным, т.е., нетривиально).

Для Writer w предположим, что существует обратимый элемент k :: w, отличный от тождественного. Пусть kinv :: w является его обратным. Тогда tell k >> tell kinv = return (), но tell k и tell kinv нетривиальны. Любая нетривиальная группа (например, целые числа при добавлении) имеет такой элемент k. Я полагаю, что свободные монады формы Writer w - это только те, для которых моноид w сам свободен, т.е. w = [a], Writer w ~ Free ((,) a).

При State s аналогично, если s допускает любой нетривиальный автоморфизм f :: s -> s с обратным finv :: s -> s, то modify f >> modify finv = return (). Любой тип s с хотя бы двумя элементами и разрешимым равенством имеет такие автоморфизмы.

Ответ 3

Я написал доказательство того, что монада списка не является бесплатной в размещении в списке рассылки haskell-cafe, на основе данных в ответе Рида:

Напомним, что для любого функтора f мы можем построить свободную монаду над f:

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

Интуитивно, Free f a - тип f-образных деревьев с листьями типа a. Операция объединения просто соединяет деревья и не выполняет никаких действий дальнейшие вычисления. Значения формы (Roll _) называются "нетривиальный" в этой публикации.

Некоторые обычные монады на самом деле являются свободными монадами над некоторым функтором:

• Монада дерева - это свободная монада над функтором Pair, где data Pair a = MkPair a a. Интуиция в виде парных деревьев является наиболее сильным в этом примере. У каждого родителя node есть пара детей.

• Возможно, монада - это свободная монада над функтором Unit, где data Unit a = MkUnit. В графическом изображении родительские узлы имеют Unit детей, поэтому детей вообще нет. Таким образом, существует ровно два Unit -образные деревья: дерево, состоящее только из листа (соответствующее до Just _), а три из них состоят из бездетного родителя node (соответствует Nothing).

• Монада Identity - свободная монада над функтором Void, где Void a - тип без конструкторов.

• Монада Partiality - свободная монада над Maybe.

• Монада Writer [r] - свободная монада над функтором (r,). В дереве (r,), родительский node украшен значением типа r и имеет ровно один дочерний элемент node. Прохождение такого пути дает список r и значение листа типа a, поэтому в целом значение типа ([r],a) = Writer r a.

  (В частности, Free (r,) () изоморфно [r]. Это наблюдение привело к утверждению, что монада-список является бесплатной. Но это утверждение неверно и действительно не следует из наблюдения. Чтобы показать, что монада m является свободным, приходится проявлять изоморфизм монады forall a. m a -> Free f a для некоторого функтора f. Напротив, демонстрируя изоморфизм m a с Free (f a) () не является ни достаточным, ни обязательным.)

Еще больше монадов являются факторами свободных монад. Например, State s является фактор Free (StateF s), где

data StateF s a = Put s a | Get (s -> a).
-- NB: This functor is itself a free functor over a type constructor
-- which is sometimes called StateI [1], rendering Free (StateF s) what
-- Oleg and Hiromi Ishii call a "freer monad" [2].

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

run :: Free (StateF s) a -> State s a
run (Pure x)         = return x
run (Roll (Put s m)) = put s >> run m
run (Roll (Get k))   = get >>= run . k

Эта точка зрения является основой операционного пакета apfelmus [1] и также упоминается в потоке StackOverflow [3]. Это главная причина, по которой свободные монады полезны в контексте программирования.

Итак, является ли монада монадой свободной монады? Интуитивно это не так, потому что операция объединения монады списка (конкатенация) не просто трансплантация выражения вместе, но выравнивает их [4].

Вот доказательство того, что монада списка не является бесплатной. Я записываю его с тех пор Я довольно долго интересовался доказательством, но искал это не дало никаких результатов. Однако потоки [3] и [5] приблизились.

В свободной монаде над любым функтором результат связывания нетривиального действие с любой функцией всегда нетривиально, т.е.

(Roll _ >>= _) = Roll _

Это можно проверить непосредственно из определения (>>=) для свободного монада или, альтернативно, с трюком Рейда Бартона об использовании монады морфизм к Возможно, см. [3].

Если монада-список была изоморфной-как-монада свободной монаде над некоторой функтор, изоморфизм будет отображать только одноэлементные списки [x] в значения формы (Pure _) и всех других списков к нетривиальным значениям. Это потому что мономорфизмы монады должны коммутировать с "возвратом" и return x [x] в монаде списка и Pure x в свободной монаде.

Эти два факта противоречат друг другу, как видно из следующего Пример:

do
    b <- [False,True]  -- not of the form (return _)
    if b
        then return 47
        else []
-- The result is the singleton list [47], so of the form (return _).

После применения гипотетического изоморфизма к свободной монаде над некоторым функтора, у нас получилось бы, что привязка нетривиального значения (изображение из [False,True] при изоморфизме) с некоторой функцией приводит к тривиальное значение (изображение [47], т.е. return 47).

Cheers, Инго

[1] http://projects.haskell.org/operational/Documentation.html

[2] http://okmij.org/ftp/Haskell/extensible/more.pdf

[3] Какие монады могут быть выражены как свободные над некоторым функтором?

[4] https://hackage.haskell.org/package/free-4.12.4/docs/Control-Monad-Free.html

[5] https://www.reddit.com/r/haskell/comments/50zvyb/why_is_liststate_not_a_free_monad/

Ответ 4

Все монады могут быть выражены как Свободная Монада. Их дополнительные свойства (например, MonadFix и Cont) могут быть удалены таким образом, потому что Free Monad не является Free MonadFix или Free Cont.

Общий способ - определить functor fmap в терминах liftM, а затем обернуть Free вокруг этого Functor. Полученная Monad может быть сведена к предыдущей/фактической Monad, указав, как функции return и join (Чистые и Нечистые) должны быть сопоставлены с фактической Monad.