트리에서 노드 계산하기

Question

f #으로 싸우는 것 - 싸움은 나무의 영역에 있으며 특히 노드 수를 세는 것입니다. 이것은 결국 F #에서 멀티 - 웨이 나무에 관한 코드를 작성하고자하는 프로그램으로 불행히도 번거로운 시작이되어 버렸습니다. 아마도 도움이되기를 바랍니다!

99 f # 시리즈의 61 번 문제는 이진 트리의 잎 수를 계산하도록 요청합니다. (아래)이 솔루션은 노드를 계산하지만 내 문제는 이중 재귀 루프 왼쪽 어떻게 작동하는지

• 이해되지 않는다 (재미 LACC를 -> 루프를 잘 ..) cont (branchF x lacc racc)이 무엇인지

• 을 내 인상은 계속이 "ABC"기능이라고했지만,이

• loop t id ID가 형 유닛으로 만 두 개의 매개 변수를 걸립니다 ... -이 함축되어 표시되지 않습니다

기본적으로이 내용을 이해하지 못하거나 트리를 통과하는 순서입니다 (디버그 & 단계는 도움이되지 않음). 간단한 예제가있는 경우 미리 읽는 것이 좋습니다. 어떤 도움

많은 감사, 문제의 해결책 코드는 다음과 같습니다 : 이름이 의미

건배

TD

type 'a Tree = Empty | Branch of 'a * 'a Tree * 'a Tree 

let foldTree branchF emptyV t = 
    let rec loop t cont = 
     match t with 
     | Empty -> 
      cont emptyV 
     | Branch (x, left, right) -> 
      loop left (fun lacc -> 
       loop right (fun racc -> 
        cont (branchF x lacc racc))) 
    loop t id 

let counLeaves tree = 
    foldTree (fun abc lc rc -> 
     if lc + rc = 0 then 1 
     else 1 + lc + rc) 0 tree 

let Tree1 = Branch ('x', Branch ('x', Empty, Empty),Branch ('x', Empty, Branch ('x', Empty, Branch ('x', Empty, Empty)))) 


let result = counLeaves Tree1 

Answer 1

으로 foldTree 사용자 정의 Tree 유형을 통해 배 함수를 정의 .

foldTree을 정의하는 순진 방법이 될 수있다 :

let rec foldTreeNaive accFun init = function 
    | Empty -> init 
    | Branch (x, left, right) -> 
     let lacc = foldTreeNaive accFun init left 
     let racc = foldTreeNaive accFun init right 
     accFun x lacc racc 

이 기능의 문제는 나무가 깊은 접힌되는 경우는 가능성이 있기 때문에 재귀 호출해야합니다 매우 깊은 재귀 호출을 만들 수 있다는 것입니다 누적 기 함수가 호출되기 전에 노드에 대해 완료하십시오. 대신, 수 있도록 두 개의 재귀 호출이 있기 때문에 그러나 이것은이 경우에는 불가능 보인다

let unbalanced = [1..100000] |> List.fold (fun t i -> Branch(i, t, Empty)) Empty 
let nodeCount = foldTreeNaive (fun _ lc rc -> lc + rc + 1) 0 unbalanced 

같은 스택 오버 플로우를 방지하는 일반적인 방법은 함수 꼬리 재귀를 만드는 것입니다 : 예를 들어, 다음은 스택 오버플로 예외가 발생합니다 목록을 접을 때 필요한 것 중 하나입니다.

foldTree은 로컬 loop 기능을 사용하여 정의됩니다. 이 함수는 continuation passing style을 사용하여 정의된다는 점에서 흥미 롭습니다. CPS에서 각 함수는 계산 결과를 전달하는 추가 '연속'함수를 사용하며 다음에 어떤 일이 발생할지 결정합니다. loop은 꼬리 재귀 적이므로 foldTreeNaive의 오버플로 문제는 피할 수 있습니다.

loop 함수의 종류 :

Tree<'a> -> ('b -> 'c) -> 'c 

A는 트리의 노드의 종류가되고, 'B는 C는 연속 함수의 결과는'축적 형이고.

리프 노드의 경우, 연속은 foldTree 함수에 전달 된 빈 누적 기 값을 전달합니다.

Branch의 비어 있지 않은 트리를 폴딩 할 때 폴드 결과는 왼쪽 및 오른쪽 하위 트리의 결과에 따라 다릅니다. 이것은 재귀 적으로 수행됩니다. 먼저 왼쪽 하위 트리를 접은 다음 오른쪽을 접습니다. 왼쪽 하위 트리를 통해 재귀 호출의 경우, loop는 결과를 받기 위해 새로운 계속을 구축해야하며, 이것은

(fun lacc -> 
    loop right (fun racc -> 
     cont (branchF x lacc racc)) 

기능입니다. 이 연속체가하는 일은 오른쪽 하위 트리에 대한 재귀 호출을 작성하고 그 연속의 결과를 수신하는 또 다른 연속을 전달하는 것입니다. 해당 연속이 호출되면 왼쪽 및 오른쪽 하위 트리에 대한 결과는 lacc 및 racc에서 사용할 수 있습니다. 이 시점에서 현재 노드의 값과 왼쪽 및 오른쪽 하위 트리의 결과를 사용하여 노드의 누적 함수를 호출 할 수 있습니다. 이 함수의 결과는 loop에 전달 된 원래 연속으로 전달됩니다.

loop 기능

다음 줄에 foldTree 기능에 의해 호출됩니다

여기

loop t id 

, id는 트리의 루트 노드에 대한 배의 결과를받을 연속이다. 이 값이 필요하기 때문에 id은 수정하지 않고 인수 만 반환합니다.

this description of fold for binary trees이 유용 할 수도 있습니다.