Переполнение стека при построении/оценке красно-черного дерева в Haskell

У меня есть следующее красное черное дерево:

data Tree a
  = E
  | S a
  | C !Color !(Tree a) !(Tree a)

data Color = R | B

В случае этого дерева все данные хранятся в листьях (конструктор S). Я написал функцию insert наподобие стандартных красно-черных деревьев Окасаки[1] (изменив части, в которых значения хранятся во внутренних узлах).

В этом случае я заполняю дерево 10 миллионами элементов:

l = go 10000000 E
  where
    go 0 t = insert 0 t
    go n t = insert t $ go (n - 1) t

Когда я пытаюсь оценить самый левый элемент (лист) дерева следующим образом:

left :: Tree a -> Maybe a
left E = Nothing
left (S x) = Just x
left (C _ _ l _) = left l

Я сталкиваюсь со следующим:

левый л

*** Исключение: переполнение стека

Это связано с тем, как я строю дерево (не хвостовое рекурсивное), или есть какая-то недостающая утечка пространства, которую я не вижу.

Обратите внимание, что функция отлично работает для миллиона элементов. Кроме того, я попытался использовать хвостовой рекурсивный способ построения дерева:

l = go 10000000 E
  where
    go 0 t = insert 0 t
    go n t = go (n - 1) (insert n t)

но столкнулся с тем же исключением переполнения стека.

[1] https://www.cs.tufts.edu/%7Enr/cs257/archive/chris-okasaki/redblack99.pdf

ИЗМЕНИТЬ

Функция вставки и баланса для полноты:

 insert :: Ord a => a -> Tree a -> Tree a
 insert x xs = makeBlack $ ins xs
   where
     ins E = S x
     ins (S a) = C R (S x) (S a)
     ins (C c l r) = balance c (ins l) r -- always traverse left and trust the balancing
 
     makeBlack (C _ l r) = C B l r
     makeBlack a = a
 
 balance :: Color -> Tree a -> Tree a -> Tree a
 balance B (C R (C R a b) c) d = C R (C B a b) (C B c d)
 balance B (C R a (C R b c)) d = C R (C B a b) (C B c d)
 balance B a (C R (C R b c) d) = C R (C B a b) (C B c d)
 balance B a (C R b (C R c d)) = C R (C B a b) (C B c d)
 balance color a b = C color a b

С моей стороны была опечатка при вводе кода вставки, это insert n $ go (n - 1) t, а не insert t $ go (n - 1) t. Однако, когда на самом деле возникло переполнение стека, код был правильным, и переполнение произошло в ghci.


functional-programming data-structures lazy-evaluation red-black-tree haskell
person Abhiroop Sarkar    schedule 01.01.2019    source источник
comment
Возможно, вам следует опубликовать MCVE.   -  person chi    schedule 01.01.2019
comment
@chi Я добавил вставку и баланс, чтобы обеспечить полноту.   -  person Abhiroop Sarkar    schedule 01.01.2019
comment
Мне пришлось немного отладить ваш код, чтобы он скомпилировался. После этого правда много памяти выделяет. Мне удалось запустить его с 10 миллионами элементов (используя GHC, а не GHCi), но при этом потребовалось несколько ГБ ОЗУ. Возможно, это требует ~ 500B/элемент. Можно использовать распаковку, чтобы уменьшить эти накладные расходы. Я не уверен, сколько памяти мы можем сохранить здесь.   -  person chi    schedule 01.01.2019
comment
@melpomene Добавлен тип цвета   -  person Abhiroop Sarkar    schedule 01.01.2019
comment
@chi Да, на моей машине, используя решение dandiaz, программа выделяет около 14 ГБ памяти.   -  person Abhiroop Sarkar    schedule 01.01.2019

Ответы (1)


arrow_upward
3
arrow_downward

В первом примере кода вставки есть ошибка: он пытается вставить само дерево как элемент.

Вторая версия

l = go 10000000 L.empty   where
    go 0 t = L.cons 0 t
    go n t = go (n - 1) (L.cons n t)

Действительно хвостовая рекурсия, но у нее все еще есть проблема: она ни на каком шаге не "форсирует" дерево, пока оно строится. Из-за лени Haskell go вернет преобразователь, который скрывает 10000000 ожидающие заявки L.cons.

Когда среда выполнения пытается «вытолкнуть» этот преобразователь, она поместит каждую переменную n в стек, в то время как преобразователь ниже, в свою очередь, «извлекается», вызывая переполнение стека. "Вызовы функций не добавляют кадры стека в Haskell; вместо этого кадры стека получаются из вложенных транков ."

Решение состоит в том, чтобы заставить каждое промежуточное дерево использовать WHNF, чтобы не накапливались переходники. Этого должно быть достаточно (используя расширение BangPatterns) :

l :: Tree Int 
l = go 10000000 L.empty
  where
    go 0 !t = L.cons 0 t
    go n !t = go (n - 1) (L.cons n t)

В основном это означает: «перед повторным добавлением другого элемента убедитесь, что аккумулятор находится в WHNF». n не нужно навязывать, потому что он тщательно проверяется при сопоставлении с образцом.

person danidiaz    schedule 01.01.2019
comment
На моей машине вышеуказанное выполняется со следующим: 14 786 460 656 байтов, выделенных в куче 2 669 788 232 байта, скопированных во время GC 598 027 032 байта максимального резидентства (12 образцов(ов)) 1 447 144 байта максимального slop 1169 МБ общей используемой памяти (0 МБ потеряно из-за фрагментации) Это нормально или используется избыточное распределение? Дополнительные флаги компилятора не передаются. - person Abhiroop Sarkar; 01.01.2019
comment
@AbhiroopSarkar (598027032 байта максимального места жительства / 10000000) дает около 60 байтов на узел, что на самом деле кажется мне низким, учитывая, как определена структура. (В качестве нижней границы потребления памяти мы должны хранить один Int для каждого элемента, а также указатель на него...) - person danidiaz; 01.01.2019