哈斯克尔：把一棵树变成一张地图 [英] Haskell: Turning a tree into a map

问题描述

基本上我想把BST树变成一个映射，其中节点是键，节点出现的次数是值。所以如果我输入这个：

toMap（第13页）

我会得到

 > [（13,1）] 
  

以下是我到目前为止：

 数据树a =空|节点a（树a）（树a）派生（显示）
叶x =节点x空空
 
 toMap':: Int  - >树a  - > （[（a，Int）]，Int）
 toMap'a Empty =（[]，a）
 toMap'a（节点x xl xr）=（（x，a）：xl'+ + xr'，k）
其中（xl'，i）= toMap'（a + 1）xl 
（xr'，k）= toMap'（i）xr 
 
 toMap :: Tree a  - > [（a，Int）] 
 toMap = fst。 toMap'1 
  

该程序返回一张地图，但这些值不正确。每个值比前一个值大1（因此如果有3个节点，那么第三个节点的值将是3）。我想我必须在每个新钥匙上放置一个计数器，但我不确定如何。提前致谢

解决方案

老实说，这是一个我只是解决构图故障的案例。 b
$ b

 数据树a =空|节点a（树a）（树a）派生（显示）
 
 toMap :: Ord a =>树a  - > [（a，Int）] 
 toMap = countDups。 toList 
  

请注意，我必须在 a 。它至少需要 Eq 才能解决，但 Ord 允许渐进式更好的解决方案。

这里的基本思想就是将解决方案分解成若干部分，并在稍后确定每个部分。所以，下一部分是 toList 。我不会假定订单很重要，因此我会选择一个前缀排序，因为很容易使懒惰和简单。

  toList :: Tree a  - > [a] 
 toList Empty = [] 
 toList（Node alr）= a：toList l ++ toList r 
  

好，很好，很直接。开始计数重复项。让我们把它分解成几块。

  countDups :: Ord a => [a]  - > [（a，Int）] 
 countDups = map（\ xs  - >（head xs，length xs））。组。 
  

好的，我可能会利用 group 和 sort from Data.List 。但另一方面，正是这种问题 group 是要解决的问题。如果我有 Control.Arrow 导入，我会替换它。

λ（head&& length）的lambda。但这只是一个标准成语，并不能真正简化事物 - 它只是让它们更简洁一些。

这种方法的主要思想是将问题分解成能自己做一些有意义的事情的小块。然后将这些碎片组合成一个完整的解决方案。有一种方法可以将 Tree a 转换为 [a] 。也可能有这样做的功能。一旦你这样做了，剩下的一块是有用的逻辑处理列表。如果你打破了这一点，你会发现它是现有位列表功能的简单组合。

这通常是解决任何编程语言问题的最佳方法之一 - 把大任务分解成更小的任务。在Haskell中做这件事的好处在于，将较小的任务组合到整个过程中是一个非常简洁的过程。

Basically I want to turn a BST tree into a map where the nodes are the keys and the number of occurrences of the nodes are the values. So if I inputted this:

toMap (leaf 13)

I would get

> [(13,1)]

Here is what I have so far:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
leaf x = Node x Empty Empty

toMap' :: Int -> Tree a -> ([(a, Int)], Int)
toMap' a Empty = ([], a)
toMap' a (Node x xl xr) = ((x, a): xl' ++ xr', k)
                      where (xl', i) = toMap' (a+1) xl
                            (xr', k) = toMap' (i) xr

toMap :: Tree a -> [(a, Int)]
toMap = fst. toMap' 1

This program returns a map but the values are incorrect. Each value is one greater than the previous value (so if there are 3 nodes than the value of the third node will be three). I think I have to place a counter on each new key, but I'm not sure how. Thanks in advance

解决方案

Honestly, this is a case that I'd just solve with a compositional breakdown.

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

toMap :: Ord a => Tree a -> [(a, Int)]
toMap = countDups . toList

Note that I had to add an extra constraint on a. It needs at least Eq to be solvable at all, but Ord allows asymptotically better solutions.

The basic idea here is just breaking the solution down into parts, and figuring out each part later. So, the next part is toList. I'm not going to assume the order matters, and as such I'll choose a prefix ordering, since it's easy to make both lazy and simple.

toList :: Tree a -> [a]
toList Empty = []
toList (Node a l r) = a : toList l ++ toList r

Ok, nice and straightforward. On to counting the duplicates. Let's break this down into a few pieces, too.

countDups :: Ord a => [a] -> [(a, Int)]
countDups = map (\xs -> (head xs, length xs)) . group . sort

Ok, I may have slightly cheated there by taking advantage of group and sort from Data.List. But on the other hand, this is exactly the kind of problem group is meant to solve. And sorting is just a standard tool for everything.

If I had Control.Arrow imported, I'd replace the lambda with (head &&& length). But that's just a bit of a standard idiom that doesn't really simplify things - it just makes them a bit more succinct to type.

The main idea of this approach is breaking down the problem into pieces that do some meaningful thing on their own. Then compose those pieces together into a full solution. It's handy to have a way to convert a Tree a into a [a]. Might as well have a function that does that. And once you do, the remaining piece is a useful bit of logic to have available for processing lists. And if you break that down, you find it's an easy composition of existing bits list functionality.

This is often one of the best ways to solve problems in any programming language - break the big task down into smaller tasks. What's nice about doing it in Haskell is that composing the smaller tasks into the full process is a nicely succinct process.

这篇关于哈斯克尔：把一棵树变成一张地图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！