Haskell中的Monads和自定义遍历函数

Question

鉴于以下简单的BST定义:

data Tree x = Empty | Leaf x | Node x (Tree x) (Tree x)
          deriving (Show, Eq)

inOrder :: Tree x -> [x]
inOrder Empty                  = []
inOrder (Leaf x)               = [x]
inOrder (Node root left right) = inOrder left ++ [root] ++ inOrder right

我想编写一个可能有副作用的有序函数.我用以下方法实现了:

inOrderM :: (Show x, Monad m) => (x -> m a) -> Tree x -> m ()
inOrderM f (Empty) = return ()
inOrderM f (Leaf y) = f y >> return ()
inOrderM f (Node root left right) = inOrderM f left >> f root >> inOrderM f right

-- print tree in order to stdout
inOrderM print tree

这样做很好,但看起来很重复 - 在inOrder中已经存在相同的逻辑,而我对Haskell的经验让我相信,如果我写两次类似的东西,我可能做错了.

有没有什么方法可以编写单个函数inOrder,可以采用纯函数还是单函数？

Answer 1

在inOrder您将a映射Tree x到a [x],即您对树进行顺序化.为什么不在结果列表中使用mapM或mapM_？

mapM_ print $ inOrder tree

只是为了提醒我提到的功能类型:

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
mapM_ :: (Monad m) => (a -> m b) -> [a] -> m ()

Answer 2

您可能希望查看为树结构实现Data.Traversable类或Data.Foldable类.每个只需要定义一个方法.

特别是,如果实现Data.Foldable该类,则可以免费获得以下两个函数:

mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
toList :: Foldable t => t a -> [a]

它也会给你丰富的功能集(foldr,concatMap,any你是用来与列表类型使用,...).

您只需要实现以下功能之一来创建以下实例Data.Foldable:

foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b