如何使用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)

作为关于风格的说明,我试着写一些不同的东西.看看基础图书馆里的玫瑰树.特别是,不要定义walk和walkM定义Functor,Monad的实例并重用现有的库函数.