Функция OCaml с деревом данных

Question

Мы даем дерево, содержащее два типа элементов. Он определяется со следующей структурой данных.

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

Написать функцию раскола: («а,» б) дерево -> "список * список б, что сохраняет все элементы типа«а для первого списка и всех элементов типа»б в второй список.

У меня возникла идея сделать это рекурсивно, но я как бы застрял на этом. Я приложу свою попытку, даже если она вообще не работает:/

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) 

Эта функция превращает список в дерево. Мне нужно было это для рекурсии, поскольку второй параметр в Vertexa или Vertexb - это список. И это работает Но рекурсивная часть этого не делает.

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

Эта часть не работает, и я понятия не имею, как ее закончить. Есть ли у кого-нибудь идея, как закончить это?

Answer 1

Для решения этой проблемы вам не нужна функция drevo_list. Это фактически приведет вас в неправильном направлении.

Чтобы применить разбивку по списку деревьев, необходимо использовать List.map. Вы получите значение ('a list * 'b list) list. Теперь вам нужна вспомогательная функция concat_pairs, которая сгладит это значение до пары типа 'a list * 'b list (c.f., standard concat функция). Для реализации этой функции вы можете использовать List.fold_left. Остальное тривиально.

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

Answer 2

Есть по крайней мере две части этой функции, которые делают его трудно написать:

1. Функция, которая возвращает пару списков необходимо упаковать и распаковать его возвращаемое значение в каждом шаге рекурсии через, например, вспомогательные функции, утверждения соответствия или привязки. Один из способов было бы написать функцию, которая вставляет элемент в список внутри пары:

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

2. Функция, которая является рекурсивным над как типа дерева и встроенного типа списка требует комбинации двух шаблонов рекурсии. Это можно решить, используя либо набор взаимно-рекурсивных функций, либо используя комбинаторы более высокого порядка для списков. Вот набросок решения с использованием прежней стратегии:

   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 это изобретение ИДК в.