Talk:Tree from nesting levels

From Rosetta Code

History or provenance of this data-structure ?

Are we sure that this is the most useful representation of 'missing' levels ?

The integers here are carrying a dual load – both as the value of a tree node, and as indicators of nesting depth.

The structure appears to slightly crack under its own weight, losing a bit of recursive coherence and easy traversability, at the point where a nesting level is skipped, and we get nodes with missing values.

Before we jump in with examples in different languages, are you sure that this data-structure has stabilised ? Does it have a history or provenance that you can reference ? Hout (talk)

I expect it to be an exercise. More the maths side than engineering, although someone *did* have the need.
I think it is ripe for first examples; as of writing, the Julia and Phix examples were completed OK, so I think they were able to follow my task description. Are you having problems following the task?
--Paddy3118 (talk) 10:10, 2 February 2021 (UTC)
There's a fault line between the very solid "format that can be used for further calculations"
and the slightly fragile (self-contradictory) should produce:, should generate: lines which
then show a notation that would have no defined meaning in more strictly typed languages.
(but the stakes are not high :-) Hout (talk) 12:43, 2 February 2021 (UTC)

The generated tree datastructure (sic) should ideally be in a languages nested list format that can be used for further calculations rather than something just calculated for printing

Perhaps it would be clearer if the task required further processing. I would suggest at least add an item, delete an item, union of two trees, and subset of a tree according to a predicate.--Nigel Galloway (talk) 15:24, 2 February 2021 (UTC)

Hmm, it might make that text redundant, but might also cloud the focus, whilst needing other text for its description. --Paddy3118 (talk) 15:50, 2 February 2021 (UTC)
It is going to have to change anyway, languages needs an apostrophe. The point is that all will be better understood when the operations for which this data structure are useful is explained.--Nigel Galloway (talk) 16:15, 2 February 2021 (UTC)
Probably a little too abstract, but I thought of flatten() getting the input back, and also whipped up a quick "collect item*level" traversal:
function square(sequence s, integer level=1)
    integer res = 0
    for i=1 to length(s) do
        res += iff(atom(s[i])?s[i]*level:square(s[i],level+1))
    end for
    return res
end function

?{ti,flatten(res,{}),square(res),sum(sq_mul(ti,ti))}
-- results:
{{},{},0,0}
{{1,2,4},{1,2,4},21,21}
{{3,1,3,1},{3,1,3,1},20,20}
{{1,2,3,1},{1,2,3,1},15,15}
{{3,2,1,3},{3,2,1,3},23,23}
{{3,3,3,1,1,3,3,3},{3,3,3,1,1,3,3,3},56,56}
(The tree traversal in no way has to be recursive, of course) --Pete Lomax (talk) 22:49, 2 February 2021 (UTC)

The target outputs shown clash with the task description

There's a clash here between the description's talk of 'a Tree' (suggesting a single root), and the examples of target output, which show forests (lists of trees), with multiple nodes at level 1.

The existence of multiple level 1 siblings tells us that each of these trees has a virtual root (parent of the level one siblings) which might be called level 0. (See the Nothing root in the Haskell tree diagrams)

In which case, the outputs shown are not, in fact, self-consistent ...

Your first output example `[]` could indeed be a tree (the virtual root, with no descendants), but it could also be an empty list of trees.

Those that follow, however, clearly show lists of trees ('forests' if you like).

If you really want each output example to have the same consistent type, and you want that to be "tree", in each case, rather than "tree" in one case, and "list of trees" in the others, then from the second example onwards, you really need an additional pair of flanking brackets.

i.e. 

list of trees -> single tree
[1, [2, [[4]]]] -> [[1, [2, [[4]]]]]

Hout (talk) 12:23, 4 February 2021 (UTC)

To put this in a Python notation, if we start with one of these forests (lists of trees), mapping over each of its members with a foldTree catamorphism, passing a function like this to it:

<lang python># levelList :: Tree (Int|None) def levelList(x): 

   A Tree in which is node is a tuple of two values:
      A possible integer, and a list of trees.
      (Int or None, [Tree])
   
   def go(xs):
       if x.get('Nothing', False):
           return (None, concat(xs))
       else:
           return [(x.get('Just', 0), concat(xs))]
   return go</lang>

We can obtain a self-consistent representation of these forests as lists of tuples, in which the first value is a kind of sum type (Int or None), and the second value is itself a (possibly empty) forest:

<lang python>[] [[(1, [(2, [(None, [(4, [])])])])]] [[(None, [(None, [(3, [])])])], [(1, [(None, [(3, [])])])], [(1, [])]] [[(1, [(2, [(3, [])])])], [(1, [])]] [[(None, [(None, [(3, [])]), (2, [])])], [(1, [(None, [(3, [])])])]] [[(None, [(None, [(3, []), (3, []), (3, [])])])], [(1, [])], [(1, [(None, [(3, []), (3, []), (3, [])])])]]</lang> Hout (talk) 14:00, 4 February 2021 (UTC)

Retrieved from "https://rosettacode.org/wiki/Talk:Tree_from_nesting_levels?oldid=307461"