將序列函數從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')