哈斯克尔树列表

哈斯克尔我们走吧！好了，所以这里是目前使用的代码示例：哈斯克尔树列表

data Tree a = Node (Tree a) (Tree a) | Leaf a | Empty deriving (Show) 
main = do 
let my_tree = Node (Node (Leaf [1,2,4,9]) (Leaf [3,5,5,8,5])) (Leaf [2,7,5,5,2]) 
cc my_tree 
bb my_tree 
aa my_tree 
cc my_tree 
print("Done")

只需在创建树保存诠释名单和需要3个职能工作AA，BB，CC：

CC - 简单地输出一棵树
BB - 广告，每个值+2
AA - 输出列表就像每个值：长度，最小值，最大值]

现在有，做这一切的代码几乎是完美的，我把它放在键盘（问我，如果你想）：http://codepad.org/ ??????? 现在你可以看到AA最后输出也是一棵树
它可能是一个速战速决，但我不能算出它 - 这样AA将输出不是树，但一个[这些]列表：

[length param,minimum param,maximum param]

换句话说，有人知道如何将它作为列表输出，而不是在树内？
所以在输出代替：

Node (Node (Leaf [4,1,9]) (Leaf [6,0,8])) (Leaf [5,2,7])

将

[[4,1,9],[6,0,8],[5,2,7]]

我相信有些事情在这里修改：

fmap3 ff (Node l r) = Node (fmap2 ff l) (fmap2 ff r) 
fmap3 ff (Leaf x) = Leaf (ff x)

任何人？

来源

2010-11-08 Florian Dardenua

这是功课？ – Paul 2010-11-08 17:57:30

您正在尝试执行减少操作：将树变成单个值（三次：长度，最大值，最小值）。这不能用map函数完成，因为按照定义，map总是将树变成树。

典型的归约算法使用函数将两个简化结果“合并”在一起，并递归合并树中任何位置获得的结果。所以，你就做这样的事：

reduce ff (Node l r) = ff (reduce ff l) (reduce ff r) 
reduce ff (Leaf x) = x

一旦做到这一点，你可以使用地图功能把你的（其他）到值的树被还原树，并应用减少功能。

cc tree = [ reduce (+) (fmap2 length tree) , 
      reduce (min) (fmap2 minimum tree) , 
      reduce (max) (fmap2 maximum tree) ]

编辑：你已经改变了你的问题，而我回答。您可以使用上述缩减函数和列表级联功能++来完成此操作，但列表级联在性能方面并不很性感。

有通过遍历与蓄能器参数把一棵树到列表中的惯用方式：

traverse init (Node l r) = traverse (traverse init r) l 
traverse init (Leaf x) = x : init 

cc tree = traverse [] (fmap2 h tree)

来源

2010-11-08 18:03:37

啊我明白了..好吧，我现在就试试吧！现在我只是尝试了第一部分：http：//codepad.org/1XPYIMOH – 2010-11-08 18:19:06

似乎它输出所有树的最大值，最小值，长度，现在尝试第二部分 – 2010-11-08 18:19:25

完美！现在，想出如何按照第三个参数的升序对最终结果进行排序（最大值） – 2010-11-08 18:22:27

这一个工程

data Tree a = EmptyTree | Node a (Tree a) (Tree a) 

treeToList :: (Ord a) => Tree a -> [a] 
treeToList EmptyTree = []   
treeToList (Node root left right) = treeToList left ++ [root] ++ treeToList right

来源

2014-01-17 16:58:17

哈斯克尔树列表

回答

相关问题