Talk:Tree from nesting levels: Difference between revisions
m
→Labelled an example of Node as a tuple of a possible integer with a list of Nodes
| (20 intermediate revisions by 3 users not shown) | |||
Line 70:
[[User:Hout|Hout]] ([[User talk: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 (
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''':
▲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:
<pre>Node (None|Int) :: ((None|Int), [Node])</pre>
<lang python>(None, [])
[[User:Hout|Hout]] ([[User talk: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]<br>
:: Not quite sure what ''wrong'' means to you exactly here. Siblings inescapably have a parent :-) [[User:Hout|Hout]] ([[User talk: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?<br>
:: 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. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 17:32, 7 February 2021 (UTC)
: What about programming languages where not everything ''has'' to be a tuple (whatever ''that'' its)?<br>
:: No problem at all :-) (Paddy3118 will explain to you what a tuple is). [[User:Hout|Hout]] ([[User talk: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. --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|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. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 17:32, 7 February 2021 (UTC)
::Aye, <strike>"You have no control of level 0, and integer zero being the unnumbered root level"</strike>. (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. --[[User:Paddy3118|Paddy3118]] ([[User talk: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:
:::# that you are speaking of single trees, but mostly showing unparented '''lists''' of trees, and
:::# 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 :-) [[User:Hout|Hout]] ([[User talk: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. --[[User:Paddy3118|Paddy3118]] ([[User talk: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 [[User:Hout|Hout]] ([[User talk: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 <pre>[3] => [[[3]]], [2] => [[2]], [1] => [1], [] => ???</pre> 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? [[User:Garbanzo|Garbanzo]] ([[User talk: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. [[User:Hout|Hout]] ([[User talk:Hout|talk]]) 06:27, 7 February 2021 (UTC)
==Source==
I formed the task from working on [https://stackoverflow.com/questions/65992295/how-to-organize-elements-in-array-by-their-level/65993607#65993607 this problem] someone else had on Stack Overflow. I hope it helps those who asked for more info. --[[User:Paddy3118|Paddy3118]] ([[User talk: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 ? [[User:Hout|Hout]] ([[User talk: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. [[User:Hout|Hout]] ([[User talk: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). [[User:Hout|Hout]] ([[User talk:Hout|talk]])
| |||