OCaml function with data type tree

Question

We give a tree containing two types of elements. It is defined with the following data structure.

type ( 'a , 'b ) tree =
   Empty
   | Vertexa of 'a * ( 'a , 'b ) tree list
   | Vertexb of 'b * ( 'a , 'b ) tree list

Write a split function: ('a,' b) tree → 'list *' b list, which saves all elements of type 'a to the first list and all elements of type' b to the second list.

I had an idea to do this recursively, but I was kind of stuck with it. I will make my attempt, even if it does not work at all: /

let rec one drevo_list=
    match drevo_list with
   | [Empty]->Empty 
   | Empty::tl -> one tl
   | Vertexa(a,b)::tl -> Vertexa(a,b@tl) 
   | Vertexb(a,b)::tl -> Vertexb(a,b@tl) 

This function turns a list into a tree. I needed this for recursion, since the second parameter in Vertexa or Vertexb is a list. And it works. But the recursive part does not.

let rec split drevo=
   match drevo with
   | Empty -> [],[]
   | Vertexa(a,b)-> split (one b)
   | Vertexb(a,b)-> split (one b)

This part does not work, and I have no idea how to finish it. Does anyone have any ideas how to end this?

Answer 1

drevo_list . .

List.map, . ('a list * 'b list) list. concat_pairs, 'a list * 'b list (c.f., standard concat function). List.fold_left. .

, , . , , .

Answer 2

:

• , , , . , . , :

  let insertA a (xs, ys) = (a::xs, ys)
  let insertB b (xs, ys) = (xs, b::ys)
  

• , , , . , - , . :

  let rec split s =
      match s with
    | Empty -> ([], [])
    | Vertexa (a, ts) -> (* if we had just one t: insertA a (split t) *)
    | Vertexb (a, ts) -> (* if we had just one t: insertB b (split t) *)
  

  , splitMany : ('a, 'b) tree list -> ('a list, 'b list), split .

  and rec splitMany ts =
      match ts with
    | [] -> ([], [])
    | (t:ts') -> (* merge (split t) with (splitMany ts') *)
  

  , , , :

  let rec split s =
      match s with
    | Empty -> [],[]
    | Vertexa (a, ts) -> insertA (concat_pairs (map split ts))
    | Vertexb (a, ts) -> insertB (concat_pairs (map split ts))
  

  concat_pairs .