Ocaml, функция уровней для бинарного дерева

Question

Я хочу реализовать функцию уровней для двоичного дерева, которая преобразует двоичное дерево в список списка int, и каждый из списка int должен содержать все значения на текущем уровне: Например:

              9
         6          10
     5     7              11
 42   
 42
 42

[[9]; [6; 10]; [5; 7; 11]; [42]; [42]; [42]]

Мне нужно использовать этот тип и fold_bin_tree

type 'a bin_tree =
   Node of 'a bin_tree * 'a * 'a bin_tree | Null;;


let rec fold_bin_tree f a t =
  match t with
  Null ->a |
  Node (l,x,r) ->f x (fold_bin_tree f a l) (fold_bin_tree f a r);;

Я реализовал функцию слияния как помощник, и это мой код:

let merge l1 l2 = (*[[a b c] [d e]] merge [[1] [2 3] [4]] = 
[[a b c 1] [d e 2 3] [4]]*)
let rec scan l1 l2 acc =
  match l1,l2 with
  | [],[] -> acc
  | h1::t1,[] -> scan t1 l2 (h1::acc)
  | [], h2::t2 -> scan l1 t2 (h2::acc)
  | h1::t1,h2::t2 -> scan t1 t2 ((h1@h2)::acc)
  in scan l1 l2 [];;

let levels t =
  fold_bin_tree
  (fun x levels_l levels_r -> let lev = merge levels_l levels_r in
    [x]::lev
  ) [] t;;

Я проверил слияние, и оно, кажется, работает хорошо, но мои уровни не работают правильно, потому что

levels example

возвращает [[9]; [5; 7]; [42]; [42]; [42; 11]; [6; 10]]

где пример - это дерево, которое я показал в начале моего поста

  let example = Node(  Node(Node(Node(Node(Node(Null,42,Null),42,Null),42,Null),5,Null), 6 ,Node( Null, 7 ,Null )) ,9, (Node(Null, 10 ,Node(Null,11,Null))));;

Answer 1

Подсказка: почему ваша функция merge возвращает

 merge [[1];[2]] [];;

[[2]; [1]]