Есть ли способ уменьшить боль дальнего слежения?

Question

В настоящее время существует pull request от Jonathan S., чтобы заменить реализацию Data.IntMap на один поясненный в this README на основе идей от blog post от Edward Kmett.

Основная концепция 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) 

Теперь каждый узел имеет либо влево, связанные или право узника, но не оба. Правильный ребенок будет иметь только левую границу, а левый ребенок будет иметь только правую границу.

Джонатан делает еще одно изменение, перемещая значения из листьев и во внутренние узлы, что ставит их точно там, где они определены. Он также использует типы фантомов для отслеживания слева и справа. Конечным типом (на данный момент, во всяком случае) является

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. Могут типы фантомных быть использованы с помощью пользовательского класса, чтобы связать лечение непосредственно Handedness?

2. Природа «пропавших кусков» несколько напоминает некоторые ситуации на молнии. Может ли быть способ использовать идеи из этой сферы?

---

Я начал думать об использовании промежуточного типа какой-то, чтобы обеспечить симметричный «вид» структуры, но я немного застрял. Я могу довольно легко конвертировать назад и вперед между базовой структурой и причудливой, но это преобразование является рекурсивным. Мне нужен способ конвертировать только частично, но я не знаю почти достаточно о фантастически построенных типах, чтобы сделать это.

Answer 1

Есть ли абстракция, которая позволила бы это сделать автоматически?

Вы должны быть в состоянии определить набор синонимов шаблонов, которые вам дадут. Я начну с второго варианта последнего кода, т. Е.:

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' как вы обход дерева, бухгалтерские теперь должен быть полностью скрыты. (Код не проверен, поэтому здесь будут опечатки)