haskell - 有什么方法可以减轻距离跟踪的痛苦吗？

Question

目前有一个pull request由 Jonathan S. 替换 Data.IntMap 的实现一个在 this README 中解释基于来自 blog post 的想法爱德华·克米特。

Jonathan 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 trie。乔纳森指出，这种结构的范围信息几乎是它需要的两倍。跟随左或右脊椎将产生所有相同的 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)

现在每个节点都有一个左边界或右边界，但不是两者都有。右 child 只有左边界，而左 child 只有右边界。

Jonathan 进行了进一步的更改，将值从叶子移到内部节点中，这将它们准确地放置在确定的位置。他还使用幻像类型来帮助跟踪左右。最后的类型(现在，无论如何)是

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)

这个新实现的某些方面非常有吸引力。最重要的是，许多最常用的操作要快得多。不太重要，但非常好，所涉及的位摆弄更容易理解。

但是，有一个严重的痛点:将缺失的范围信息向下传递到树中。这对于查找、插入等来说并不是那么糟糕，但是在联合和交集代码中会变得非常棘手。是否有一些抽象可以自动完成？

几个非常模糊的想法:

幻像类型可以与自定义类一起使用以将治疗直接与惯用手联系起来吗？

“丢失的部分”性质有点让人想起一些 zipper 的情况。有没有办法使用那个领域的想法？

我已经开始考虑使用某种中间类型来提供结构的对称“ View ”，但我有点卡住了。我可以很容易地在基本结构和花哨的结构之间来回转换，但这种转换是递归的。我需要一种只进行部分转换的方法，但我对花哨构建的类型知之甚少，无法完成它。

Answer 1

Is there some abstraction that would allow this to be done automatically?

您应该能够定义一组给您的模式同义词。我将从您的代码的倒数第二个变体开始，即:

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'当您遍历树时，簿记现在应该完全隐藏。 (代码未测试，所以这里会有错别字)