我的(尝试的)迭代M实现有什么问题？

Question

我想实现一个函数iterateM，它的类型是这样的:

iterateM :: Monad m => (a -> m a) -> a -> [m a]

然而，我第一次写这个函数:

iterateM f x = f x >>= (x' -> return x' : iterateM f x')

给出错误:

Could not deduce (m ~ [])
from the context (Monad m)
  bound by the type signature for
             iterateM :: Monad m => (a -> m a) -> a -> [m a]
  at main.hs:3:1-57
  `m' is a rigid type variable bound by
      the type signature for
        iterateM :: Monad m => (a -> m a) -> a -> [m a]
      at main.hs:3:1
Expected type: [a]
  Actual type: m a
In the return type of a call of `f'
In the first argument of `(>>=)', namely `f x'
In the expression: f x >>= ( x' -> return x' : iterateM f x')

如果我删除我的类型签名，ghci告诉我函数的类型是:

iterateM :: Monad m => (a -> [a]) -> a -> [m a]

我在这里错过了什么?

Answer 1

我从你的签名中得知:

iterateM :: (Monad m) => (a -> m a) -> a -> [m a]

表示n元素iterateM f x将是运行f n次的动作。这非常接近iterate，我怀疑我们可以在这方面实现它。

iterate :: (b -> b) -> b -> [b]

iterate给了我们一个b s的列表，我们想要一个m a s的列表，所以我怀疑是b = m a。

iterate :: (m a -> m a) -> m a -> [m a]

现在我们需要一种方法将f :: a -> m a转换为m a -> m a类型的东西。幸运的是，这正是bind:

的定义。

(=<<) :: (Monad m) => (a -> m b) -> (m a -> m b)

:

f -> iterate (f =<<) :: (a -> m a) -> m a -> [m a]

要将初始的x :: a转换为所需的m a，我们可以使用return:

return :: (Monad m) => a -> m a

:

iterateM f x = iterate (f =<<) (return x)

pointfreeze to taste.

Answer 2

你递归地使用iterateM是在强迫它在列表单子中。您需要运行iterateM操作并返回其结果。

试题:

iterateM f x = do
      x' <- f x
      xs <- iterateM f x'
      return $ x':xs