Tree from nesting levels

From Rosetta Code
Revision as of 09:27, 3 February 2021 by Nig (talk | contribs) (→‎{{header|AppleScript}}: Very minor optimisation reducing the number of empty lists created during execution.)
Tree from nesting levels is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given a flat list of integers greater than zero, representing object nesting levels, e.g. [1, 2, 4], generate a tree formed from nested lists of those nesting level integers where:

  • Every int appears, in order, at its depth of nesting.
  • If the next level int is greater than the previous then it appears in a sub-list of the list containing the previous item


The generated tree data structure should ideally be in a languages nested list format that can be used for further calculations rather than something just calculated for printing.


An input of [1, 2, 4] should produce the equivalent of: [1, [2, [[4]]]] where 1 is at depth1, 2 is two deep and 4 is nested 4 deep.

[1, 2, 4, 2, 2, 1] should produce [1, [2, [[4]], 2, 2], 1].
All the nesting integers are in the same order but at the correct nesting levels.

Similarly [3, 1, 3, 1] should generate [[[3]], 1, [[3]], 1]

Task

Generate and show here the results for the following inputs:

  • []
  • [1, 2, 4]
  • [3, 1, 3, 1]
  • [1, 2, 3, 1]
  • [3, 2, 1, 3]
  • [3, 3, 3, 1, 1, 3, 3, 3]


AppleScript

