constructing/evaluating 红黑树在 Haskell 时堆栈溢出

Question

我有以下红黑树：

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

data Color = R | B

对于这棵树，所有数据都存储在叶子（S 构造函数）中。我已经写了一个 insert 函数，就像标准的冈崎红黑树 [1] （修改了值存储在内部节点中的部分）

在这种情况下，我用 1000 万个元素填充树：

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

*** Exception: stack overflow

这是因为我构建树的方式（非尾递归）还是有一些我看不到的遗漏 space 泄漏。

请注意该函数适用于一百万个元素。另外，我尝试了树构造的尾递归方式：

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中。

Answer 1

插入代码的第一个示例有一个错误：它试图将树本身作为元素插入。

第二个版本

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

确实是尾递归，但它仍然有一个问题：它在构建树时的任何一步都没有"force"。由于 Haskell 的懒惰，go 将 return 隐藏 L.cons 的 10000000 个待处理申请的 thunk。

当运行时尝试"pop"那个thunk时，它会将每个n变量放入堆栈，而下面的thunk轮到"popped"，导致堆栈溢出. "Function calls don't add stack frames in Haskell; instead, stack frames come from nesting thunks."

解决方案是强制每个中间树为 WHNF，这样 thunk 就不会累积。这应该足够了（使用 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)

这基本上意味着："before recursing to add another element, make sure the accumulator is in WHNF"。 n 不需要强制，因为它在模式匹配中被仔细检查。

constructing/evaluating 红黑树在 Haskell 时堆栈溢出

Stack overflow when constructing/evaluating a red black tree in Haskell

haskell

data-structures

functional-programming

lazy-evaluation

red-black-tree