Tree from nesting levels: Difference between revisions

Content added Content deleted

Inline

Revision as of 09:00, 7 February 2021

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

Iterative

<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>

Recursive

Same task code and output as above. <lang applescript>on treeFromNestingLevels(input)

   script recursion
       property emptyList : {}
       
       on recurse(input, currentLevel)
           set output to {}
           set subnest to {}
           repeat with thisLevel in input
               set thisLevel to thisLevel's contents
               if (thisLevel > currentLevel) then
                   set end of subnest to thisLevel
               else
                   if (subnest ≠ emptyList) then
                       set end of output to recurse(subnest, currentLevel + 1)
                       set subnest to {}
                   end if
                   set end of output to thisLevel
               end if
           end repeat
           if (subnest ≠ emptyList) then set end of output to recurse(subnest, currentLevel + 1)
           
           return output
       end recurse
   end script
   
   return recursion's recurse(input, 1)

end treeFromNestingLevels</lang>

C++

Uses C++20 <lang cpp>#include <any>

include <iostream>
include <iterator>
include <vector>

using namespace std;

// Make a tree that is a vector of either values or other trees vector<any> MakeTree(input_iterator auto first, input_iterator auto last, int depth = 1) {

   vector<any> tree;
   while (first < last && depth <= *first)
   {
       if(*first == depth)
       {
           // add a single value
           tree.push_back(*first);
           ++first;
       }
       else // (depth < *b)
       {
           // add a subtree
           tree.push_back(MakeTree(first, last, depth + 1));
           first = find(first + 1, last, depth); 
       }
   }
       
   return tree;

}

// Print an input vector or tree void PrintTree(input_iterator auto first, input_iterator auto last) {

   cout << "[";
   for(auto it = first; it != last; ++it)
   {
       if(it != first) cout << ", ";
       if constexpr (is_integral_v<remove_reference_t<decltype(*first)>>)
       {
           // for printing the input vector
           cout << *it;
       }
       else
       {
           // for printing the tree
           if(it->type() == typeid(unsigned int))
           {
               // a single value
               cout << any_cast<unsigned int>(*it);
           }
           else
           {
               // a subtree
               const auto& subTree = any_cast<vector<any>>(*it);
               PrintTree(subTree.begin(), subTree.end());
           }
       }
   }
   cout << "]";

}

int main(void) {

   auto execises = vector<vector<unsigned 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(const auto& e : execises)
   {
       auto tree = MakeTree(e.begin(), e.end());
       PrintTree(e.begin(), e.end());
       cout << " Nests to:\n"; 
       PrintTree(tree.begin(), tree.end());
       cout << "\n\n";
   }

} </lang>

Output:

[] Nests to:
[]

[1, 2, 4] Nests to:
[1, [2, [[4]]]]

[3, 1, 3, 1] Nests to:
[[[3]], 1, [[3]], 1]

[1, 2, 3, 1] Nests to:
[1, [2, [3]], 1]

[3, 2, 1, 3] Nests to:
[[[3], 2], 1, [[3]]]

[3, 3, 3, 1, 1, 3, 3, 3] Nests to:
[[[3, 3, 3]], 1, 1, [[3, 3, 3]]]

Go

Iterative

Translation of: Python

<lang go>package main

import "fmt"

type any = interface{}

func toTree(list []int) any {

   s := []any{[]any{}}
   for _, n := range list {
       for n != len(s) {
           if n > len(s) {
               inner := []any{}
               s[len(s)-1] = append(s[len(s)-1].([]any), inner)
               s = append(s, inner)
           } else {
               s = s[0 : len(s)-1]
           }
       }
       s[len(s)-1] = append(s[len(s)-1].([]any), n)
       for i := len(s) - 2; i >= 0; i-- {
           le := len(s[i].([]any))
           s[i].([]any)[le-1] = s[i+1]
       }
   }
   return s[0]

}

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)
       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]]]

Recursive

Translation of: Python

<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:

Same as iterative version.

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.

We can reverse the translation, from tree back to sparse list, without loss of information, by using a standard fold. See sparseLevelsFromTree below:

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

import Data.Bifunctor (bimap) import Data.Tree (Forest, Tree (..), drawTree, foldTree)

TREE FROM NEST LEVELS (AND BACK) -----------

treeFromSparseLevels :: [Int] -> Tree (Maybe Int) treeFromSparseLevels =

 Node Nothing
   . forestFromNestLevels
   . rooted
   . normalised

sparseLevelsFromTree :: Tree (Maybe Int) -> [Int] sparseLevelsFromTree = foldTree go

 where
   go Nothing xs = concat xs
   go (Just x) xs = x : (concat xs)

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_
   ( \xs ->
       putStrLn ("From: " <> show xs)
         >> let tree = treeFromSparseLevels xs
             in putStrLn ((drawTree . fmap show) tree)
                  >> putStrLn
                    ( "Back to: "
                        <> show (sparseLevelsFromTree tree)
                        <> "\n\n"
                    )
   )
   [ [],
     [1, 2, 4],
     [3, 1, 3, 1],
     [1, 2, 3, 1],
     [3, 2, 1, 3],
     [3, 3, 3, 1, 1, 3, 3, 3]
   ]

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:

