有没有办法减少范围跟踪的痛苦？

Question

目前,Jonathan S. 提出了拉取请求,根据Edward Kmett撰写的博客文章中的想法取代本自述文件中Data.IntMap解释的实现.

Jonathan S.开发的基本概念IntMap是a是一个看起来像这样的二叉树(为了保持一致性,我对他的开发做了一些细微的改动):

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.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)

现在每个节点都有左边界或右边界,但不是两个.一个正确的孩子只有一个左边界,而一个左边的孩子只有一个右边界.

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)

这种新实现的某些方面非常有吸引力.最重要的是,许多最常用的操作都要快得多.不太重要,但非常好,所涉及的小小提琴更容易理解.

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

一对非常含糊的想法:

1. 幻影类型可以与自定义类一起使用,直接将治疗与手性联系起来吗？

2. "缺失的部分"性质有点让人联想到一些拉链情况.可能有办法使用该领域的想法吗？

---

我开始考虑使用某种类型的中间类型来提供结构的对称"视图",但我有点卡住了.我可以很容易地在基本结构和花哨的结构之间来回转换,但转换是递归的.我需要一种只能部分转换的方法,但我不太了解有关完美构建的类型以完成它.

Answer 1

\n

是否有一些抽象可以让这一切自动完成？

\n

\n\n

您应该能够定义一组模式同义词来实现这一点。I\xe2\x80\x99ll 从代码的倒数第二个变体开始，即：

\n\n

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

\n\n

我们将这样的值与来自父级的边界元组化Either（指示它是下限还是上限）。

\n\n

viewLoHi (Left lo, IntMapNE1 hi left right)\n    = Just (lo, hi, (Left lo, left), (Right hi, right)\nviewLoHi (Right hi, IntMapNE1 lo left right)\n    = Just (lo, hi, (Left lo, left), (Right hi, right)\nviewLoHi _\n    = Nothing\n\npattern Bin' lo hi left right <- (viewLoHi -> Just (lo, hi, left, right))\n

\n\n

顶级数据类型不同，因此需要自己的模式同义词

\n\n

viewLoHi' (NonEmpty lo child) = viewLoHi (Left lo, child)\nviewLoHi' Empty = Nothing\n\npattern NonEmpty' lo hi left right <- (viewLoHi' -> Just (lo, hi, left, right)\n

\n\n

仅使用NonEmpty'和Bin'当您遍历树时，簿记现在应该完全隐藏。（代码没有经过测试，所以这里会有错别字）

\n