Haskell二叉树函数（地图）

如何定义一个Haskell函数，该函数将函数应用于二叉树中的每个值？所以，我知道这是类似于map功能 - 以及它的类型是：Haskell二叉树函数（地图）

mapT :: (a -> b) -> Tree a -> Tree b

但是那它...

来源

2010-05-03 Bizarro

这是功课吗？如果是这样，请相应标记。 – Thomas 2010-05-03 07:21:51

'mapT = fmap'？ – kennytm 2010-05-03 08:34:12

我会假装这是功课，而不是放弃所有的答案。如果我错了，我的道歉。

可能是你Tree型看起来是这样的：

data Tree a = TreeNode a (Tree a) (Tree a) | EmptyNode

这里有两种情况，你将需要编写一个mapT实施为他们每个人：

内部节点， TreeNode，其中携带a类型的值，并具有左侧和右侧孩子。在这种情况下需要做什么？
终端节点，EmptyNode。在这种情况下需要做什么？

来源

2010-05-03 07:25:42 Thomas

有趣的问题，如果输入和输出应该是排序二叉树。如果您只是天真地遍历树并应用该函数，则输出树可能不再被排序。例如，考虑如果函数是非线性的，如

f(x) = x * x - 3 * x + 2

如果输入具有{1，2，3，4}，那么输出将具有{2，0，0，2}。输出树应该只包含0和2吗？

如果是这样，当您剥离并处理输入树时，您可能需要迭代地构建输出树。

来源

2010-05-03 07:29:05 Dan

你说得对，在许多情况下这是一个问题，但我认为这可能是在OP的情况下过于复杂。并非所有的二叉树都具有它们的元素都是唯一的，甚至按特定顺序排序的属性。例如，二叉树可以用廉价的随机插入来模拟列表。 – Chuck 2010-05-03 07:41:31

@Chuck：好点。 – Dan 2010-05-03 08:13:30

地图功能的基本格式适用于两者。让我们看一下地图功能的定义列表：

map f (x:xs) = f x : map f xs 
map _ []  = []

我们可以概括这个像这样：

你把数据结构
的第一个值应用功能，它
用数据结构的其余部分递归调用您的映射函数
将修改后的值和递归调用传递到您的类型的构造函数中。
当你到达终点，停止递归

您真正需要的是看你的构造和地图功能应该水到渠成。

来源

2010-05-03 07:34:32 Chuck

自从我编写任何Haskell之后已经很长时间了......应该不是'map f（x：xs）= f x：map f xs'？ – Dan 2010-05-03 07:37:06

绝对，谢谢。对不起，我很粗心。 – Chuck 2010-05-03 07:42:47

您可以声明类Functor的实例。这是允许映射函数的数据类型的标准类。请注意，fmap类型的相似是你mapT的类型：

class Functor f where 
    fmap :: (a -> b) -> f a -> f b

让我们假设你的树被定义为

data Tree a = Node (Tree a) (Tree a) | Leaf a 
    deriving (Show)

然后你就可以申报Functor一个实例是这样的：

instance Functor Tree where 
    fmap f (Node l r) = Node (fmap f l) (fmap f r) 
    fmap f (Leaf x) = Leaf (f x)

这就是你如何使用它：

main = do 
    let t = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3) 
    let f = show . (2^) 
    putStrLn $ "Old Tree: " ++ (show t) 
    putStrLn $ "New Tree: " ++ (show . fmap f $ t)

输出：

Old Tree: Node (Node (Leaf 1) (Leaf 2)) (Leaf 3) 
New Tree: Node (Node (Leaf "2") (Leaf "4")) (Leaf "8")

您也可以定义为方便起见：

mapT = fmap

当然，你可以不用类型的类，但它使别人，如果你的代码更易读使用标准功能（每个人都知道fmap的常见行为）。

来源

2010-05-03 11:05:56 sastanin

Haskell二叉树函数（地图）

回答

相关问题