OCaml - Зеркальное изображение дерева

Question

Моего типа дерева является

type 'a tree = Tree of 'a * 'a tree list;; 

Как я могу получить зеркальное изображение дерева, как это? Для меня это путают, имея список детей, потому что я не знаю, как получить индивидуально для каждого ребенка и сделать рекурсию без потери родительского трека, любой идеи?

Редакция: Я старалась, и я думаю, что я получил решение:

let spec arbol = 
     match arbol with 
     Tree(a,[])-> Tree(a,[]) 
     | Tree(a,l)-> Tree(a, List.rev (
        let rec aux = function 
         Tree(a,[])::[]->Tree(a,[])::[] 
         | Tree(a,[])::l-> [Tree(a,[])]@(aux l) 
         | Tree(a,t)::[]-> [Tree(a, (List.rev (aux t)))] 
         | Tree(a,t)::l-> [Tree(a, (List.rev (aux t)))]@(aux l) 
        in aux l));; 

Я попробовал его с этим деревом:

let p = Tree(1, [ 
    Tree(2,[]); 
    Tree(3, [ 
     Tree(6,[]); 
     Tree(7,[]) 
     ]); 
    Tree(4,[]); 
    Tree(5,[]) 
]);; 

И я получил в результате # spec p;;

-: int tree = Tree (1, [ 
       Tree (5,[]); 
       Tree (4,[]); 
       Tree (3,[ 
        Tree(7,[]); 
        Tree(6,[])]); 
       Tree (2,[]) 
       ]) 

Таким образом, я думаю, что моя функция работает должным образом. Дайте мне знать, если это не так.

Answer 1

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

К сожалению, ваш код вводит так много случаев, что его трудно проверить на глаз.

Мне кажется, что ваша функция aux предназначена для расчета зеркального отображения списка деревьев. Однако он не работает в пустом списке. Если вы переписываете aux для работы с пустым списком, вы можете обнаружить, что вам не потребуется так много разных случаев. В частности, вы можете удалить свой внешний матч и половину случаев в своем внутреннем матче.

Фактически, ваша функция aux (если правильна) выполняет всю работу. Если вы посмотрите на это правильно, вы можете просто использовать aux для всего.

Поскольку вы используете List.rev, предположим, вы также можете использовать List.map. На это тоже можно взглянуть.

Update

Деревья неотъемлемо рекурсивные структуры, поэтому при поиске алгоритма дерева, это часто помогает представить, как вы будете использовать свой алгоритм рекурсивно. В этом случае вы могли бы спросить себя, как бы вы собрали зеркальные изображения всех поддеревьев дерева, чтобы сделать зеркальное изображение всего дерева.