Функция foldBack для дерева в F#
У меня есть тип дерева:
type Tree<'value> =
| Node of value: 'value * children: ConsList<Tree<'value>>
| Leaf of value: 'value
И функция сгиба для него:
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
ConsList на случай, если вам это нужно:
type ConsList<'value> =
| Cons of head: 'value * tail: ConsList<'value>
| Empty
let rec fold folder acc lst =
let f = fold folder
match lst with
| Empty -> acc
| Cons (hd, tl) -> f (folder acc hd) tl
Мне нужна функция foldBack, то есть функция проходит по узлам слева направо сверху вниз, начиная с корня.
Я остановился на этом:
let rec foldBack folder acc tree =
let f = fold folder
match tree with
| Leaf value -> f acc value
| Node(value, children) -> f value (f acc *children*)
Ожидается, что дочерние элементы с типом ** будут Tree<'a>, но имеют тип ConsList<Tree<Tree<'a>>>
Ответы 1
Для обратных сгибов обычно используется аккумулятор как функция, которая получает промежуточное свернутое значение подветви и возвращает новое свернутое значение по отношению к текущему элементу. Таким образом, проходя по дереву обычно сверху вниз, вы буквально строите вычисление, которое при получении конечных элементов будет вычислять складку снизу вверх. Продолжение темы по прохождению стиля вы можете поискать сами. Этот подход также используется для оптимизации рекурсии хвостового вызова, потому что функция, которую вы накапливаете, представляет собой цепочку объектов функций, которая не влияет на стек.
Вот что я сделал до сих пор (я заменил ConsList на обычный тип List, потому что в противном случае для него также потребовалось бы создать foldBack, что вы можете попробовать сами)
type ConsList<'t> = 't list
type Tree<'value> =
| Node of value: 'value * children: ConsList<Tree<'value>>
| Leaf of value: 'value
let foldBack seed folder (tree: 't Tree) =
let rec fold acc tree =
match tree with
| Leaf value ->
let acc' inner = folder (acc inner) value
acc'
| Node (value, children) ->
let acc' inner = List.foldBack (fold acc) children inner
let acc'' inner = folder (acc' inner) value
acc''
fold id tree seed
let treeSample =
Node ("node1", [
Leaf "subnode1";
Node ("node1.1", [
Leaf "subnode1.1";
Node("node1.2", [
Leaf "leaf1.2"
])
])
])
treeSample|>foldBack ">>seed<<" (fun value acc -> $"{value} -> {acc}" )
val it: string = ">>seed<< -> leaf1.2 -> node1.2 -> subnode1.1 -> node1.1 -> subnode1 -> node1"