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

我实现了 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

如何实现 (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] ?只需通过构造函数 m 包装 question(2) 的结果。

因此，关键点是问题(3)。

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

仅对问题 (3) 的回答是可以的。

更新

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

最佳答案

先换个角度想一想。

我们当然可以得到任何 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] 吗？

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

关于haskell - 如何使用递归定义遍历 Monad 并收集结果？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50276622/