Преобразование розовых деревьев в различные типы бинарных деревьев

Question

Я полностью заблудился о том, как сделать некоторые преобразования деревьев в Haskell. Мне нужно идти от розового дерева, определенного как:

data Rose a = Node a [Rose a] deriving (Eq, Show, Ord)

в двоичное дерево, которое определяется как:

data Btree a = Empty | Fork a (Btree a) (Btree a) deriving (Eq, Show, Ord)

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

Btree a = Leaf a | Fork (Btree a) (Btree a)

с функцией от розового дерева до бинарного дерева, определенной как:

toB :: Rose a -> Btree a
toB (Node x xts) = foldl Fork (Leaf x) (map toB xts)
toB (Node x []) = foldl Fork (Leaf x) []

У меня есть ответ, но я не знаю, как преобразовать его, чтобы он работал с новым определением Btree.

Answer 1

Попробуйте написать функцию, конвертирующую из первого во второе определение двоичного дерева. Тогда убедись. Тоб это ваша новая функция! Теперь систематически создайте новую функцию, которая действует как слияние двух, встраивая одну в другую, и вы получите простое и элегантное решение.

Answer 2

Когда я делал что-то подобное, я считал «левое» поддерево первым дочерним элементом, а «правое» поддерево - родным узлом узла. Это означает, что вы конвертируете дерево так:

     h                 h
    /|\               /
   / | \             /
  b  d  e     ==>   b->d->e
 / \   / \         /     /
a   c f   g       a->c  f->g

h по-прежнему является корнем, но на второй диаграмме / - это левое поддерево, а -> - это правое. Листья не имеют левого поддерева, но могут иметь братьев и сестер (правые поддеревья). Корень не имеет правого поддерева, но может иметь детей (левое поддерево). Внутренние узлы имеют оба.

Это помогает?