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)

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 – in Python terms (None or integer), and the second value is itself a (possibly empty) forest.

A consistent recursive data structure – lets give it a name like Node.

In Python terms, Node here is a tuple of a possible integer with a list of Nodes: 

Node (None|Int) :: ((None|Int), [Node])

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

Sorry, but what's wrong with a tree with multiple nodes at level 1? I mean, even a binary tree has got 2! [oh, one node, two children.. hmm]
Not quite sure what wrong means to you exactly here. Siblings inescapably have a parent :-) Hout (talk) 17:32, 7 February 2021 (UTC)
What is the purpose or benefit of littering up the nested structures (a better name?) with all those None?
That's just a representation of the implicit structure. Each of these examples implies the existence of one or more parent nodes which have no explicit (integer) node value.
  • Two or more level 1 siblings implicitly share a level 0 parent:
  • Where we are given a 1 and a 3 but no 2, the 3 inescapably has a level 2 parent which (a) lacks the integer 2 as a node value and (b) is a child of a level 1 node. Hout (talk) 17:32, 7 February 2021 (UTC)
What about programming languages where not everything has to be a tuple (whatever that its)?
No problem at all :-) (Paddy3118 will explain to you what a tuple is). Hout (talk) 17:32, 7 February 2021 (UTC)
It seems to me you're trying to forcefully impose functional programming rules or something onto this task. --Pete Lomax (talk) 17:24, 4 February 2021 (UTC)
Does it ? Just exploring what the input notation really represents.
That's necessary, because the output shown is rejected as inconsistent by compilers of strictly-typed languages, so we need something else in those cases, and that means we need to know what we are really representing. Hout (talk) 17:32, 7 February 2021 (UTC)
Aye, "You have no control of level 0, and integer zero being the unnumbered root level". (For an alternate view, that now I've wrote it, I don't like). The task description is enough to write examples, for I think. --Paddy3118 (talk) 18:23, 4 February 2021 (UTC)
Not necessarily suggesting a change, just thinking it through, and preparing you to understand if some contributions add an extra layer of brackets.
Forgive me for the notational excursus, which PeteLomax clearly didn't find illuminating :-)
I was just illustrating a couple of probably quite inconsequential points:
  1. that you are speaking of single trees, but mostly showing unparented lists of trees, and
  2. the first example and the rest are not necessarily of the same type.
The conclusion is just that if anyone decides to try a rigorous data-typing, then they may produce output that diverges a bit from yours (extra pair of flanking brackets, or additional virtual root) I'm sure you will be able to cope with that :-) Hout (talk) 19:27, 4 February 2021 (UTC)
If one takes a position that doesn't allow one to fulfill the task, then the smart thing to do if you have been shown how to, and no doubt know what I required, is to adjust ones position or be doomed to never fulfil the requirements. I would suggest you add a small note at the beginning of your solution then supply an idiomatic solution fitting the description. --Paddy3118 (talk) 19:57, 4 February 2021 (UTC)
"takes a position that ..." Not me – Math :-) In more strictly typed languages, the bracket nesting you show trips a compiler error, because the type is inconsistent.
But as you say – where the inconsistency of the type becomes a problem, a note in the preamble and a variant representation will be enough Hout (talk) 20:21, 4 February 2021 (UTC)
Considering the first level as a forest with the current wording seems fine. You do have a good point about the [] case being inconsistent though. Following the pattern 
[3] => [[[3]]],  [2] => [[2]], [1] => [1], [] => ???
then it seems like [] should map to 'nothing' instead of []. Also for the sum type in the python above, why is it between Int and None? Isn't the choice between Int and Tree? Garbanzo (talk) 03:40, 7 February 2021 (UTC)
Yes, the value represented by `[]` is ambiguous in the output notation shown in the task – we don't have a way of knowing whether it's a single value node, or an empty list of potentially multiple children.
(This is clearly not a binary tree incidentally – we have multiple nodes with common ancestry at the same level).
The sum type representing value nodes has a None/Nothing option for the cases where no level integer has been supplied, but we do know that there must be an intermediate node. If there is a level 1 and a level 3, then there must be a level in between, descending from 1 and a parent to 3.
An alternative – where there the input contains a 1 and a 3 but no 2, for example,
would be to supply a 2, making the implicit parent nodes explicit.
The simplification of the node value type might be appealing, but the cost is
that the (input sequence -> output tree) rewrite would then cease to be reversible –
once we have added integers that were not explicitly supplied, we have discarded
information, for any return trip, about which levels were implicit, and should
be discarded for the integer list representation, and which were explicit,
and should be kept. Hout (talk) 06:27, 7 February 2021 (UTC)

Source

I formed the task from working on this problem someone else had on Stack Overflow. I hope it helps those who asked for more info. --Paddy3118 (talk) 06:02, 7 February 2021 (UTC)

But the key issue introduced by your examples here, which was not, I think, a component of that Stack Overflow discussion, was that of implicit intermediate levels, for which no integer is supplied in the input list.
I believe the Stack Overflow examples are all fully saturated, with no missing nesting levels ? Hout (talk) 06:36, 7 February 2021 (UTC)
If [1, 2, 4] represents object nesting levels, as the task description tell us, then there is an implicit level 3. Hout (talk) 06:40, 7 February 2021 (UTC)
Perhaps the task could best be tightened up and filled out by also requiring, (as was already suggested elsewhere on this page, I think) a round-trip transformation, to ensure that no information is lost in the translation from list to tree (and back). Hout (talk)
Retrieved from "https://rosettacode.org/wiki/Talk:Tree_from_nesting_levels?oldid=307485"