Как пройти монаду с определением рекурсии и собрать результаты? - PullRequest
Новая
       24

Как пройти монаду с определением рекурсии и собрать результаты?

0 голосов
/ 10 мая 2018

Я реализую монадный преобразователь MaybeT. 

newtype MaybeT m a =
    MaybeT { runMaybeT :: m (Maybe a) }

Затем я пишу монаду для возврата. 

newtype BackT m a =
    BackT { unBackT :: MaybeT m (a, BackT m a) }

Здесь Back m a имеет определение рекурсии.

На мой взгляд, существуют изоморфизмы. 

                 unBackT
BackT m a <-------------------> MaybeT m (a, BackT m a)
            BackT(constructor)    

                              runMaybeT
MaybeT m (a, BackT m a) <------------------> m (Maybe (a, BackT m a))
                         MaybeT(constructor)

Таким образом, я на самом деле получаю что-то вроде 

m (Just(1, m (Just(2, m (Just(3, m (Just(4, Nothing))))))))

В приведенном выше примере есть 4 вычисления(Монада это вычисление?).Мне нужно что-то под названием runBackT, чтобы собрать их, используя [].

Спасибо за ответ от @rampion, и я удалил некоторые бессмысленные вопросы.

  • Какой тип результатов?Это должно быть что-то в зависимости от m. (Ответ: тип результатов должен быть m a.)
  • Как собрать все результаты?Возможно ли это? (Ответ: Монада m a не гарантирует наличия способа получить «развернутый» тип.)
  • Как собрать все аргументы, такие как 1, 2, 3, 4 впример.Это тип должен быть [a].Существует ли такая BackT m a -> [a] функция?Или мы можем получить только m [a]?(Ответ: может существовать только BackT m a -> m [a] .)

Обновление

Монаду можно разделить на два класса:«открытые монады» (например, [], Maybe) и «закрытые монады» (например, IO).«Открытые монады» имеют функции типа m a -> b для их открытия.например, 

showMaybe :: (Show a) => Maybe a -> String
showMaybe mx = case mx of
    Nothing -> "Nothing"
    Just x -> show x
  1. Как реализовать (Monad m, Show m) => BackT m a -> [String]?
  2. В общем, Monad m => (m a -> b) -> BackT m a -> [b]?
  3. При каких условиях существует Monad m => BackT m a -> [m a]?BackT m a последовательности вычислений m a рекурсивно по кросс-рекурсивному определению.Как превратить его в итерацию [m a]?Если он существует, как его реализовать?Мы можем сопоставить m a -> b с [m a], и вопрос (2) будет решен.
  4. Monad m => (m a -> a) -> BackT m a -> m [a]?Просто оберните результат вопроса (2) конструктором m.

Поэтому ключевым моментом является вопрос (3).

Самым сложным для меня является определение рекурсии BackT m a.Буду признателен, если вы покажете орудие или поделитесь советом.

Ответы только на вопрос (3) в порядке.

Обновление

Спасибо за комментарии @rampion, ListT из списка list-t ответил на мои вопросы.

1 Ответ

0 голосов
/ 10 мая 2018

Как собрать все аргументы, например 1, 2, 3, 4 в примере. Это тип должен быть [a]. Существует ли такая BackT m a -> [a] функция? Или мы можем получить только m [a]?

Сначала подумайте об этом наоборот.

Мы, безусловно, можем получить значение BackT m a для любого Monad m: 

Prelude> emptyBackT = BackT (MaybeT (return Nothing))
Prelude> :t emptyBackT
emptyBackT :: Monad m => BackT m a

И с силой fmap мы можем преобразовать любой m a в BackT m a для любого Functor m: 

Prelude> lift ma = BackT (MaybeT (fmap (\a -> Just (a, emptyBackT)) ma))
Prelude> :t lift
lift :: Monad m => m a -> BackT m a

Так что, если бы у нас был способ конвертировать любой BackT m a -> [a], мы могли бы объединить это с lift, чтобы получить m a -> [a] для любого Functor m!

Но мы знаем, что не можем этого сделать в Хаскеле. Некоторые функторы (например, [] или Maybe) развернуты, но есть другие (например, IO), которые не могут.

Так что runBackT должен иметь тип BackT m a -> m [a].

Что касается реализации, вот несколько наводящих вопросов.

У вас есть изоморфизм от BackT m a до m (Maybe (a, BackT m a)), поэтому

  • Предполагая, что runBackT :: BackT m a -> m [a] уже реализовано, не могли бы вы реализовать consBackT :: a -> BackT m a -> m [a]?
  • Предполагая, что runBackT :: BackT m a -> m [a] уже реализовано, не могли бы вы реализовать unwrapBackT :: Maybe (a, BackT m a) -> m [a]?
  • Предполагая, что unwrapBackT :: Maybe (a, BackT m a) -> m [a] уже реализовано, не могли бы вы реализовать innerToList :: m (Maybe (a, BackT m a)) -> m [a]?

(Подсказка: типы, которые я использовал в ведущих вопросах, являются неполными)

...