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].