F # Как выровнять дерево двоичного поиска

Question

У меня есть дерево, структурированное как:

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

Я использую хвостовую рекурсию в стиле продолжения над моим деревом и пытаюсь сгладить его.

let rec loop tree k acc = 
  match tree with
  | Leaf v -> v :: acc
  | Branch (tl,tr) -> loop tl (loop tr k) acc
loop xs id []


(Branch (Branch (Leaf 1.0,Leaf 2.0),Branch (Leaf 3.0,Leaf 4.0)))

Возвращает только [1.0]

Однако я получаю только первый лист дерева, моя функция не работает на всем дереве. Как мне этого добиться?

Answer 1

Вы передаете продолжение, но нигде не звоните. Попробуйте это:

let rec loop tree k acc = 
  match tree with
  | Leaf v -> k (v :: acc)
  | Branch (tl,tr) -> loop tl (loop tr k) acc

Тогда loop xs id [] производит [4.0; 3.0; 2.0; 1.0].