我(尝试)实现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第th个元素iterateM f x是一个运行f n时间的动作.这非常接近iterate,我怀疑我们可以用它来实现它.

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

iterate给我们一个bs 的列表,我们想要一个m as 的列表,所以我怀疑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尝尝.