Talk:Tree datastructures

From Rosetta Code
Latest comment: 4 years ago by Paddy3118 in topic Task tree in dot format, and diagram


My thanks to Ralf Ebert who asked this question on Stack Overflow which introduced me to the indent form. I answered his question then thought of RC. --Paddy3118 (talk) 08:28, 17 October 2019 (UTC)Reply[reply]

Good idea for a task – a couple of thoughts.

This seems a promising kind of task – perhaps worth linking to the Functional Coverage Tree task, so that the latter can use outline parsing routines shaped up here.

A couple of thoughts:

  1. Perhaps JSON serialisations, both for the nested and numbered data types ?
  2. Unicode characters beyond the narrowly Anglo-Saxon alphabet ? Hout (talk) 23:09, 15 October 2019 (UTC)Reply[reply]

The simplest nested JSON output (each node a value+list pair) would be:

Hout (talk) 23:43, 15 October 2019 (UTC)Reply[reply]

Incidentally, do you feel strongly committed to that particular outline ? For some reason the word 'mock' jars a little (perhaps particularly now that we are beginning to understand more about the destructive potential of digital networks). Hout (talk) 23:43, 15 October 2019 (UTC)Reply[reply]

Similarly, the simplest JSON output list for integer+value tuples would be:

Hout (talk) 23:46, 15 October 2019 (UTC)Reply[reply]
Good Q's. I have a cold (streaming eyes), and will get back to you tomorrow? Thanks. --Paddy3118 (talk) 13:33, 16 October 2019 (UTC)Reply[reply]
Ginger and turmeric are the thing, with hot water in large quantities. Hout (talk) 13:40, 16 October 2019 (UTC)Reply[reply]
Appreciated, thanks. --Paddy3118 (talk) 08:24, 17 October 2019 (UTC)Reply[reply]
On those questions.
JSON: I didn't want to restrict the task that way, as some could make an equal claim for XML or lisp lists - I thought I'd stay more neutral on that point.
The outline: There should be one, and only one, blah-de-blah :-) Well actually I loved my rocks/mocks pun too much and just slapped in "golfing" as a bad afterthought. I think it is very useful to have the one tree for all language examples, but I stopped mocking golfing years and years ago - its not for RC, but not for mocking IMHO. I have tried for a late save with a note, but is it too late to ask for all examples to update to use just "trolling"?
Your task statement sensibly specifies code that is outline-independent, so any change would, if the code is working, be a quick copy-paste.
(I can speak for 4 of the 7 current entries, all of which I would very happy to change :-)
To be honest, I feel a little embarrassed by any 'mocking' / 'trolling' references – people are dying from it at the moment – I think I would feel less uneasy with something a bit more plausible and motivating – maybe something that gave a sense of the contexts in which one might actually want to work with a tree structure, or something related to the content ? Hout (talk) 08:41, 17 October 2019 (UTC)Reply[reply]
Let's go for it then. I'll Update the task text to only specify "trolling", and my Python; you update your examples to use "trolling".
Could you also put an incomplete box on the other examples informing them of the update?
Thanks --Paddy3118 (talk) 08:19, 18 October 2019 (UTC)Reply[reply]
I'm a little puzzled ... now you want references to 'mocking' *and* to 'trolling' ? Not really an example that I can feel relaxed about. For the moment I will just withdraw my examples. I really don't want to propagate jokes about mocking and trolling Hout (talk) 08:37, 18 October 2019 (UTC)Reply[reply]

And when comparison has children?

--Nigel Galloway (talk) 13:03, 16 October 2019 (UTC)Reply[reply]

Depends, of course, on the implementation of equality in each language. For JS I have had to hand-write a recursive eq. Haskell's Data.Tree module includes a Tree instance for the Eq class. Python's (==) equality is recursive out of the box. Hout (talk) 13:27, 16 October 2019 (UTC)Reply[reply]

Hi, I added a note to the task to try and downplay the significance of this part of the task after this query as I would like the datastructures and the conversion between them to be central. --Paddy3118 (talk) 08:40, 18 October 2019 (UTC)Reply[reply]

Deriving a tree from a list of lines with their indent levels

For what its worth, a declarative description which is also a recursive algorithm might look something like:

If a forest is understood as a list of trees,
then the forest structure of an indented outline is either
    an empty list,
        (if the outline contains no lines)
    or a list with a tree at its head, and a tail which is a forest.
        The head tree:
            - has the first line of the outline as its value
            - and has a (possibly empty) child list 
                    which is the forest structure of all the lines (if any) which:
                        - follow the first line,
                        - and precede its next peer
                            (the next line that shares the first's indent level)
        The tail forest has the structure of the remaining outline, 
            - from the next line which shares the indent level of the first line, 
            - to the last line of the outline.

Generic tree to indent-type datastructure conversion

The following is the diagram from the Tree traversal task annotated with depth information for the nodes:

         1              :0
        / \
       /   \
      /     \
     2       3          :1
    / \     /
   4   5   6            :2
  /       / \
 7       8   9          :3

A preorder traversal of the tree outputting (node_depth, node_name) pairs will generate the indent form of this and other rooted trees. --Paddy3118 (talk) 21:43, 19 October 2019 (UTC)Reply[reply]

Task tree in dot format, and diagram

<lang dot>digraph rc {

   node [fontsize=12 height=0.1 nodesep=0.25 width=0.1]
   RosettaCode -> rocks
   rocks -> code
   rocks -> comparison
   rocks -> wiki
   RosettaCode -> mocks
   mocks -> trolling
   RosettaCode [color=brown fontcolor=green fontname=bold]


--Paddy3118 (talk) 10:06, 20 October 2019 (UTC)Reply[reply]