haskell - 我的(尝试的)iterateM 实现有什么问题？

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)

Pointfreeize 品尝。