1

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

toMap（第 13 页）

我会得到

> [(13,1)]

这是我到目前为止所拥有的：

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

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

4

2 回答 2

5

假设您有一个foldt跨树折叠的函数（以某种与当前应用程序无关的顺序），以及一些insertIncr插入或增加 a 中键的值的函数Map a Int，您可以将一个应用于另一个。

您将处理以下类型签名：

import Data.Map

foldt :: (a -> b -> b) -> b -> Tree a -> b
foldt f acc Empty = acc
foldt f acc (Node x l r) = acc'
    where accl = foldt f acc l
          accr = foldt f accl r
          acc' = f x accr

-- insert 1 if not present, increment if present
insertIncr :: Ord a => a -> Map a Int -> Map a Int
insertIncr = undefined

toMap' :: Ord a => Tree a -> Map a Int
toMap' = foldt insertIncr empty

该insertIncr函数可以使用例如Data.Map.insertWith来实现。请注意，Ord类型类对于将某些内容插入 Data.Map 是必需的。如果您更喜欢普通[(a,Int)]类型的地图，那么insertIncr可以使用 type Eq a => a -> [(a,Int)] -> [(a,Int)]。

编辑：将使用adjustWithKey的建议更改为insertWith。

于 2013-07-16T17:54:29.897 回答
2

老实说，这是一个我只需通过组合分解来解决的案例。

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

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

请注意，我必须在a. 它至少Eq需要完全可解，但Ord允许渐近更好的解决方案。

这里的基本思想是将解决方案分解为多个部分，然后再弄清楚每个部分。所以，下一部分是toList。我不会假设顺序很重要，因此我会选择前缀顺序，因为它很容易变得既懒惰又简单。

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

好的，很好，很简单。继续计算重复项。让我们也将其分解为几部分。

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

好的，我可能通过利用group和sort从Data.List. 但另一方面，这正是group要解决的问题。排序只是一切的标准工具。

如果我已经Control.Arrow导入，我会将 lambda 替换为(head &&& length). 但这只是一个标准的习语，并没有真正简化事情——它只是让它们打字更简洁。

这种方法的主要思想是将问题分解成可以自己做一些有意义的事情的部分。然后将这些部分组合成一个完整的解决方案。有一种方法可以将 aTree a转换为[a]. 还不如有一个功能来做到这一点。一旦你这样做了，剩下的部分就是一个有用的逻辑，可用于处理列表。如果你把它分解，你会发现它是现有位列表功能的简单组合。

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

于 2013-07-16T19:11:01.613 回答