如何遍历具有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定义实例并重用现有的库函数。