이진 트리 구조에서 스택 오버플로를 피하십시오.

Question

학습용으로 haskell을 배웠습니다. 이진 트리를 작성하기로했습니다.

까지 내가 이해할 수있는 것처럼 삽입과 삭제의 큰 세트는 결과 트리가 상대적으로 작더라도 마침내 평가를 시작할 때 스택 오버플로에 쉽게 도달 할 수 있습니다.

여기 내 질문은 다음과 같습니다

1. 난 내 기능에 약간의 엄격함을 도입하여이를 방지 할 수 있습니까? (뭔가 seq/deepseq?).

2. 상황에 따라 현재 상태에서 삽입/삭제를 유지하고 싶습니까?

내가 잘못 설계 한 것으로 느껴지면 코드를 수정하고 개선하십시오.

관련 코드 :

import Data.List 

data Tree a = Empty | Branch a (Tree a) (Tree a) 
       deriving (Eq) 

leaf x = Branch x Empty Empty 

-- insert ------------------------------------ 
treeInsert :: (Eq a, Ord a) => Tree a -> a -> Tree a 
treeInsert Empty x = leaf x 
treeInsert (Branch y l r) x | x<y = Branch y (treeInsert l x) r 
          | x>y = Branch y l (treeInsert r x) 
          | otherwise = Branch x l r --edit 


-- delete ------------------------------------ 
treeDelete :: (Eq a, Ord a) => Tree a -> a -> Tree a 
treeDelete Empty _ = Empty 
treeDelete (Branch y l r) x | y<x = Branch y l (treeDelete r x) 
           | y>x = Branch y (treeDelete l x) r 
           | y==x = del' $ Branch y l r 
    where 
    -- if this Branch is a leaf dispose of it. 
    -- if branch has only one child return the child (skip over). 
    -- otherwise, replace this branch with its successor (the leftmost child of the right tree) 
    --  successor will be extracted from its original location. 
    del' (Branch y Empty Empty) = Empty 
    del' (Branch y Empty r)  = r 
    del' (Branch y l Empty)  = l 
    del' (Branch y l r)   = Branch ySucc l rWithout_ySucc 

     where 
     (rWithout_ySucc, ySucc) = leftmost r 

      where 
      leftmost (Branch y Empty Empty) = (Empty, y) 
      leftmost (Branch y Empty r)  = (r, y) 
      leftmost (Branch y l r)   = (Branch y ll r, z) where (ll, z) = leftmost l 

Answer 1

전형적인 방법은 구조가 엄격하게 그것에 엄격한 기능을하는 것이 아니라 형식 자체를 변경하지 않는 것입니다.

이 경우

우리는

data Tree a = Empty | Branch a (Tree a) (Tree a) 

에

data Tree a = Empty | Branch a !(Tree a) !(Tree a) 

을 변경할 수 있습니다 그리고 이것은 당신이 Branch을 가지고있는 시간이 두 Tree들 포함, 또한 그들의 머리에 강제 것을 의미합니다 . 트리 안의 a은 엄격하지 않고 구조 자체이므로 spine-strict이라고하며 매우 일반적인 패턴입니다.

때때로이 작업을 수행하지 않으려는 이유는 모든 작업에 대해 "전체 비용"을 한꺼번에 지불해야하기 때문입니다. 트리에서 5 단계 아래로 요소를 삭제하면 5 단계의 재구성 한 번에 수행 할 수있는 새로운 트리가 있습니다. 반면에 실제로 이러한 경로를 살펴볼 필요가 없다면, 결코 그렇지 않을 것입니다.

그래서 올바른 이 점근 적 성능을 상각 얻기 위해, 당신은하지 추가 엄격를 추가 할 할 특정 구조 (Okasaki 잘 그들을 설명)이 있습니다.

실제로 사용 사이트에서 엄격함 을 적용하면 스택 오버플로를 피할 수 있습니다. 자, 빈 트리 위에 fold을 가지고 있다고 가정 해보십시오. foldl' (게으른 트리 포함)을 사용하면 게으른 폴드를 사용했을 때보 다 훨씬 적은 스택을 소비하게됩니다.