如何使用递归定义遍历 Monad 并收集结果？

Question

我实现了 monad 转换器 MaybeT。

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

然后，我写一个 monad 用于回溯。

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个计算（Monad是计算？）。我需要一个叫做 runBackT 的东西来使用 [].

收集它们

感谢@rampion 的回答，我删除了一些无意义的问题。

~~结果的类型是什么？应该是依赖m.~~的东西（答案：结果类型应该是m a.）
~~如何收集所有结果？有可能吗？~~（答案：Monad m a 不保证有办法得到一个 "unwrapped" 类型。）
如何收集示例中的所有参数，如 1、2、3、4。它的类型应该是[a]。这样的BackT m a -> [a]函数存在吗？或者，我们只能得到m [a]吗？（答案：只有 BackT m a -> m [a] 可能存在。）

更新

Monad可分为两个类："opened monads"（如[]、Maybe）和"closed monads"（如IO） . "opened monads" 具有类型为 m a -> b 的函数来打开它们。例如

showMaybe :: (Show a) => Maybe a -> String
showMaybe mx = case mx of
    Nothing -> "Nothing"
    Just x -> show x

如何实现(Monad m, Show m) => BackT m a -> [String]？
更一般地说，Monad m => (m a -> b) -> BackT m a -> [b]?
在什么条件下，Monad m => BackT m a -> [m a]存在？ BackT m a 序列计算 m a 通过交叉递归定义递归。怎么改成迭代[m a]？如果存在，如何实现？我们可以将m a -> b映射到[m a]，问题(2)就解决了。
Monad m => (m a -> a) -> BackT m a -> m [a]？只需将问题（2）的结果用构造函数 m.

因此，重点是问题(3)。

对我来说最困难的部分是BackT m a的递归定义。如果您能展示该工具或分享一些建议，我将不胜感激。

只回答问题 (3) 即可。

更新

感谢@rampion 的评论，ListT from list-t package 回答了我的问题。

Answer 1

How to collect all arguments like 1, 2, 3, 4 in example. It's type should be [a]. Does such a BackT m a -> [a] function exist? Or we can only get m [a]?

先反过来想一下。

我们当然可以得到任何 Monad m:

的 BackT m a 值

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 结合起来，以获得任何 Functor m!

的 m a -> [a]

但我们知道在 Haskell 中我们不能这样做。一些函子（如 [] 或 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]吗？

（提示：我在主要问题中使用的类型不完整）

如何使用递归定义遍历 Monad 并收集结果？

How to traverse a Monad with recursion definition and collect the results?

haskell

recursion

monads

monad-transformers