Преобразовать дерево в список
каждый! У меня есть тип списка:
type ConsList<'value> =
| Cons of head: 'value * tail: ConsList<'value>
| Empty
И тип дерева:
type Tree<'value> =
| Node of value: 'value * children: ConsList<Tree<'value>>
| Leaf of value: 'value
Мне нужна функция, которая могла бы собирать все значения в узлах и листьях дерева и преобразовывать их в ConsList в порядке, начиная с корня и следуя слева направо.
Например, если у меня есть: Node(1, Cons(Leaf 2, Cons(Leaf 3, Empty)))
Тогда я ожидаю, что результат будет: Cons(1, Cons(2, Cons(3, Empty)))
У меня есть fold-функции, если они могут быть полезны:
let rec fold folder acc lst =
let f = fold folder
match lst with
| Empty -> acc
| Cons (hd, tl) -> f (folder acc hd) tl
let rec fold folder acc tree =
let f = fold folder
match tree with
| Leaf value -> folder acc value
| Node(value, children) -> ConsList.fold f (folder acc value) children
Ответы 2
Используйте дерево fold, чтобы создать список значений. Что-то вроде этого:
Tree.fold (fun currentStateOfList value ->
// add value to currentStateOfList here
) initialStateOfList aTree
Вам нужно выяснить:
- Каково начальное состояние списка?
- Что нужно сделать, чтобы добавить значение в текущее состояние списка?
В зависимости от требований вам, возможно, придется изменить порядок списка в конце.
Вроде бы первое — это Empty, а второе — конкатенация, но как это реализовать мне в голову не приходит. Я тоже хотел бы обойтись без реверса.
Подумайте о том, что делает Cons. Можете ли вы использовать это для реализации конкатенации?
Думаю, я на финишной прямой, осталось научиться как-то добавлять пункт в конец списка. Это вообще возможно?
Не с неизменяемыми списками, такими как тот, с которым вы работаете. Однако несложно определить функцию с именем rev, которая переворачивает список. Вы можете попробовать. (Я рад, что вы нашли решение. Хорошая работа!)
Если бы у меня было n-арное дерево, оно могло бы «выглядеть» примерно так.
----1--------------------
/ \ \
---2--- ---3---- --4--
/ / \ / / \ \ / \
5 6 7 8 9 10 11 12 --13--
/ \
14 15
Мой F# не очень хорош, но я неплохо разбираюсь в OCaml, поэтому этот тип может выглядеть примерно так, как показано ниже, если я не определю свой собственный тип списка.
type 'a tree = Node of 'a | Tree of 'a * 'a tree list
Создание вышеуказанной структуры тогда:
Tree (1,
[Tree (2, [Node 5; Node 6; Node 7]);
Tree (3, [Node 8; Node 9; Node 10; Node 11]);
Tree (4, [Node 12; Tree (13, [Node 14; Node 15])])])
Чтобы преобразовать это в список в глубину и сохранить хвостовую рекурсию, можно использовать алгоритм на основе стека. По мере выполнения итерации мы сохраняем стек значений tree для оценки по очереди.
В приведенном выше примере мы бы добавили 1 в список результатов, а затем рекурсивно вызвали бы функцию tree_to_list для:
---2---
/ / \
5 6 7
Помещая оставшуюся часть детей в стек.
---3---- --4--
/ / \ \ / \
8 9 10 11 12 --13--
/ \
14 15
Столкнувшись с Node, мы записываем значение в список результатов и сохраняем оставшиеся деревья (оба узла) в стеке.
6 7 ---3---- --4--
/ / \ \ / \
8 9 10 11 12 --13--
/ \
14 15
Теперь мы начинаем потреблять стек. Сначала идут узлы 6 и 7, затем мы начинаем с 3Tree.
9 10 11 --4--
/ \
12 --13--
/ \
14 15
И затем, в конце концов, потребляем 4Tree, пока не наткнемся на Node или Tree без дочерних элементов (на самом деле одно и то же), и стек не станет пустым. Затем, поскольку мы строили список в обратном порядке для повышения эффективности, нам нужно перевернуть его.
Простая реализация может выглядеть так:
let tree_to_list t =
let rec tree_to_list' t a s =
match t, s with
| (Node v | Tree (v, [])), [] -> List.rev (v :: a)
| Node v, x::xs -> tree_to_list' x (v :: a) xs
| Tree (v, x::xs), _ -> tree_to_list' x (v :: a) (xs @ s)
| Tree (v, []), s::ss -> tree_to_list' s (v :: a) ss
in
tree_to_list' t [] []
Учитывая тесную связь между языками, надеюсь, вы найдете этот алгоритм легко применимым.
это домашнее задание? Я не хочу помогать тебе обманывать. Так что могу я просто дать подсказку. Представьте, что у вас есть цикл, который проходит через все узлы, и на каждой итерации вы добавляете элемент в список. Цикл называется «свернуть», все, что вам нужно сделать, это написать код внутри цикла, чтобы добавить элемент в список