Подсчет узлов в дереве

Question

борьба с f # - борьба в царстве деревьев - в частности, подсчет количества узлов. Это представляет реальный интерес, так как программа, которую я хотел бы в конечном итоге закодировать в F #, касается многоуровневых деревьев, к сожалению, она дошла до неприятного начала - надеюсь, вы, возможно, сможете помочь!

Задача 61 из серии 99 f #, просит подсчитать листья двоичного дерева. Решение (ниже) подсчитывает узлы, но моя проблема не понимая

• как двойная рекурсия работает петлю влево (прикольная LACC -> петля правый ..)

• , что cont (branchF x lacc racc), мои Создавалось впечатление, что продолжение было функцией «а», но это занимает всего два параметра ...

• loop t id идентификатора единицы типа - я не вижу, как это подразумевается

в основном не понимает этого, или порядок, в котором он протекает через дерево (отладка & шаг за шагом не доказывает, что это полезно). Если есть более простые примеры, рекомендации для предварительного чтения и т. Д., Тогда, пожалуйста, направляйте меня к ним.

Большое спасибо за любую помощь, код решение о котором идет речь ниже:

Приветствия

тд

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 

, где «а является типом узлов в дереве,» б является типом аккумулятора, и «с является результатом функции продолжения.

В случае листового узла продолжение передается пустым значением аккумулятора, переданным функции 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 полезно.