将序列函数从foldr更改为递归函数

Question

我试图让我的头绕过序列函数。我认为这可能会有所帮助，如果我把它作为一个递归函数来写的话，但是我认为它是一个单调的表达式，我觉得有点难以转换为递归，所以我有点不知所措。我的意思是你用return（x：xs）做什么？换句话说，我想写没有foldr的函数。下面的两个定义我已经包括：

sequence _ = foldr k (return []) 
       where 
       k m m' = do { x <- m; xs <- m'; return (x:xs) } 

sequence' _ = foldr k (return []) 
       where 
        k m m' = m >>= 
          (\fstr -> m'>>= 
          (\rstr -> return (fstr:rstr))) 

Answer 1

一个写sequence方法就是traverse id，我会鼓励你去探索Traversable和Applicative之间的关系进行更深入的了解。

我想你要找的是什么这样的定义：

sequence :: Monad m => [m a] -> m [a] 
sequence [] = return [] 
sequence (x:xs) = do 
    x' <- x 
    xs' <- sequence xs 
    return (x':xs')