Haskell：將樹變成地圖

基本上我想將BST樹變成一個映射，其中節點是鍵，節點的出現次數是值。所以，如果我輸入的是：Haskell：將樹變成地圖

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

這個程序返回地圖但值不正確。每個值比前一個值大1（因此如果有3個節點，那麼第三個節點的值將是3）。我想我必須在每個新鑰匙上放置一個計數器，但我不確定如何。在此先感謝

來源

2013-07-16 user2548080

另請參閱[這個答案]（http://stackoverflow.com/a/9498623/1598537）;如果你把它做成'可摺疊'，你可以將它摺疊成一張整潔的地圖。 – AndrewC

老實說，這是一個我只是解決構圖故障的情況。

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

好吧，我可有輕度從Data.List採取的group和sort優勢被騙那裏。但另一方面，這正是group要解決的問題。排序只是一切的標準工具。

如果我輸入了Control.Arrow，我會用(head &&& length)替換lambda。但這只是一個標準成語，並不能真正簡化事物 - 它只是讓它們更簡潔一些。

這種方法的主要思想是將問題分解成單獨做一些有意義的事情。然後將這些碎片組合成一個完整的解決方案。有一種方法可以將Tree a轉換爲[a]。也可能有這樣做的功能。一旦你這樣做了，剩下的一塊是有用的邏輯處理列表。如果你打破這一點，你會發現它是一個簡單的現有位列表功能組合。

這通常是解決任何編程語言中問題的最佳方法之一 - 將大任務分解爲更小的任務。在Haskell中做這件事的好處在於，將較小的任務組合到整個過程中是一個非常簡潔的過程。

來源

2013-07-16 19:11:01 Carl

非常感謝！這不僅工作，但我學到了很多關於如何編寫程序的方法。我還選擇了一些將在未來有用的新功能。再次感謝！ – user2548080

@ user2548080：Simons解決方案雖然更有效 - 我用好奇心測試了它，使用1..150數字循環重複構建的樹。西蒙的解決方案可以在同一時間處理大約20萬個元素（大約半秒鐘），卡爾的解決方案可以達到10,000個。如果你有很多數據，請小心「簡單」的事情，比如「排序」。另外，摺疊是用於在高層表達許多類似問題的適當思想構造。 – firefrorefiddle

或者，可以定義'toList = foldt（:) []'。 :)對於漸近比較，在Data.Map中進行樹摺疊和插入是O（n lg n）（n代表元素的數量，lg n代表插入到基於樹的地圖中），而countDups '是O（n lg n + n + n）（n lg n用於排序，n用於分組，n用於長度）。即使排序是這裏的漸近壞人，但我很想去考慮這個長度也是怪罪。我不知道記憶是否是真正的壞人。 –

假設你有一個函數foldt跨樹倍（以某種順序無關當前應用程序），以及一些功能insertIncr是插入或增加一個關鍵的一個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的更改建議。

來源

2013-07-16 17:54:29

如果鍵不在地圖中，'adjustWithKey'將忽略插入。一個合適的定義是'Data.Map.insertWith（+）k 1' – firefrorefiddle

Haskell：將樹變成地圖

回答

相關問題