haskell - 如何用递归定义遍历 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 不保证有办法获得“未包装”类型。)
• 如何收集示例中的所有参数，例如 1、2、3、4。它的类型应该是[a]。这样的BackT m a -> [a] 函数存在吗？或者，我们只能得到m [a]吗？ (答案:只有BackT m a -> m [a]可能存在。)

<小时/>

更新

Monad 可以分为两类:“开放的 monad”(如 []、Maybe)和“封闭的 monad”(如 IO >)。 “打开的单子(monad)”具有类型为 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]?只需通过构造函数 m 包装问题(2) 的结果即可。

因此，关键点是问题(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]?

首先从相反的角度思考这个问题。

我们当然可以得到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 !

但我们知道在 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] ？

(提示:我在引导问题中使用的类型不完整)