Talk:Tree from nesting levels: Difference between revisions

← Older edit

Talk:Tree from nesting levels (view source)

Revision as of 15:24, 8 February 2021

1,386 bytes added , 3 years ago

m

→‎Labelled an example of Node as a tuple of a possible integer with a list of Nodes

Hout

9,655

edits

Revision as of 06:37, 7 February 2021 (view source) Hout (talk \| contribs) (→‎The cited source doesn't seem to cover the central issue of missing nesting levels) ← Older edit		Latest revision as of 15:24, 8 February 2021 (view source) Hout (talk \| contribs) m (→‎Labelled an example of Node as a tuple of a possible integer with a list of Nodes)
(7 intermediate revisions by the same user 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 (~~Int~~None or ~~None~~integer), and the second value is itself a (possibly empty) forest:.▼ ~~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:~~ A consistent recursive data structure – lets give it a name like '''Node'''. ~~<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>~~ 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, []) [(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> [[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) Line 126 ⟶ 122: 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 ~~example~~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]])