рекурсии перечислять бесконечное дерево слева направо

Question

У меня есть дерево, представленное

type LazyTree<'T> = 
    | LazyBranch of 'T * ('T LazyTree list Lazy) 

Хочу присвоить номер n к каждому узлу, считая слева направо.

Более формально

Отредактировано:

Для узла a, h(a)=0 если a не имеет детей

Для узла a с родителем p, h(a)=h(p+1)

Для узла a , без родителя, L(a) - пустой набор.

Для узла a, который имеет родитель, L(a) представляет собой набор всех узлов, где для каждого узла, i пути от корня к ней не содержит a

для узла a, S(a) это все элементы из L(a), где для каждого элемента i держит h(i)<=h(a)

мне нужно заменить значение каждого узла a с размером S(a)

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

Моя функция должна возвращать дерево.

Его узел зависит от узла левого брата. Таким образом, функция должна получить 'T LazyTree Option в качестве параметра.

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

Я не спрашиваю, как его решить на конечном дереве.

---

Я не прошу об абстрактной концепции. Вот как я могу вернуть одно бесконечное дерево от другого:

type LazyTree<'T> = 
    | LazyBranch of 'T * ('T LazyTree list Lazy) 
with 
    member this.Item = match this with LazyBranch(item,_) -> item 
    member this.Children = match this with LazyBranch(_,children) -> children 
member this.Map func = 
     let children = 
      lazy 
      (
       this.Children.Force() 
       |> List.map (fun child -> child.Map func) 
      ) 
     LazyBranch(func this.Item, children) 

Answer 1

невозможно назначить такие числа, поскольку это потребует (не ленивый) обхода бесконечного дерева. Что вам нужно, ширину первого обхода, как в этом псевдокоде:

let traverse (node:LazyTree<'T>) = 
    let q = System.Collections.Generic.Queue() 
    q.Enqueue node 
    let mutable i = 0 
    while 0 < q.Count do // always TRUE 
     let node = q.Dequeue() 
     printfn "Node #%i: %A" i node.Map 
     i <- i + 1 
     for child in node.Children.Force() do 
      q.Enqueue child 

Answer 2

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

1. Хвост нужного списка можно вычислить рекурсивно, передавая чтобы быть вычисленным результатом нумерации голову списка, как в предыдущем дереве и добавления дети этого списка в «промежуточный» список, так как они предстают перед детьми второго элемента.
2. Пронумерованное дерево, соответствующее заголовку списка, просто занимает следующее число после своего предшественника как его значение. Дети этого узла также могут быть вычислены рекурсивно. Рассмотрим все пронумерованных деревьев между тем, которое соответствует голове и ее детям; это немного отличается от существующей промежуточной последовательности, в которой есть только элементы, начинающиеся после хвоста этого списка, поэтому нам нужно добавить хвост списка, вычисленный на шаге 1, перед существующим «промежуточным» списком , Тогда узел, непосредственно предшествующий первому дочернему узлу головного узла, является всего лишь последним элементом этой новой промежуточной последовательности, если есть такой узел или само пронумерованное дерево, если это не так (это может произойти, если между узлами нет узлов узел и его дочерние элементы). И узлы между детьми и их детей - это только дети этой новой промежуточной последовательности.

Извините, если это описание не прояснилось, но картинка может помочь. В любом случае, вот соответствующий код:

// These help with type inference 
let value (LazyBranch(v,_)) = v 
let children (LazyBranch(_,ts)) = ts.Value 

let numberedTree = 
    let rec number prev between = function 
    | [] -> [] 
    | t::ts -> 
     let rec rest = number first (seq { yield! between; yield! children first }) ts 
     and first = 
      let between' = seq { yield! rest; yield! between } 
      LazyBranch(value prev + 1, lazy (children t |> number (defaultArg (Seq.tryLast between') first) (between' |> Seq.collect children))) 
     first::rest 
    fun t -> 
     let rec result = LazyBranch(0, lazy number result [] (children t)) 
     result