From: []
Nothing

Back to: []


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

Back to: [1,2,4]


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

Back to: [3,1,3,1]


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

Back to: [1,2,3,1]


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

Back to: [3,2,1,3]


From: [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

Back to: [3,3,3,1,1,3,3,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]]]

Perl

String Eval

<lang perl>#!/usr/bin/perl

use strict; use warnings; use Data::Dump qw(dd pp);

my @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 my $before ( @tests )

 {
 dd { before => $before };
 local $_ = (pp $before) =~ s/\d+/ '['x($&-1) . $& . ']'x($&-1) /ger;
 1 while s/\](,\s*)\[/$1/;
 my $after = eval;
 dd { after => $after };
 }</lang>

Output:

{ before => [] }
{ after => [] }
{ before => [1, 2, 4] }
{ after => [1, [2, [[4]]]] }
{ before => [3, 1, 3, 1] }
{ after => [[[3]], 1, [[3]], 1] }
{ before => [1, 2, 3, 1] }
{ after => [1, [2, [3]], 1] }
{ before => [3, 2, 1, 3] }
{ after => [[[3], 2], 1, [[3]]] }
{ before => [3, 3, 3, 1, 1, 3, 3, 3] }
{ after => [[[3, 3, 3]], 1, 1, [[3, 3, 3]]] }

Iterative

Translation of: Raku

<lang perl>use 5.020_000; # Also turns on `strict` use warnings; use experimental qw<signatures>; use Data::Dump qw<pp>;

sub new_level ( $stack ) {

   my $e = [];
   push @{ $stack->[-1] }, $e;
   push @{ $stack       }, $e;

} sub to_tree_iterative ( @xs ) {

   my $nested = [];
   my $stack  = [$nested];

   for my $x (@xs) {
       new_level($stack) while $x > @{$stack};
       pop     @{$stack} while $x < @{$stack};
       push    @{$stack->[-1]},$x;
   }

   return $nested;

} my @tests = ([],[1,2,4],[3,1,3,1],[1,2,3,1],[3,2,1,3],[3,3,3,1,1,3,3,3]); say sprintf('%15s => ', join(' ', @{$_})), pp(to_tree_iterative(@{$_})) for @tests;</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}}}

iterative

<lang Phix>function nest(sequence input)

   if length(input) then
       for level=max(input) to 2 by -1 do
           sequence output = {}
           bool subnest = false
           for i=1 to length(input) do
               object ii = input[i]
               if integer(ii) and ii<level then
                   subnest = false
                   output &= ii
               elsif not subnest then
                   output &= Template:Ii
                   subnest = true
               else
                   output[$] &= {ii}
               end if
           end for
           input = output
       end for
   end if
   return input

end function</lang> Same output (using nest instead of test)

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
for the return trip from tree to list, a generic catamorphism over trees (foldTree).

<lang python>Tree from nesting levels

from itertools import chain, repeat from operator import add

treeFromSparseLevels :: [Int] -> Tree Maybe Int

def treeFromSparseLevels(levelList):

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

sparseLevelsFromTree :: Tree (Maybe Int) -> [Int]

def sparseLevelsFromTree(tree):

   Sparse representation of the tree
      a list of nest level integers.
   
   def go(x):
       return lambda xs: concat(xs) if (
           x.get('Nothing', False)
       ) else [x.get('Just', 0)] + concat(xs)
   return foldTree(go)(tree)

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)

showTree :: Tree Maybe Int -> String

def showTree(tree):

   A string representation of
      a Maybe Int tree.
   
   return drawTree(
       fmapTree(showMaybe)(tree)
   )

------------------------- TEST -------------------------
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]
   ]:
       tree = treeFromSparseLevels(xs)
       (
           print('From: ' + repr(xs)),
           print(showTree(tree)),
           print(
               'Back to: ' + (
                   repr(sparseLevelsFromTree(tree))
               )
           ),
           print()
       )

------ TRANSLATION TO A CONSISTENT DATA STRUCTURE ------

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 []

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 []

---------------- GENERIC TREE FUNCTIONS ----------------

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}

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))
   )

drawForest :: [Tree String] -> String

def drawForest(trees):

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

drawTree :: Tree a -> String

def drawTree(tree):

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

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

foldTree :: (a -> [b] -> b) -> Tree a -> b

def foldTree(f):

   The catamorphism on trees. A summary
      value defined by a depth-first fold.
   
   def go(node):
       return f(root(node))([
           go(x) for x in nest(node)
       ])
   return go

nest :: Tree a -> [Tree a]

def nest(t):

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

root :: Tree a -> a

def root(t):

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

-------------------- GENERIC OTHER ---------------------

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}

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}

