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

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

0 голосов
/ 01 января 2019

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

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

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

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/~nr/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.

1 Ответ

0 голосов
/ 01 января 2019

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

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

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

действительно является хвостовой рекурсивной, но все жеесть проблема: он ни в коем случае не «форсирует» дерево, пока оно строится.Из-за лени Хаскелла go вернет thunk , который скрывает 10000000 ожидающих приложений L.cons.

Когда среда выполнения пытается «вытолкнуть» этот thunk, он поместит каждую переменную n в стек, в то время как thunk ниже «выталкивается» в свою очередь, вызывая переполнение стека. "Вызовы функций не добавляют стековые фреймы в Haskell; вместо этого стековые фреймы получаются из вложенных групп."т накопить.Этого должно быть достаточно (используя расширение 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 не нужно вводить принудительно, потому что он тщательно проверяется на соответствие шаблону.

...