<lang applescript>on treeFromNestingLevels(input) 

   set maxLevel to 0
   repeat with thisLevel in input
       if (thisLevel > maxLevel) then set maxLevel to thisLevel
   end repeat
   if (maxLevel < 2) then return input
   
   set emptyList to {}
   repeat with testLevel from maxLevel to 2 by -1
       set output to {}
       set subnest to {}
       repeat with thisLevel in input
           set thisLevel to thisLevel's contents
           if ((thisLevel's class is integer) and (thisLevel < testLevel)) then
               if (subnest ≠ emptyList) then set subnest to {}
               set end of output to thisLevel
           else
               if (subnest = emptyList) then set end of output to subnest
               set end of subnest to thisLevel
           end if
       end repeat
       set input to output
   end repeat
   
   return output

end treeFromNestingLevels

-- Task code: local output, astid, input, part1, errMsg set output to {} set astid to AppleScript's text item delimiters repeat with input in {{}, {1, 2, 4}, {3, 1, 3, 1}, {1, 2, 3, 1}, {3, 2, 1, 3}, {3, 3, 3, 1, 1, 3, 3, 3}} 

   set input to input's contents
   set AppleScript's text item delimiters to ", "
   set part1 to "{" & input & "} nests to:  {"
   -- It's a pain having to parse nested lists to text, so throw a deliberate error and parse the error message instead.
   try
       || of treeFromNestingLevels(input)
   on error errMsg
       set AppleScript's text item delimiters to {"{", "}"}
       set end of output to part1 & ((text from text item 2 to text item -2 of errMsg) & "}")
   end try

end repeat set AppleScript's text item delimiters to linefeed set output to output as text set AppleScript's text item delimiters to astid return output</lang>

Output:

<lang applescript>"{} nests to: {} {1, 2, 4} nests to: {1, {2, Template:4}} {3, 1, 3, 1} nests to: {Template:3, 1, Template:3, 1} {1, 2, 3, 1} nests to: {1, {2, {3}}, 1} {3, 2, 1, 3} nests to: {{{3}, 2}, 1, Template:3} {3, 3, 3, 1, 1, 3, 3, 3} nests to: {Template:3, 3, 3, 1, 1, Template:3, 3, 3}"</lang>

Go

Translation of: Python

This is based on the Python recursive version. <lang go>package main

import "fmt"

type any = interface{}

func toTree(list []int, index, depth int) (int, []any) { 

   var soFar []any
   for index < len(list) {
       t := list[index]
       if t == depth {
           soFar = append(soFar, t)
       } else if t > depth {
           var deeper []any
           index, deeper = toTree(list, index, depth+1)
           soFar = append(soFar, deeper)
       } else {
           index = index - 1
           break
       }
       index = index + 1
   }
   if depth > 1 {
       return index, soFar
   }
   return -1, soFar

}

func main() { 

   tests := [][]int{
       {},
       {1, 2, 4},
       {3, 1, 3, 1},
       {1, 2, 3, 1},
       {3, 2, 1, 3},
       {3, 3, 3, 1, 1, 3, 3, 3},
   }
   for _, test := range tests {
       _, nest := toTree(test, 0, 1)
       fmt.Printf("%17s => %v\n", fmt.Sprintf("%v", test), nest)
   }

}</lang>

Output:
               [] => []
          [1 2 4] => [1 [2 [[4]]]]
        [3 1 3 1] => [[[3]] 1 [[3]] 1]
        [1 2 3 1] => [1 [2 [3]] 1]
        [3 2 1 3] => [[[3] 2] 1 [[3]]]
[3 3 3 1 1 3 3 3] => [[[3 3 3]] 1 1 [[3 3 3]]]

Haskell

The output notation shown here would be rejected by Haskell because of the inconsistency of the types in each 'list' – sometime integer, sometimes list of integer, sometimes list of list of integer etc.

For the task description's format that can be used for further calculations we can turn to Haskell's Data.Tree types, which give us a Forest (a consistently-typed list of Trees), where a single Tree combines some node value with a Forest of Trees.

The node value will have to be a sum type like `Maybe Int`, where implicit Tree nodes (that have no explicit Int value) have a `Nothing` value.

For display purposes, we can either show the list of Tree records directly, or use the drawForest and drawTree functions defined in the standard Data.Tree module.

<lang haskell>{-# LANGUAGE TupleSections #-}

import Data.Bifunctor import Data.Tree

FOREST FROM NEST LEVELS ----------------

levelIntegerForest :: [Int] -> Forest (Maybe Int) levelIntegerForest = 

 forestFromNestLevels
   . rooted
   . normalised

forestFromNestLevels :: [(Int, a)] -> Forest a forestFromNestLevels = go 

 where
   go [] = []
   go ((n, v) : xs) =
     uncurry (:) $
       bimap (Node v . go) go (span ((n <) . fst) xs)

TEST AND DISPLAY -------------------

main :: IO () main = 

 mapM_ putStrLn $
   fmap
     ( unlines
         . ( (:) <$> show
               <*> (pure . display . levelIntegerForest)
           )
     )
     [ [],
       [1, 2, 4],
       [3, 1, 3, 1],
       [1, 2, 3, 1],
       [3, 2, 1, 3],
       [3, 3, 3, 1, 1, 3, 3, 3]
     ]

display :: Show a => [Tree a] -> String display = drawTree . Node "Nothing" . fmap (fmap show)

MAPPING TO A STRICTER DATA STRUCTURE ---------

-- Path from the virtual root to the first explicit node. rooted :: [(Int, Maybe Int)] -> [(Int, Maybe Int)] rooted [] = [] rooted xs = go $ filter ((1 <=) . fst) xs 

 where
   go xs@((1, mb) : _) = xs
   go xs@((n, mb) : _) =
     fmap (,Nothing) [1 .. pred n] <> xs

-- Representation of implicit nodes. normalised [] = [] normalised [x] = [(x, Just x)] normalised (x : y : xs) 

 | 1 < (y - x) =
   (x, Just x) :
   (succ x, Nothing) : normalised (y : xs)
 | otherwise = (x, Just x) : normalised (y : xs)</lang>
Output:
[]
Nothing


[1,2,4]
Nothing
|
`- Just 1
   |
   `- Just 2
      |
      `- Nothing
         |
         `- Just 4


[3,1,3,1]
Nothing
|
+- Nothing
|  |
|  `- Nothing
|     |
|     `- Just 3
|
+- Just 1
|  |
|  `- Nothing
|     |
|     `- Just 3
|
`- Just 1


[1,2,3,1]
Nothing
|
+- Just 1
|  |
|  `- Just 2
|     |
|     `- Just 3
|
`- Just 1


[3,2,1,3]
Nothing
|
+- Nothing
|  |
|  +- Nothing
|  |  |
|  |  `- Just 3
|  |
|  `- Just 2
|
`- Just 1
   |
   `- Nothing
      |
      `- Just 3


[3,3,3,1,1,3,3,3]
Nothing
|
+- Nothing
|  |
|  `- Nothing
|     |
|     +- Just 3
|     |
|     +- Just 3
|     |
|     `- Just 3
|
+- Just 1
|
`- Just 1
   |
   `- Nothing
      |
      +- Just 3
      |
      +- Just 3
      |
      `- Just 3

Julia

<lang julia>function makenested(list) 

   nesting = 0
   str = isempty(list) ? "[]" : ""
   for n in list
       if n > nesting
           str *=  "["^(n - nesting)
           nesting = n
       elseif n < nesting
           str *= "]"^(nesting - n) * ", "
           nesting = n
       end
       str *= "$n, "
   end
   str *= "]"^nesting
   return eval(Meta.parse(str))

end

for test in [[], [1, 2, 4], [3, 1, 3, 1], [1, 2, 3, 1], [3, 2, 1, 3], [3, 3, 3, 1, 1, 3, 3, 3]] 

   result = "$test  =>  $(makenested(test))"
   println(replace(result, "Any" => ""))

end

</lang>

Output:
[]  =>  []
[1, 2, 4]  =>  [1, [2, [[4]]]]
[3, 1, 3, 1]  =>  [[[3]], 1, [[3]], 1]
[1, 2, 3, 1]  =>  [1, [2, [3]], 1]
[3, 2, 1, 3]  =>  [[[3], 2], 1, [[3]]]
[3, 3, 3, 1, 1, 3, 3, 3]  =>  [[[3, 3, 3]], 1, 1, [[3, 3, 3]]]

Phix

I was thinking along the same lines but admit I had a little peek at the (recursive) python solution.. <lang Phix>function test(sequence s, integer level=1, idx=1) 

   sequence res = {}, part
   while idx<=length(s) do
       switch compare(s[idx],level) do
           case +1: {idx,part} = test(s,level+1,idx)
                    res = append(res,part)
           case  0: res &= s[idx]
           case -1: idx -= 1 exit
       end switch
       idx += 1
   end while
   return iff(level=1?res:{idx,res})

end function

constant tests = {{}, 

                 {1, 2, 4},

-- {1, 2, 4, 2, 2, 1}, -- (fine too) 

                 {3, 1, 3, 1},
                 {1, 2, 3, 1},
                 {3, 2, 1, 3},
                 {3, 3, 3, 1, 1, 3, 3, 3}}

for i=1 to length(tests) do 

   sequence ti = tests[i],
            res = test(ti),
            rpp = ppf(res,{pp_Nest,3,pp_Indent,4})
   printf(1,"%v nests to %v\n or %s\n",{ti,res,rpp})

end for</lang>

Output:
{} nests to {}
 or {}

{1,2,4} nests to {1,{2,{{4}}}}
 or {1,
     {2,
      {{4}}}}

{3,1,3,1} nests to {{{3}},1,{{3}},1}
 or {{{3}},
     1,
     {{3}},
     1}

{1,2,3,1} nests to {1,{2,{3}},1}
 or {1,
     {2,
      {3}},
     1}

{3,2,1,3} nests to {{{3},2},1,{{3}}}
 or {{{3},
      2},
     1,
     {{3}}}

{3,3,3,1,1,3,3,3} nests to {{{3,3,3}},1,1,{{3,3,3}}}
 or {{{3,
       3,
       3}},
     1,
     1,
     {{3,
       3,
       3}}}

Python

Python: Procedural

Python: Recursive

<lang python>def to_tree(x, index=0, depth=1): 

  so_far = []
  while index < len(x):
      this = x[index]
      if this == depth:
          so_far.append(this)
      elif this > depth:
          index, deeper = to_tree(x, index, depth + 1)
          so_far.append(deeper)
      else: # this < depth:
          index -=1
          break
      index += 1
  return (index, so_far) if depth > 1 else so_far


if __name__ == "__main__": 

   from pprint import pformat

   def pnest(nest:list, width: int=9) -> str:
       text = pformat(nest, width=width).replace('\n', '\n    ')
       print(f" OR {text}\n")

   exercises = [
       [],
       [1, 2, 4],
       [3, 1, 3, 1],
       [1, 2, 3, 1],
       [3, 2, 1, 3],
       [3, 3, 3, 1, 1, 3, 3, 3],
       ]
   for flat in exercises:
       nest = to_tree(flat)
       print(f"{flat} NESTS TO: {nest}")
       pnest(nest)</lang>
Output:
[] NESTS TO: []
 OR []

[1, 2, 4] NESTS TO: [1, [2, [[4]]]]
 OR [1,
     [2,
      [[4]]]]

[3, 1, 3, 1] NESTS TO: [[[3]], 1, [[3]], 1]
 OR [[[3]],
     1,
     [[3]],
     1]

[1, 2, 3, 1] NESTS TO: [1, [2, [3]], 1]
 OR [1,
     [2,
      [3]],
     1]

[3, 2, 1, 3] NESTS TO: [[[3], 2], 1, [[3]]]
 OR [[[3],
      2],
     1,
     [[3]]]

[3, 3, 3, 1, 1, 3, 3, 3] NESTS TO: [[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
 OR [[[3,
       3,
       3]],
     1,
     1,
     [[3,
       3,
       3]]]

Python: Iterative

<lang python>def to_tree(x: list) -> list: 

  nested = []
  stack = [nested]
  for this in x:
      while this != len(stack):
          if this > len(stack):
              innermost = []               # new level
              stack[-1].append(innermost)  # nest it
              stack.append(innermost)      # push it
          else: # this < stack:
              stack.pop(-1)
      stack[-1].append(this)

  return nested

</lang>

Output:

Using the same main block it produces the same output as the recursive case above.

Python: Functional

A translation of the sparse level-lists to a stricter generic data structure gives us access to standard tree-walking functions,

allowing for simpler top-level functions, and higher levels of code reuse.

Here, for example, we apply a generic tree-drawing function. <lang python>Tree from nesting levels

from itertools import chain, repeat from operator import add

  1. forestFromLevelInts :: [Int] -> Forest Maybe Int

def forestFromLevelInts(levelList): 

   A Forest (list of Trees) of (Maybe Int) values,
      in which implicit nodes have the value Nothing.
   
   return forestFromLevels(
       rooted(normalized(levelList))
   )


  1. forestFromLevels :: [(Int, a)] -> [Tree a]

def forestFromLevels(nvs): 

   A list of generic trees derived from a list of
      values paired with integers representing
      nesting depths.
   
   def go(xs):
       if xs:
           level, v = xs[0]
           children, rest = span(
               lambda x: level < x[0]
           )(xs[1:])
           return [Node(v)(go(children))] + go(rest)
       else:
           return []
   return go(nvs)


  1. showForest :: Forest Maybe Int -> String

def showForest(forest): 

   A string representation of a list
      of Maybe Int trees.
   
   return drawTree(
       Node('Nothing')([
           fmapTree(showMaybe)(tree) for tree
           in forest
       ])
   )


  1. ------------------------- TEST -------------------------
  2. main :: IO ()

def main(): 

   Test the building and display of
      normalized forests from level integers.
   
   for xs in [
       [],
       [1, 2, 4],
       [3, 1, 3, 1],
       [1, 2, 3, 1],
       [3, 2, 1, 3],
       [3, 3, 3, 1, 1, 3, 3, 3]
   ]:
       (
           print(xs),
           print(
               showForest(
                   forestFromLevelInts(xs)
               )
           ),
           print()
       )


  1. ------ TRANSLATION TO A CONSISTENT DATA STRUCTURE ------
  1. normalized :: [Int] -> [(Int, Maybe Int)]

def normalized(xs): 

   Explicit representation of implicit nodes.
   
   if xs:
       x = xs[0]
       h = [(x, Just(x))]
       return h if 1 == len(xs) else (
           h + [(1 + x, Nothing())] if (
               1 < (xs[1] - x)
           ) else h
       ) + normalized(xs[1:])
   else:
       return []


  1. rooted :: [(Int, Maybe Int)] -> [(Int, Maybe Int)]

def rooted(pairs): 

   Path from the virtual root
      to the first explicit node.
   
   def go(xs):
       n = xs[0][0]
       return xs if 1 == n else (
           [(x, Nothing()) for x in range(1, n)] + xs
       )
   return go([
       x for x in pairs if 1 <= x[0]
   ]) if pairs else []


  1. ---------------- GENERIC TREE FUNCTIONS ----------------
  1. Node :: a -> [Tree a] -> Tree a

def Node(v): 

   Constructor for a Tree node which connects a
      value of some kind to a list of zero or
      more child trees.
   
   return lambda xs: {'type': 'Tree', 'root': v, 'nest': xs}


  1. draw :: Tree a -> [String]

def draw(node): 

   List of the lines of an ASCII
      diagram of a tree.
   
   def shift_(h, other, xs):
       return list(map(
           add,
           chain(
               [h], (
                   repeat(other, len(xs) - 1)
               )
           ),
           xs
       ))

   def drawSubTrees(xs):
       return (
           (
               ['|'] + shift_(
                   '├─ ', '│  ', draw(xs[0])
               ) + drawSubTrees(xs[1:])
           ) if 1 < len(xs) else ['|'] + shift_(
               '└─ ', '   ', draw(xs[0])
           )
       ) if xs else []

   return (root(node)).splitlines() + (
       drawSubTrees(nest(node))
   )


  1. drawForest :: [Tree String] -> String

def drawForest(trees): 

   A simple unicode character representation of
      a list of trees.
   
   return '\n'.join(map(drawTree, trees))


  1. drawTree :: Tree a -> String

def drawTree(tree): 

   ASCII diagram of a tree.
   return '\n'.join(draw(tree))


  1. fmapTree :: (a -> b) -> Tree a -> Tree b

def fmapTree(f): 

   A new tree holding the results of
      an application of f to each root in
      the existing tree.
   
   def go(x):
       return Node(
           f(x['root'])
       )([go(v) for v in x['nest']])
   return go


  1. nest :: Tree a -> [Tree a]

def nest(t): 

   Accessor function for children of tree node.
   return t.get('nest')


  1. root :: Tree a -> a

def root(t): 

   Accessor function for data of tree node.
   return t.get('root')


  1. -------------------- GENERIC OTHER ---------------------
  1. Just :: a -> Maybe a

def Just(x): 

   Constructor for an inhabited Maybe (option type) value.
      Wrapper containing the result of a computation.
   
   return {'type': 'Maybe', 'Nothing': False, 'Just': x}


  1. Nothing :: () -> Maybe a

def Nothing(): 

   Constructor for an empty Maybe (option type) value.
      Empty wrapper returned where a computation is not possible.
   
   return {'type': 'Maybe', 'Nothing': True}


  1. showMaybe :: Maybe a -> String

def showMaybe(mb): 

   Stringification of a Maybe value.
   return 'Nothing' if (
       mb.get('Nothing')
   ) else 'Just ' + repr(mb.get('Just'))


  1. span :: (a -> Bool) -> [a] -> ([a], [a])

def span(p): 

   The longest (possibly empty) prefix of xs
   that contains only elements satisfying p,
   tupled with the remainder of xs.
   span p xs is equivalent to (takeWhile p xs, dropWhile p xs).
   
   def match(ab):
       b = ab[1]
       return not b or not p(b[0])

   def f(ab):
       a, b = ab
       return a + [b[0]], b[1:]

   def go(xs):
       return until(match)(f)(([], xs))
   return go


  1. until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p): 

   The result of repeatedly applying f until p holds.
   The initial seed value is x.
   
   def go(f):
       def g(x):
           v = x
           while not p(v):
               v = f(v)
           return v
       return g
   return go


  1. MAIN ---

if __name__ == '__main__': 

   main()</lang>
Output:
[]
Nothing

[1, 2, 4]
Nothing
|
└─ Just 1
   |
   └─ Just 2
      |
      └─ Nothing
         |
         └─ Just 4

[3, 1, 3, 1]
Nothing
|
├─ Nothing
│  |
│  └─ Nothing
│     |
│     └─ Just 3
|
├─ Just 1
│  |
│  └─ Nothing
│     |
│     └─ Just 3
|
└─ Just 1

[1, 2, 3, 1]
Nothing
|
├─ Just 1
│  |
│  └─ Just 2
│     |
│     └─ Just 3
|
└─ Just 1

[3, 2, 1, 3]
Nothing
|
├─ Nothing
│  |
│  ├─ Nothing
│  │  |
│  │  └─ Just 3
│  |
│  └─ Just 2
|
└─ Just 1
   |
   └─ Nothing
      |
      └─ Just 3

[3, 3, 3, 1, 1, 3, 3, 3]
Nothing
|
├─ Nothing
│  |
│  └─ Nothing
│     |
│     ├─ Just 3
│     |
│     ├─ Just 3
│     |
│     └─ Just 3
|
├─ Just 1
|
└─ Just 1
   |
   └─ Nothing
      |
      ├─ Just 3
      |
      ├─ Just 3
      |
      └─ Just 3

Wren

Translation of: Python
Library: Wren-seq
Library: Wren-fmt

More or less the same as the Python iterative version. <lang ecmascript>import "/seq" for Stack import "/fmt" for Fmt

var toTree = Fn.new { |list| 

   var nested = []
   var s = Stack.new()
   s.push(nested)
   for (n in list) {
       while (n != s.count) {
           if (n > s.count) {
               var inner = []
               s.peek().add(inner)
               s.push(inner)
           } else {
               s.pop()
           }
       }
       s.peek().add(n)
   }
   return nested

}

var tests = [ 

   [],
   [1, 2, 4],
   [3, 1, 3, 1],
   [1, 2, 3, 1],
   [3, 2, 1, 3],
   [3, 3, 3, 1, 1, 3, 3, 3]

] for (test in tests) { 

   var nest = toTree.call(test)
   Fmt.print("$24n => $n", test, nest)

}</lang>

Output:
                      [] => []
               [1, 2, 4] => [1, [2, [[4]]]]
            [3, 1, 3, 1] => [[[3]], 1, [[3]], 1]
            [1, 2, 3, 1] => [1, [2, [3]], 1]
            [3, 2, 1, 3] => [[[3], 2], 1, [[3]]]
[3, 3, 3, 1, 1, 3, 3, 3] => [[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
Retrieved from "https://rosettacode.org/wiki/Tree_from_nesting_levels?oldid=307398"