concat :: a -> [a]
concat :: [String] -> String

def concat(xs):

   The concatenation of all the elements
      in a list or iterable.
   
   def f(ys):
       zs = list(chain(*ys))
       return .join(zs) if isinstance(ys[0], str) else zs

   return (
       f(xs) if isinstance(xs, list) else (
           chain.from_iterable(xs)
       )
   ) if xs else []

showMaybe :: Maybe a -> String

def showMaybe(mb):

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

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

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

MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

From: []
Nothing
Back to: []

From: [1, 2, 4]
Nothing
|
└─ Just 1
   |
   └─ Just 2
      |
      └─ Nothing
         |
         └─ Just 4
Back to: [1, 2, 4]

From: [3, 1, 3, 1]
Nothing
|
├─ Nothing
│  |
│  └─ Nothing
│     |
│     └─ Just 3
|
├─ Just 1
│  |
│  └─ Nothing
│     |
│     └─ Just 3
|
└─ Just 1
Back to: [3, 1, 3, 1]

From: [1, 2, 3, 1]
Nothing
|
├─ Just 1
│  |
│  └─ Just 2
│     |
│     └─ Just 3
|
└─ Just 1
Back to: [1, 2, 3, 1]

From: [3, 2, 1, 3]
Nothing
|
├─ Nothing
│  |
│  ├─ Nothing
│  │  |
│  │  └─ Just 3
│  |
│  └─ Just 2
|
└─ Just 1
   |
   └─ Nothing
      |
      └─ Just 3
Back to: [3, 2, 1, 3]

From: [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
Back to: [3, 3, 3, 1, 1, 3, 3, 3]

Raku

Iterative

Translation of: Python

<lang perl6>sub new_level ( @stack --> Nil ) {

   my $e = [];
   push @stack.tail, $e;
   push @stack,      $e;

} sub to_tree_iterative ( @xs --> List ) {

   my $nested = [];
   my @stack  = $nested;

   for @xs -> Int $x {
       new_level(@stack) while $x > @stack;
       pop       @stack  while $x < @stack;
       push @stack.tail, $x;
   }

   return $nested;

} my @tests = (), (1, 2, 4), (3, 1, 3, 1), (1, 2, 3, 1), (3, 2, 1, 3), (3, 3, 3, 1, 1, 3, 3, 3); say .Str.fmt( '%15s => ' ), .&to_tree_iterative for @tests;</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]]]

Recursive

Translation of: Python

<lang perl6>sub to_tree_recursive ( @list, $index is copy, $depth ) {

   my @so_far = gather while $index <= @list.end {
       my $t = @list[$index];

       given $t <=> $depth {
           when Order::Same {
               take $t;
           }
           when Order::More {
               ( $index, my $n1 ) = to_tree_recursive( @list, $index, $depth+1 );
               take $n1;
           }
           when Order::Less {
               $index--;
               last;
           }
       }
       $index++;
   }

   my $i = ($depth > 1) ?? $index !! -1;
   return $i, @so_far;

} my @tests = (), (1, 2, 4), (3, 1, 3, 1), (1, 2, 3, 1), (3, 2, 1, 3), (3, 3, 3, 1, 1, 3, 3, 3); say .Str.fmt( '%15s => ' ), to_tree_recursive( $_, 0, 1 ).[1] for @tests;</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]]]

String Eval

Translation of: Perl

<lang perl6>use MONKEY-SEE-NO-EVAL; sub to_tree_string_eval ( @xs --> Array ) {

   my @gap = [ |@xs, 0 ]  Z-  [ 0, |@xs ];

   my @open  = @gap.map( '[' x  * );
   my @close = @gap.map( ']' x -* );

   my @wrapped = [Z~] @open, @xs, @close.skip;

   return EVAL @wrapped.join(',').subst(:g, ']]', '],]') || '[]';

} my @tests = (), (1, 2, 4), (3, 1, 3, 1), (1, 2, 3, 1), (3, 2, 1, 3), (3, 3, 3, 1, 1, 3, 3, 3); say .Str.fmt( '%15s => ' ), .&to_tree_string_eval for @tests;</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]]]

Wren

Iterative

Translation of: Python

Library: Wren-seq

Library: Wren-fmt

<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]]]

Recursive

Translation of: Python

<lang ecmascript>import "/fmt" for Fmt

var toTree // recursive toTree = Fn.new { |list, index, depth|

   var soFar = []
   while (index < list.count) {
       var t = list[index]
       if (t == depth) {
           soFar.add(t)
       } else if (t > depth) {
           var n = toTree.call(list, index, depth+1)
           index = n[0]
           soFar.add(n[1])
       } else {
           index = index - 1
           break
       }
       index = index + 1
   }
   if (depth > 1) return [index, soFar]
   return [-1, soFar]

}

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 n = toTree.call(test, 0, 1)
   Fmt.print("$24n => $n", test, n[1])

}</lang>

Output:

Same as iterative version.