有什麼方法可以減少距離跟蹤的痛苦嗎？

Jonathan S.目前有pull request取代Data.IntMap的實現，其中this README的解釋基於Edward Kmett的blog post的想法。有什麼方法可以減少距離跟蹤的痛苦嗎？

的基本概念喬納森S.從開發是一個IntMap是二叉樹，看起來像這樣（我做了他的發展的一些細微變化的一致性的緣故）：

data IntMap0 a = Empty | NonEmpty (IntMapNE0 a) 
data IntMapNE0 a = 
    Tip !Int a 
    | Bin { lo :: !Int 
     , hi :: !Int 
     , left :: !(IntMapNE0 a) 
     , right :: !(IntMapNE0 a) }

在這種表示，每個節點都有一個字段，指示IntMapNE0中包含的最少和最大的密鑰。只使用一點點擺弄就可以將它用作PATRICIA特里。 Jonathan指出，這種結構的距離信息幾乎是其需要量的兩倍。在左側或右側脊柱後面將產生所有相同的lo或hi範圍。於是，他切出那些只包括約束，不得由祖先確定：

data IntMap1 a = Empty | NonEmpty { topLo :: !Int, child :: !(IntMapNE1 a) } 
data IntMapNE1 a = 
    Tip a 
    | IntMapNE1 { bound :: !Int 
       , left :: !(IntMapNE1 a) 
       , right :: !(IntMapNE1 a)

現在，每個節點有任何束縛左或約束的權利，但不能同時使用。一個正確的孩子只會有一個左邊界，而一個左邊的孩子只會有一個右邊界。

喬納森做了一個進一步的改變，將值移出樹葉並進入內部節點，這將它們放置在確定的位置。他還使用幻像類型來幫助追蹤左右。最終類型（現在，無論如何）是

data L 
data R 
newtype IntMap a = IntMap (IntMap_ L a) deriving (Eq) 
data IntMap_ t a = NonEmpty !Int a !(Node t a) | Empty deriving (Eq) 
data Node t a = Bin !Int a !(Node L a) !(Node R a) | Tip deriving (Eq, Show)

這個新實現的某些方面是相當有吸引力的。最重要的是，許多最常用的操作要快得多。不那麼重要，但非常好，涉及到的一點點擺弄更容易理解。

但是，有一個嚴重的問題：將遺漏的範圍信息傳遞到樹中。這對於查找，插入等來說並不是那麼糟糕，但是在聯合和交叉碼中變得非常嚴重。是否有一些抽象可以讓它自動完成？

一對夫婦極其模糊的想法：

能幻影類型的自定義類可用於治療綁直接用手習慣？
「缺失的部分」的性質有點讓人聯想到一些拉鍊的情況。有沒有辦法使用這個領域的想法？

我已經開始考慮使用一箇中間類型某種提供結構的對稱的「觀點」，但我有點卡住了。我可以很容易地在基本結構和花式結構之間來回轉換，但是這種轉換是遞歸的。我需要一種只能部分轉換的方式，但我不太瞭解花哨的構建類型來完成它。

來源

2016-09-15 dfeuer

雖然這很有趣，但我認爲你應該擴大這個問題。目前它太依賴外部鏈接，所以問題和答案應該大部分都是獨立的。 – Cubic

@Cubic，我想我修好了。 – dfeuer

如果你複製問題的「簡單」聯合/交集代碼的情況下，你會得到重複的界限信息，這可能會有幫助，所以我們可以嘗試修改它以處理更難的情況。 – Clinton

是否有一些抽象可以讓它自動完成？

你應該能夠定義一組給你的模式同義詞。我將從代碼的倒數第二個變體開始，即：

data IntMap1 a = Empty | NonEmpty { topLo :: !Int, child :: !(IntMapNE1 a) } 
data IntMapNE1 a = 
    Tip a 
    | IntMapNE1 { bound :: !Int 
       , left :: !(IntMapNE1 a) 
       , right :: !(IntMapNE1 a)

我們元組從在Either親本結合的這樣一個值（指示是否它是低或高約束）。

viewLoHi (Left lo, IntMapNE1 hi left right) 
    = Just (lo, hi, (Left lo, left), (Right hi, right) 
viewLoHi (Right hi, IntMapNE1 lo left right) 
    = Just (lo, hi, (Left lo, left), (Right hi, right) 
viewLoHi _ 
    = Nothing 

pattern Bin' lo hi left right <- (viewLoHi -> Just (lo, hi, left, right))

中的頂級數據類型是不同的，因此它需要自己的模式代名詞

viewLoHi' (NonEmpty lo child) = viewLoHi (Left lo, child) 
viewLoHi' Empty = Nothing 

pattern NonEmpty' lo hi left right <- (viewLoHi' -> Just (lo, hi, left, right)

只使用NonEmpty'和Bin'當你遍歷樹，簿記現在應該完全隱藏。（代碼沒有經過測試，所以這裏會出現拼寫錯誤）

來源

2017-03-29 21:17:50

有什麼方法可以減少距離跟蹤的痛苦嗎？

回答

相關問題