4

给定以下简单的 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 函数？

4

2 回答 2

11

在inOrder您将 a 映射Tree x到 a[x]时，即您对树进行排序。为什么不直接在结果列表中使用mapMor呢？mapM_

mapM_ print $ inOrder tree

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

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
mapM_ :: (Monad m) => (a -> m b) -> [a] -> m ()
于 2010-04-01T01:34:47.630 回答
7

您可能希望查看为您的树结构实现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
于 2010-04-01T01:54:35.707 回答