如何遍歷具有Haskell monadic函數的樹的元素？

Question

我已經定義了一個代表一棵樹的新數據類型。我還實現了一個函數walk來遍歷樹的所有元素，函數的功能版本是正確的，但不是他的monadic版本walkM。

module Hdot where 
import qualified Data.ByteString.Char8 as B 
import qualified Data.Map as Map 

data RDoll a = Null | RDoll a [RDoll a] deriving (Show)  

test :: RDoll Int 
test = RDoll 1 [RDoll 2 [Null], RDoll 3 [RDoll 4 [Null]]] 

walk :: (a -> b) -> RDoll a -> [b] 

walk f Null   = [] 
walk f (RDoll x rds) = ((f x): (concatMap (\x -> walk f x) rds)) 

walkM :: (Monad m) => (a -> m b) -> RDoll a -> m [b] 
walkM f Null   = return [] 
walkM f (RDoll rd rdss) = do 
    x <- f rd 
    xs <- concatMap (walkM f) rdss 
    return (x:xs) 

有一種類型的錯誤

Couldn't match type `b' with `[b]' 
... 

有人可以幫我！

感謝您的任何答覆。

Answer 1

一般來說，你應該給予充分的錯誤消息，因爲它有價值的背景資料：

A.hs:19:26: 
    Could not deduce (m ~ []) 
    from the context (Monad m) 
     bound by the type signature for 
       walkM :: Monad m => (a -> m b) -> RDoll a -> m [b] 
     at A.hs:(16,1)-(20,15) 
     `m' is a rigid type variable bound by 
      the type signature for 
      walkM :: Monad m => (a -> m b) -> RDoll a -> m [b] 
      at A.hs:16:1 
    Expected type: [b] 
     Actual type: m b 
    Expected type: a -> [b] 
     Actual type: a -> m b 
    In the first argument of `walkM', namely `f' 
    In the first argument of `concatMap', namely `(walkM f)' 

因此，有值[b]和行動m b的列表之間有些混亂。

可疑代碼是您使用concatMap以遞歸方式運行walkM。我想你的意思是使用concatMapM（例如mapM和concat）：

walkM :: (Monad m) => (a -> m b) -> RDoll a -> m [b] 
walkM f Null   = return [] 
walkM f (RDoll rd rdss) = do 
    x <- f rd 
    xs <- mapM (walkM f) rdss 
    return (x:concat xs) 

---

由於風格上的說明，我想嘗試寫的東西有點不同。看看rose tree in the base library。特別是，不要定義walk和walkM，爲Functor，Monad定義實例並重用現有的庫函數。