Как превратить бесплатную монаду в функтор?

Question

Страница Свободная структура в вики Haskell определяет функцию для преобразования экземпляра функтора в свободную монаду:

inj :: Functor f => f a -> Free f a
inj fa = Roll $ fmap Return fa

Тогда, скажем, inj [1,2,3], имеет тип (Num t) => Free [] t. Как определить функцию, возвращающую что-то вроде inj [1,2,3] обратно в [1,2,3]?

Answer 1

Первое, что нужно заметить, это то, что изменение inj превращает Free в нечто почти монадное преобразование.

Я буду использовать Control.Monad.Free из моей бесплатной посылки на хакер, чтобы не повторять здесь все.Это означает, что Roll становится Free, а Return вместо этого именуется Pure в приведенном ниже коде относительно версии в вики.

import Control.Monad
import Control.Monad.Free -- from 'free'

instance MonadTrans Free where
    lift = Free . liftM Pure

Однако вы не можете пойти в другом направлении для произвольного Functor.Однако, если у вас есть экземпляр Monad на m, вы можете отменить подъем, сгладив Free m вниз до одного слоя базовой монады m!

retract :: Monad f => Free f a -> f a  
retract (Pure a) = return a
retract (Free as) = as >>= retract

Имявыбран, потому что это ретракция из lift.Так называется, потому что

retract . lift = id 

выполняется, как показано

retract (lift as) =                        -- by definition of lift
retract (Free (liftM Pure as)) =           -- by definition of retract
liftM Pure as >>= retract =                -- by definition of liftM
as >>= \a -> return (Pure a) >>= retract = -- first monad law
as >>= \a -> retract (Pure a)              -- by definition of retract
as >>= \a -> return a =                    -- eta reduction
as >>= return                              -- second monad law
as

, поэтому функция retract отменяет работу lift.

Поскольку fmap = liftM, это верно и для inj.

Обратите внимание, что lift . retract - это , а не id.Просто не хватает места, чтобы поместить все в промежуточный тип - использование монады разбивает все плоско - но lift . retract . lift . retract = lift . retract держится, потому что lift . retract . lift . retract = lift . id . retract = lift . retract, поэтому lift . retract идемпотентно.

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

Сейчас я собираюсь добавить retract в бесплатный пакет прямо сейчас.Мне это нужно было недавно для статьи, которую я пишу в любом случае.

Answer 2

Как говорит @sclv, нет способа напрямую конвертировать из свободной монады функтора обратно в функтор в общем случае.Почему бы и нет?

Если вы вспомните страницу «свободных структур», на которую вы ссылались, сначала она расскажет о свободных моноидах , а затем расширит эту же концепцию и расскажет о монадах .,Свободный моноид для типа - это список;эквивалентная функция «конвертировать обратно» в этом случае будет превращать свободный моноид типа [a] в один элемент типа a.Это, очевидно, невозможно выполнить двумя разными способами: если список пуст, он не может ничего вернуть;и если список имеет несколько элементов, он должен отбросить все, кроме одного.

Конструкция свободной монады аналогична и представляет аналогичную проблему.Свободная монада определяется композицией функторов , которая аналогична обычной композиции функций, за исключением конструктора типа .Мы не можем написать композицию функтора непосредственно в Haskell, но так же, как f . g означает \x -> f (g x), мы можем вложить приложение конструктора типа.Например, составление Maybe с самим собой дает тип, подобный Maybe (Maybe a).

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

Так что если мы посмотрим на Free [] Int, это может быть один Int, список Int с, список списков Ints и т. д.on.

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

---

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

В конкретном случае свободной монады для списков есть один очевидный подход - рекурсивное выравнивание структуры путем вычеркиванияTОн Roll и Return конструкторы и списки составления по мере продвижения.Также может быть полезно подумать о , почему этот подход работает в этом случае, и как он связан со структурой списков.

Answer 3

Я не понимаю, почему вы запрашиваете эту функцию, и в общем случае нет единственной функции типа Free f a -> f a.Тем не менее, равно , обратному inj - то есть есть функция этого типа , если вы знаете, что структура представляет собой внешний рулон с одним слоемВернуть.Если есть более глубокие значения Roll s, то это не удастся с ошибками сопоставления с шаблоном, поэтому для начала это своего рода глупость.Тем не менее, здесь вы идете:

unInj :: Functor f => Free f a -> f a
unInj (Roll x) = fmap (\(Return y) -> y) x