Haskell:把一棵树变成一张地图

Question

基本上我想将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个).我想我必须在每个新钥匙上放置一个计数器,但我不确定如何.提前致谢

Answer 1

假设您有一个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可以选择类型Eq a => a -> [(a,Int)] -> [(a,Int)].

编辑:使用的变更建议adjustWithKey到insertWith.