代码之家 › 专栏 › 技术社区 › Bill

haskell中的monad和自定义遍历函数

monads haskell data-structures

Bill · 技术社区 · 16 年前

给出以下简单的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

这很好,但似乎是重复的——相同的逻辑已经存在于无序我在哈斯克尔的经历让我相信,如果我写了两次类似的东西,我可能会做错什么。

我有没有办法写出一个函数,它可以取纯函数,也可以取一元函数?

2 回复 | 直到 16 年前

Andrey Vlasovskikh 16 年前

在 inOrder 您正在映射 Tree x 致 [x] 也就是说,你把你的树按顺序排列。为什么不只用 mapM 或 mapM_ 在结果列表上?

mapM_ print $ inOrder tree

只是提醒一下我提到的函数类型:

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

Dietrich Epp 16 年前

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

尤其是,如果您实现 数据可折叠 类,您可以免费获得以下两个函数:

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

它还将为您提供丰富的功能集( foldr , concatMap , any ,…)用于列表类型。

您只需要实现以下函数之一,就可以创建 数据。可折叠 :

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

推荐文章

Piskator · 在Haskell中提取、操作和累积monad列表中的值

3 年前

Piskator · Haskells绑定运算符和>>运算符及其关系

3 年前

kaqqao · 理解读者单子

9 年前

user1 · 制作哈斯克尔单子

9 年前

Pedro Rolo · 生成解析器,该解析器在另一个解析器的输出上运行接收到的解析器,并以一元方式连接结果

9 年前

maiermic · 使用带透镜的一元函数修改状态

9 年前

Nathan Ringo · 将单子添加到transformer堆栈的中间

9 年前

Saurabh Nanda · 如何创建允许IO但不是MonadIO的monad?

9 年前

Bailey Parker · 处理optparse应用程序ReadM中openFile的异常

9 年前

Savenkov Alexey · Scalaz:如何组合OptionT[State[_],T]类型的单子,这样它就不会终止于None

9 年前