data-structures - Haskell 中的 Monad 和自定义遍历函数

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

这工作正常，但似乎重复 - 中已经存在相同的逻辑订购 我在 Haskell 方面的经验让我相信，如果我写了两次类似的东西，我可能做错了。

有什么方法可以编写一个可以采用纯函数或单子(monad)函数的 inOrder 函数？

Answer 1

在 inOrder您正在映射 Tree x到 [x] ， 一世。 e.你对你的树进行排序。为什么不直接使用 mapM或 mapM_在结果列表中？

mapM_ print $ inOrder tree

只是为了提醒我提到的函数的类型:

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