Rosetta Code

Tree datastructures: Difference between revisions

Page Discussion

Tree datastructures (view source)

Revision as of 18:12, 12 May 2024

30,759 bytes added ,  11 days ago
PascalABC.NET solution added before Perl
(PascalABC.NET solution added before Perl)
(44 intermediate revisions by 14 users not shown)
Line 1:
{{draft task}}
The following shows a tree of data with nesting denoted by visual levels of indentation:
<pre>RosettaCode
Line 7:
wiki
mocks
golfingtrolling</pre>
 
A common datastructure for trees is to define node structures having a name and a, (possibly empty), list of child nodes. The nesting of nodes captures the indentation of the tree. Lets call this '''the nest form'''.
Line 34:
;Note:
* It's all about showing aspects of the contrasting datastructures as they hold the tree.
* The word "golfing" may be substituted by "trolling" in the tree as golfing can be friendly fun! (just not for RC examples).
* Comparing nested datastructures is secondary - saving formatted output as a string then a string compare would suffice for this task, if its easier.
<br>
Line 40 ⟶ 39:
Show all output on this page.
 
=={{header|AppleScript11l}}==
{{trans|Nim}}
{{incorrect|AppleScript|"Strayed" from task example}}
The 'mocking' task example seems a little unpleasant. Perhaps an alternative ?
<lang applescript>use AppleScript version "2.4"
use framework "Foundation"
use scripting additions
 
<syntaxhighlight lang="11l">T NNode
on run
String value
set strOutline to ¬
[NNode] children
"The Rosetta stone\n" & ¬
" is a granodiorite stele\n" & ¬
" engraved\n" & ¬
" with Greek and Egyptian texts\n" & ¬
" in different scripts.\n" & ¬
" which, in the 19c, shed new light\n" & ¬
" on various homologies."
set forestA to ¬
forestFromNestLevels(indentLevelsFromLines(paragraphs of strOutline))
set indentLevels to nestLevelsFromForest(forestA)
set forestB to forestFromNestLevels(indentLevels)
-- Logged to Messages panel of macOS Script Editor
log intercalate(linefeed & linefeed, {¬
"Outline:", ¬
strOutline, ¬
"Forest from outline:", ¬
forestJSON(forestA), ¬
"Nesting levels from forest:", ¬
toJSON(indentLevels), ¬
"Forest rebuilt from nesting levels", ¬
forestJSON(forestB), ¬
"Equality test:", ¬
"(forestA = forestB) -> " & (forestA = forestB)})
end run
 
F (value)
-- TREES ⇄ LEVEL TUPLES ----------------------------------
.value = value
 
F add(node)
-- forestFromNestLevels :: [(Int, a)] -> [Tree a]
.children.append(node)
on forestFromNestLevels(tuples)
-- A list of trees derived from a list of values paired
-- with integers giving their levels of indentation.
script go
on |λ|(xs)
if 0 < length of xs then
set lineOne to item 1 of xs
set {intIndent, v} to {fst(lineOne), snd(lineOne)}
set {firstTreeLines, remainingLines} to ¬
listFromTuple(|λ|(rest of xs) of ¬
span(compose(lt(intIndent), my fst)))
{Node(v, |λ|(firstTreeLines) of go)} & |λ|(remainingLines) of go
else
{}
end if
end |λ|
end script
|λ|(tuples) of go
end forestFromNestLevels
 
F.const to_str(depth) -> String
V result = (‘ ’ * depth)‘’(.value)"\n"
L(child) .children
result ‘’= child.to_str(depth + 1)
R result
 
F String()
-- nestLevelsFromForest :: [Tree a] -> [(Int, a)]
R .to_str(0)
on nestLevelsFromForest(trees)
-- A flat list of (nest level, value) tuples,
-- representing a series of trees.
script go
on |λ|(level)
script
on |λ|(tree)
{{level, root of tree}} & ¬
concatMap(|λ|(1 + level) of go, nest of tree)
end |λ|
end script
end |λ|
end script
concatMap(|λ|(0) of go, trees)
end nestLevelsFromForest
 
T INode
String value
Int level
F (value, level)
.value = value
.level = level
 
F to_indented(node)
-- INDENT LEVELS FROM OUTLINE ----------------------------
[INode] result
F add_node(NNode node, Int level) -> Void
@result.append(INode(node.value, level))
L(child) node.children
@add_node(child, level + 1)
add_node(node, 0)
R result
 
F to_nested(tree)
--indentLevelsFromLines :: [String] -> [(Int, String)]
[NNode] stack
on indentLevelsFromLines(xs)
V nnode = NNode(tree[0].value)
set tuples to map(compose(firstArrow(my |length|), ¬
L(i) 1 .< tree.len
span(my isSpace)), xs)
V inode = tree[i]
I inode.level > stack.len
script minimumIndent
on |λ|stack.append(a, tplnnode)
E I inode.level == set n to fst(tpl)stack.len
stack.last.children.append(nnode)
bool(a, n, n < a and 0 < n)
end |λ|E
L inode.level < stack.len
end script
stack.last.children.append(nnode)
set indentUnit to foldl(minimumIndent, 100, tuples)
nnode = stack.pop()
stack.last.children.append(nnode)
map(firstArrow(flipDiv(indentUnit)), tuples)
nnode = NNode(inode.value)
end indentLevelsFromLines
 
L stack.len > 0
stack.last.children.append(nnode)
nnode = stack.pop()
 
R nnode
-- JSON SERIALISATIONS ------------------------------------
 
print(‘Displaying tree built using nested structure:’)
-- forestJSON :: [Tree a] -> JSON String
V nestedTree = NNode(‘RosettaCode’)
on forestJSON(trees)
V rocks = NNode(‘rocks’)
toJSON(forestAsNestedPairs(trees))
rocks.add(NNode(‘code’))
end forestJSON
rocks.add(NNode(‘comparison’))
rocks.add(NNode(‘wiki’))
V mocks = NNode(‘mocks’)
mocks.add(NNode(‘trolling’))
nestedTree.add(rocks)
nestedTree.add(mocks)
print(nestedTree)
 
print(‘Displaying tree converted to indented structure:’)
-- forestAsNestedPairs :: [Tree a] -> NestedPair [(a, [NestedPair])]
V indentedTree = to_indented(nestedTree)
on forestAsNestedPairs(xs)
L(node) indentedTree
--A simple nested pair representation of a tree.
print((node.level)‘ ’(node.value))
script go
print()
on |λ|(tree)
{root of tree, map(go, nest of tree)}
end |λ|
end script
map(go, xs)
end forestAsNestedPairs
 
print(‘Displaying tree converted back to nested structure:’)
-- toJSON :: Show a => a -> String
print(to_nested(indentedTree))
on toJSON(a)
set blnAtom to {list, record} does not contain class of a
if blnAtom then
set obj to {a}
else
set obj to a
end if
set ca to current application
try
set {v, e} to ca's NSJSONSerialization's ¬
dataWithJSONObject:obj options:0 |error|:(reference)
on error
return ("(Not representatable as JSON)")
end try
set strJSON to ca's NSString's alloc()'s initWithData:v ¬
encoding:(ca's NSUTF8StringEncoding)
if blnAtom then
text 2 thru -2 of (strJSON as string)
else
strJSON as string
end if
end toJSON
 
print(‘Are they equal? ’(I String(nestedTree) == String(to_nested(indentedTree)) {‘yes’} E ‘no’))</syntaxhighlight>
 
{{out}}
-- GENERIC ------------------------------------------------
<pre>
Displaying tree built using nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Displaying tree converted to indented structure:
-- Node :: a -> [Tree a] -> Tree a
0 RosettaCode
on Node(v, xs)
1 rocks
{type:"Node", root:v, nest:xs}
2 code
end Node
2 comparison
2 wiki
1 mocks
2 trolling
 
Displaying tree converted back to nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Are they equal? yes
-- Tuple (,) :: a -> b -> (a, b)
</pre>
on Tuple(a, b)
-- Constructor for a pair of values, possibly of two different types.
{type:"Tuple", |1|:a, |2|:b, length:2}
end Tuple
 
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
#include <list>
#include <string>
#include <vector>
#include <utility>
#include <vector>
 
class nest_tree;
-- bool :: a -> a -> Bool -> a
on bool(f, t, p)
if p then
set v to t
else
set v to f
end if
-- Delayed evaluation, if needed.
if handler is class of v then
|λ|() of mReturn(v)
else
v
end if
end bool
 
bool operator==(const nest_tree&, const nest_tree&);
-- compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
on compose(f, g)
script
property mf : mReturn(f)
property mg : mReturn(g)
on |λ|(x)
mf's |λ|(mg's |λ|(x))
end |λ|
end script
end compose
 
class nest_tree {
-- concatMap :: (a -> [b]) -> [a] -> [b]
public:
on concatMap(f, xs)
explicit nest_tree(const std::string& name) : name_(name) {}
set lng to length of xs
nest_tree& add_child(const std::string& name) {
set acc to {}
children_.emplace_back(name);
tell mReturn(f)
repeatreturn with i from 1 to lngchildren_.back();
}
set acc to acc & (|λ|(item i of xs, i, xs))
void print(std::ostream& out) const {
end repeat
print(out, 0);
end tell
return acc}
const std::string& name() const {
end concatMap
return name_;
}
const std::list<nest_tree>& children() const {
return children_;
}
bool equals(const nest_tree& n) const {
return name_ == n.name_ && children_ == n.children_;
}
private:
void print(std::ostream& out, int level) const {
std::string indent(level * 4, ' ');
out << indent << name_ << '\n';
for (const nest_tree& child : children_)
child.print(out, level + 1);
}
std::string name_;
std::list<nest_tree> children_;
};
 
bool operator==(const nest_tree& a, const nest_tree& b) {
return a.equals(b);
}
 
class indent_tree {
-- flipDiv:: Int -> Int -> Int
public:
on flipDiv(a)
explicit indent_tree(const nest_tree& n) {
-- Integer division, with arguments reversed
items_.emplace_back(0, n.name());
script
on |λ|from_nest(bn, 0);
b div a}
void print(std::ostream& out) const {
end |λ|
for (const auto& item : items_)
end script
std::cout << item.first << ' ' << item.second << '\n';
end flipDiv
}
nest_tree to_nest() const {
nest_tree n(items_[0].second);
to_nest_(n, 1, 0);
return n;
}
private:
void from_nest(const nest_tree& n, int level) {
for (const nest_tree& child : n.children()) {
items_.emplace_back(level + 1, child.name());
from_nest(child, level + 1);
}
}
size_t to_nest_(nest_tree& n, size_t pos, int level) const {
while (pos < items_.size() && items_[pos].first == level + 1) {
nest_tree& child = n.add_child(items_[pos].second);
pos = to_nest_(child, pos + 1, level + 1);
}
return pos;
}
std::vector<std::pair<int, std::string>> items_;
};
 
int main() {
-- Lift a simple function to one which applies to a tuple,
nest_tree n("RosettaCode");
-- transforming only the first item of the tuple
auto& child1 = n.add_child("rocks");
-- firstArrow :: (a -> b) -> ((a, c) -> (b, c))
auto& child2 = n.add_child("mocks");
on firstArrow(f)
child1.add_child("code");
script
child1.add_child("comparison");
on |λ|(xy)
child1.add_child("wiki");
Tuple(mReturn(f)'s |λ|(|1| of xy), |2| of xy)
child2.add_child("trolling");
end |λ|
end script
std::cout << "Initial nest format:\n";
end firstArrow
n.print(std::cout);
indent_tree i(n);
std::cout << "\nIndent format:\n";
i.print(std::cout);
nest_tree n2(i.to_nest());
std::cout << "\nFinal nest format:\n";
n2.print(std::cout);
 
std::cout << "\nAre initial and final nest formats equal? "
-- foldl :: (a -> b -> a) -> a -> [b] -> a
<< std::boolalpha << n.equals(n2) << '\n';
on foldl(f, startValue, xs)
tell mReturn(f)
return 0;
set v to startValue
}</syntaxhighlight>
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
 
{{out}}
-- fst :: (a, b) -> a
<pre>
on fst(tpl)
Initial nest format:
if class of tpl is record then
RosettaCode
|1| of tpl
elserocks
item 1 of tplcode
end if comparison
wiki
end fst
mocks
trolling
 
Indent format:
0 RosettaCode
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Final nest format:
-- intercalate :: String -> [String] -> String
RosettaCode
on intercalate(delim, xs)
rocks
set {dlm, my text item delimiters} to ¬
code
{my text item delimiters, delim}
set str to xs as textcomparison
set my text item delimiters to dlmwiki
strmocks
trolling
end intercalate
 
-- isSpace :: Char -> Bool
on isSpace(c)
set i to id of c
32 = i or (9 ≤ i and 13 ≥ i)
end isSpace
 
-- length :: [a] -> Int
on |length|(xs)
set c to class of xs
if list is c or string is c then
length of xs
else
(2 ^ 29 - 1) -- (maxInt - simple proxy for non-finite)
end if
end |length|
 
-- listFromTuple :: (a, a ...) -> [a]
on listFromTuple(tpl)
items 2 thru -2 of (tpl as list)
end listFromTuple
 
-- lt :: Ord a => a -> a -> Bool
on lt(x)
script
on |λ|(y)
x < y
end |λ|
end script
end lt
 
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
 
Are initial and final nest formats equal? true
-- minimum :: Ord a => [a] -> a
</pre>
on minimum(xs)
set lng to length of xs
if lng < 1 then return missing value
set m to item 1 of xs
repeat with x in xs
set v to contents of x
if v < m then set m to v
end repeat
return m
end minimum
 
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
 
-- snd :: (a, b) -> b
on snd(tpl)
if class of tpl is record then
|2| of tpl
else
item 2 of tpl
end if
end snd
 
-- span :: (a -> Bool) -> [a] -> ([a], [a])
on span(f)
-- The longest (possibly empty) prefix of xs
-- that contains only elements satisfying p,
-- tupled with the remainder of xs.
-- span(p, xs) eq (takeWhile(p, xs), dropWhile(p, xs))
script
on |λ|(xs)
set lng to length of xs
set i to 0
tell mReturn(f)
repeat while i < lng and |λ|(item (i + 1) of xs)
set i to i + 1
end repeat
end tell
splitAt(i, xs)
end |λ|
end script
end span
 
 
-- splitAt :: Int -> [a] -> ([a], [a])
on splitAt(n, xs)
if n > 0 and n < length of xs then
if class of xs is text then
Tuple(items 1 thru n of xs as text, ¬
items (n + 1) thru -1 of xs as text)
else
Tuple(items 1 thru n of xs, items (n + 1) thru -1 of xs)
end if
else
if n < 1 then
Tuple({}, xs)
else
Tuple(xs, {})
end if
end if
end splitAt</lang>
{{Out}}
<pre>Outline:
 
The Rosetta stone
is a granodiorite stele
engraved
with Greek and Egyptian texts
in different scripts.
which, in the 19c, shed new light
on various homologies.
 
Forest from outline:
 
[["The Rosetta stone",[["is a granodiorite stele",[["engraved",[["with Greek and Egyptian texts",[]]]],["in different scripts.",[]]]],["which, in the 19c, shed new light",[["on various homologies.",[]]]]]]]
 
Nesting levels from forest:
 
[[0,"The Rosetta stone"],[1,"is a granodiorite stele"],[2,"engraved"],[3,"with Greek and Egyptian texts"],[2,"in different scripts."],[1,"which, in the 19c, shed new light"],[2,"on various homologies."]]
 
Forest rebuilt from nesting levels
 
[["The Rosetta stone",[["is a granodiorite stele",[["engraved",[["with Greek and Egyptian texts",[]]]],["in different scripts.",[]]]],["which, in the 19c, shed new light",[["on various homologies.",[]]]]]]]
 
Equality test:
 
(forestA = forestB) -> true</pre>
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
"fmt"
"io"
"os"
"strings"
)
Line 448 ⟶ 311:
}
 
func printNest(n nNode, level int, w io.Writer) {
if level == 0 {
fmt.PrintlnFprintln(w, "\n==Nest form==\n")
}
fmt.PrintfFprintf(w, "%s%s\n", strings.Repeat(" ", level), n.name)
for _, c := range n.children {
fmt.PrintfFprintf(w, "%s", strings.Repeat(" ", level+1))
printNest(c, level+1, w)
}
}
Line 474 ⟶ 337:
}
 
func printIndent(iNodes []iNode, w io.Writer) {
fmt.PrintlnFprintln(w, "\n==Indent form==\n")
for _, n := range iNodes {
fmt.PrintfFprintf(w, "%d %s\n", n.level, n.name)
}
}
Line 491 ⟶ 354:
n1 := nNode{"RosettaCode", nil}
n2 := nNode{"rocks", []nNode{{"code", nil}, {"comparison", nil}, {"wiki", nil}}}
n3 := nNode{"mocks", []nNode{{"golfingtrolling", nil}}}
n1.children = append(n1.children, n2, n3)
 
printNest(n1, 0)
var sb strings.Builder
printNest(n1, 0, &sb)
s1 := sb.String()
fmt.Print(s1)
 
var iNodes []iNode
toIndent(n1, 0, &iNodes)
printIndent(iNodes, os.Stdout)
 
var n nNode
toNest(iNodes, 0, 0, &n)
printNestsb.Reset(n, 0)
printNest(n, 0, &sb)
}</lang>
s2 := sb.String()
fmt.Print(s2)
 
fmt.Println("\nRound trip test satisfied? ", s1 == s2)
}</syntaxhighlight>
 
{{out}}
Line 512 ⟶ 386:
wiki
mocks
golfingtrolling
 
==Indent form==
Line 522 ⟶ 396:
2 wiki
1 mocks
2 trolling
2 golfing
 
==Nest form==
Line 532 ⟶ 406:
wiki
mocks
golfingtrolling
 
Round trip test satisfied? true
</pre>
 
=={{header|Haskell}}==
The task is all about the isomorphism between different representations of a nested list structure. Therefore the solution is given in terms of the isomorphisms.
Using the rose tree constructor in the standard Data.Tree module.
 
<syntaxhighlight lang="haskell">{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
Parses the initial tree from outline text, and writes out the flat
{-# LANGUAGE UndecidableSuperClasses #-}
and nested structures in a JSON format:
<lang haskell>{-# LANGUAGE OverloadedStringsTypeApplications #-}
 
import qualified Data.Text.Lazy.Encoding asList E(span)
import qualified Data.Text.Lazy.IO as T
import qualified Data.Text.Lazy as T
import Control.Arrow (first)
import Data.Char (isSpace)
import Data.Bool (bool)
import Data.Tree
import Data.Aeson
import Data.Aeson.Text
import Control.Arrow ((***))
 
-- A nested tree structure.
-- TREES <-> LIST OF LEVELS <-> TREES -----------------------
-- Using `Maybe` allows encoding several zero-level items
nestLevelsFromForest :: [Tree a] -> [(Int, a)]
-- or irregular lists (see test example)
nestLevelsFromForest xs =
data Nest a = Nest (Maybe a) [Nest a]
let go level node =
deriving Eq
(level, rootLabel node) : (subForest node >>= go (succ level))
in xs >>= go 0
 
instance Show a => Show (Nest a) where
forestFromNestLevels
show (Nest (Just a) []) = show a
:: Ord t
=>show [(t,Nest (Just a)] ->s) Forest= show a ++ show s
show (Nest Nothing []) = "\"\""
forestFromNestLevels pairs =
show (Nest Nothing s) = "\"\"" ++ show s
let go [] = []
go ((n, s):xs) =
uncurry (:) $ (Node s . go *** go) (span ((n <) . fst) xs)
in go pairs
 
-- An indented tree structure.
-- INITIAL PARSE TREE OF OUTLINE --------------------------
type Indent a = [(Int, a)]
nestLevelsFromLines xs =
 
let pairs = T.span isSpace <$> xs
-- class for isomorphic types
indentUnit =
class Iso b a => Iso a b foldrwhere
from (\x:: a -> b
 
let w = (T.length . fst) x
-- A bijection from nested form to indent form
in bool a w (w < a && 0 < w))
instance Iso (Nest a) (Indent a) where
maxBound
from = go pairs(-1)
where
in first (flip div indentUnit . T.length) <$> pairs
go n (Nest a t) =
case a of
Just a -> (n, a) : foldMap (go (n + 1)) t
Nothing -> foldMap (go (n + 1)) t
 
-- A bijection from indent form to nested form
instance Iso (Indent a) (Nest a) where
from = revNest . foldl add (Nest Nothing [])
where
add t (d,x) = go 0 t
where
go n (Nest a s) =
case compare n d of
EQ -> Nest a $ Nest (Just x) [] : s
LT -> case s of
h:t -> Nest a $ go (n+1) h : t
[] -> go n $ Nest a [Nest Nothing []]
GT -> go (n-1) $ Nest Nothing [Nest a s]
 
revNest (Nest a s) = Nest a (reverse $ revNest <$> s)
 
-- A bijection from indent form to a string
instance Iso (Indent String) String where
from = unlines . map process
where
process (d, s) = replicate (4*d) ' ' ++ s
 
-- A bijection from a string to indent form
instance Iso String (Indent String) where
from = map process . lines
where
process s = let (i, a) = span (== ' ') s
in (length i `div` 4, a)
 
-- A bijection from nest form to a string via indent form
instance Iso (Nest String) String where
from = from @(Indent String) . from
 
-- A bijection from a string to nest form via indent form
instance Iso String (Nest String) where
from = from @(Indent String) . from</syntaxhighlight>
 
Testing:
<syntaxhighlight lang="haskell">test = unlines
[ "RosettaCode"
, " rocks"
, " code"
, " comparison"
, " wiki"
, " mocks"
, " trolling"
, "Some lists"
, " may"
, " be"
, " irregular" ]
 
itest :: Indent String
itest = from test
 
ttest :: Nest String
ttest = from test</syntaxhighlight>
 
<pre>λ> mapM_ print itest
(0,"RosettaCode")
(1,"rocks")
(2,"code")
(2,"comparison")
(2,"wiki")
(1,"mocks")
(2,"trolling")
(0,"Some lists")
(3,"may")
(2,"be")
(1,"irregular")
 
λ> ttest
""["RosettaCode"["rocks"["code","comparison","wiki"],"mocks"["trolling"]],
"Some lists"[""[""["may"],"be"],"irregular"]]
 
λ> putStr $ from (from test :: Indent String)
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
Some lists
may
be
irregular
 
λ> putStr $ from (from test :: Nest String)
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
Some lists
may
be
irregular
 
λ> test == from (from test :: Nest String)
True
 
λ> test == from (from test :: Indent String)
True
 
λ> itest == from (from itest :: String)
True
 
λ> itest == from (from itest :: Nest String)
True
 
λ> ttest == from (from ttest :: String)
True
 
λ> ttest == from (from ttest :: Indent String)
True</pre>
 
 
And less satisfyingly and instructively – just relying a little passively on the existing Data.Tree,
we might also write something like:
 
<syntaxhighlight lang="haskell">import Data.Bifunctor (bimap, first)
import Data.Char (isSpace)
import Data.List (find)
import Data.Tree (Forest, Tree (..), drawTree)
 
-------- MAPPINGS BETWEEN INDENTED LINES AND TREES -------
-- DISPLAY OF JSON SERIALISATION --------------------------
showJSON
:: ToJSON a
=> a -> T.Text
showJSON = E.decodeUtf8 . encode . toJSON
 
forestFromNestLevels :: [(Int, String)] -> Forest String
-- TEST ---------------------------------------------------
forestFromNestLevels = go
forestA :: Forest T.Text
where
forestA = (forestFromNestLevels . nestLevelsFromLines) (T.lines outline)
go [] = []
go ((n, v) : xs) =
uncurry (:) $
bimap (Node v . go) go (span ((n <) . fst) xs)
 
nestLevelsindentLevelsFromLines :: [String] -> [(Int, T.TextString)]
indentLevelsFromLines xs =
nestLevels = nestLevelsFromForest forestA
let pairs = first length . span isSpace <$> xs
indentUnit = maybe 1 fst (find ((0 <) . fst) pairs)
in first (`div` indentUnit) <$> pairs
 
outlineFromForest ::
forestB :: [Tree T.Text]
(String -> String -> String) ->
forestB = forestFromNestLevels nestLevels
String ->
Forest String ->
String
outlineFromForest showRoot tabString forest =
let go indent node =
showRoot indent (rootLabel node) :
(subForest node >>= go ((<>) tabString indent))
in unlines $ forest >>= go ""
 
-------------------------- TESTS -------------------------
main :: IO ()
main = do
putStrLn "Tree representation parsed directly:\n"
mapM_
putStrLn $ drawTree $ Node "" nativeForest
T.putStrLn
[ "Initial parse tree from outline:\n"
, showJSON forestA
, "\nFlat list of nesting levels from parse tree:\n"
, showJSON nestLevels
, "\nTree rebuilt from nest levels:\n"
, showJSON forestB
]
putStrLn $
"\n\n(Reconstructed tree == parsed tree) -> " ++ show (forestA == forestB)
 
let levelPairs = indentLevelsFromLines test
outline :: T.Text
putStrLn "\n[(Level, Text)] list from lines:\n"
outline =
mapM_ print levelPairs
"RosettaCode\n\
 
\ rocks\n\
putStrLn "\n\nTrees from indented text:\n"
\ code\n\
let trees = forestFromNestLevels levelPairs
\ comparison\n\
putStrLn $ drawTree $ Node "" trees
\ wiki\n\
 
\ knocks\n\
putStrLn "Indented text from trees:\n"
\ golfing"</lang>
putStrLn $ outlineFromForest (<>) " " trees
 
test :: [String]
test =
[ "RosettaCode",
" rocks",
" code",
" comparison",
" wiki",
" mocks",
" trolling",
"Some lists",
" may",
" be",
" irregular"
]
 
nativeForest :: Forest String
nativeForest =
[ Node
"RosettaCode"
[ Node
"rocks"
[ Node "code" [],
Node "comparison" [],
Node "wiki" []
],
Node
"mocks"
[Node "trolling" []]
],
Node
"Some lists"
[ Node "may" [],
Node "be" [],
Node "irregular" []
]
]</syntaxhighlight>
{{Out}}
<pre>Tree representation parsed directly:
<pre>Initial parse tree from outline:
 
|
[["RosettaCode",[["rocks",[["code",[]],["comparison",[]],["wiki",[]]]],["knocks",[["golfing",[]]]]]]]
+- RosettaCode
| |
| +- rocks
| | |
| | +- code
| | |
| | +- comparison
| | |
| | `- wiki
| |
| `- mocks
| |
| `- trolling
|
`- Some lists
|
+- may
|
+- be
|
`- irregular
 
Flat list of nesting levels from parse tree:
 
[(Level, Text)] list from lines:
[[0,"RosettaCode"],[1,"rocks"],[2,"code"],[2,"comparison"],[2,"wiki"],[1,"knocks"],[2,"golfing"]]
 
(0,"RosettaCode")
Tree rebuilt from nest levels:
(1,"rocks")
(2,"code")
(2,"comparison")
(2,"wiki")
(1,"mocks")
(2,"trolling")
(0,"Some lists")
(3,"may")
(2,"be")
(1,"irregular")
 
[["RosettaCode",[["rocks",[["code",[]],["comparison",[]],["wiki",[]]]],["knocks",[["golfing",[]]]]]]]
 
Trees from indented text:
 
|
(Reconstructed tree == parsed tree) -> True</pre>
+- RosettaCode
| |
| +- rocks
| | |
| | +- code
| | |
| | +- comparison
| | |
| | `- wiki
| |
| `- mocks
| |
| `- trolling
|
`- Some lists
|
+- may
|
+- be
|
`- irregular
 
Indented text from trees:
=={{header|JavaScript}}==
Parses the initial tree from outline text, and writes out the flat and nested structures in a minimal JSON format:
<lang javascript>(() => {
'use strict';
 
RosettaCode
// main :: IO ()
rocks
const main = () => {
code
comparison
wiki
mocks
trolling
Some lists
may
be
irregular</pre>
 
=={{header|Java}}==
// (INDENT, STRING) PAIRS FROM OUTLINE ------------
<syntaxhighlight lang="java">
const
public class TreeDatastructures {
indentLevelTuplesA = indentLevelsFromLines(
lines(strOutlineB)
);
 
public static void main(String[] args) {
// LIST OF TREES FROM LIST OF (INDENT, STRING) PAIRS
String initialNested = """
const
Rosetta Code
forestA = forestFromIndentLevels(
....rocks
indentLevelTuplesA
);........code
........comparison
........wiki
....mocks
........trolling
""";
System.out.println(initialNested);
String indented = nestedToIndented(initialNested);
System.out.println(indented);
String finalNested = indentedToNested(indented);
System.out.println(finalNested);
 
final boolean equal = ( initialNested.compareTo(finalNested) == 0 );
// (INDENT, STRING) PAIRS FROM LIST OF TREES ------
System.out.println("initialNested = finalNested ? " + equal);
const
}
indentLevelTuplesB = indentLevelsFromForest(forestA);
private static String nestedToIndented(String nested) {
StringBuilder result = new StringBuilder();
for ( String line : nested.split(LINE_END) ) {
int index = 0;
while ( line.charAt(index) == '.' ) {
index += 1;
}
result.append(String.valueOf(index / 4) + " " + line.substring(index) + LINE_END);
}
return result.toString();
}
 
private static String indentedToNested(String indented) {
// LIST OF TREES FROM SECONDARY (INDENT, STRING) PAIRS
StringBuilder result = new StringBuilder();
const forestB = forestFromIndentLevels(
indentLevelTuplesB
for ( String line : indented.split(LINE_END) ) {
);
final int index = line.indexOf(' ');
final int level = Integer.valueOf(line.substring(0, index));
for ( int i = 0; i < level; i++ ) {
result.append("....");
}
result.append(line.substring(index + 1) + LINE_END);
}
return result.toString();
}
private static final String LINE_END = "\n";
 
}
// JSON OUTPUT OF FORESTS AND INDENT TUPLES -------
</syntaxhighlight>
{{ out }}
<pre>
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
 
0 Rosetta Code
console.log('Tree structure from outline:\n')
1 rocks
console.log(jsonFromForest(forestA));
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Rosetta Code
console.log('\n\nIndent levels from tree structure:\n')
....rocks
console.log(jsonFromIndentLevels(indentLevelTuplesB));
........code
........comparison
........wiki
....mocks
........trolling
 
initialNested = finalNested ? true
console.log('\nTree structure from indent levels:\n')
</pre>
console.log(jsonFromForest(forestB));
 
=={{header|jq}}==
console.log(
'''Adapted from [[#Wren|Wren]]'''
'(Reconstructed tree === parsed tree) -> ' +
{{works with|jq}}
Boolean(eq(forestA)(forestB))
'''Also works with gojq, the Go implementation of jq'''
);
};
 
<syntaxhighlight lang="jq">
// CONVERSIONS BETWEEN OUTLINES, TREES, AND (LEVEL, VALUE) PAIRS
# node of a nested representation
def NNode($name; $children): {$name, $children};
 
# node of an indented representation:
// indentLevelsFromLines :: [String] -> [(Int, String)]
def INode($level; $name): {$level, $name};
const indentLevelsFromLines = xs => {
const
indentTextPairs = xs.map(compose(
firstArrow(length), span(isSpace)
)),
indentUnit = minimum(indentTextPairs.flatMap(pair => {
const w = fst(pair);
return 0 < w ? [w] : [];
}));
return indentTextPairs.map(
firstArrow(flip(div)(indentUnit))
);
};
 
# Output: string representation of an NNode structure
// forestFromIndentLevels :: [(Int, String)] -> [Tree String]
def printNest:
const forestFromIndentLevels = tuples => {
. as $nested
const go = xs =>
# input: string so far
0 < xs.length ? (() => {
| def printNest($n; $level):
const [n, s] = Array.from(xs[0]);
if ($level == 0) then "\n==Nest form==\n\n" else . end
return uncurry(cons)(
| reduce ($n.children[], null) as $c ( . + "\((" " * splitArrow(compose(Node(s$level), go)// "")\(go$n.name)(\n";
if $c == null then span(compose(lt(n), fst))(.
else . + (" " * ($level + 1)) | printNest($c; $level + xs.slice(1)
end );
printNest($nested; 0);
)
);
})() : [];
return go(tuples);
};
 
# input: an INode structure
// indentLevelsFromForest :: [Tree a] -> [(Int, a)]
# output: the corresponding NNode structure
const indentLevelsFromForest = trees => {
def toNest:
const go = n => node => [
. as $in
[n, node.root]
| def toNest($iNodes; start; level):
]
{ i: .concat(node.nest.flatMap(go(1start + n))1),
n: (if (level == 0) then .name = $iNodes[0].name else . end)
return trees.flatMap(go(0));
};
| until ( (.i >= ($iNodes|length)) or .done;
if ($iNodes[.i].level == level + 1)
then .i as $i
| (NNode($iNodes[$i].name; []) | toNest($iNodes; $i; level+1)) as $c
| .n.children += [$c]
else if ($iNodes[.i].level <= level) then .done = true else . end
end
| .i += 1 )
| .n ;
NNode(""; []) | toNest($in; 0; 0);
 
# Output: string representation of an INode structure
// JSON RENDERING OF NESTED LINES AND (LEVEL, VALUE) PAIRS
def printIndent:
"\n==Indent form==\n\n"
+ reduce .[] as $n ("";
. + "\($n.level) \($n.name)\n") ;
 
# output: representation using INode
// jsonFromForest :: [Tree a] -> JSON String
def toIndent:
const jsonFromForest = trees =>
def toIndent($n; level):
JSON.stringify(
. + [INode(level; $n.name)]
nestedListsFromForest(trees),
+ reduce $n.children[] as $c null, 2([];
toIndent($c; level+1) );
. as $in
| [] | toIndent($in; 0);
 
 
### Example
// nestedListsFromForest :: [Tree a] -> NestedList a
const nestedListsFromForest = xs => {
const go = node => [node.root, node.nest.map(go)];
return xs.map(go);
};
 
def n: NNode(""; []);
// jsonFromIndentLevels :: [(Int, String)] -> JSON String
def n1: NNode("RosettaCode"; []);
const jsonFromIndentLevels = xs =>
def n2: NNode("rocks"; [NNode("code"; []), NNode("comparison"; []), NNode("wiki"; [])] );
JSON.stringify(
def n3: NNode("mocks"; [NNode("trolling"; [])]);
xs.map(x => Array.from(x)),
null, 2
);
 
def n123:
n1
| .children += [n2]
| .children += [n3];
 
### The task
// GENERIC FUNCTIONS ----------------------------
def nested:
n123
| printNest ;
 
def indented:
// Node :: a -> [Tree a] -> Tree a
n123
const Node = v => xs => ({
| toIndent
type: 'Node',
| printIndent;
root: v, // any type of value (consistent across tree)
nest: xs || []
});
 
def roundtrip:
// Tuple (,) :: a -> b -> (a, b)
n123
const Tuple = a => b => ({
| toIndent
type: 'Tuple',
| toNest
'0': a,
| printNest;
'1': b,
length: 2
});
 
def task:
// compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
nested as $nested
const compose = (...fs) =>
| roundtrip as $roundtrip
x => fs.reduceRight((a, f) => f(a), x);
| $nested, indented, $roundtrip,
"\nRound trip test satisfied? \($nested == $roundtrip)" ;
 
task
// cons :: a -> [a] -> [a]
</syntaxhighlight>
const cons = x =>
{{output}}
xs => [x].concat(xs)
As for [[#Wren|Wren]].
 
=={{header|Julia}}==
// div :: Int -> Int -> Int
<syntaxhighlight lang="julia">const nesttext = """
const div = x => y => Math.floor(x / y);
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
"""
 
function nesttoindent(txt)
// eq (==) :: Eq a => a -> a -> Bool
const eq = a => bret => {""
windent = gcd(length.([x.match for x in eachmatch(r"\s+", txt)]) .- 1)
const t = typeof a;
for lin in split(txt, "\n")
return t !== typeof b ? (
ret *= isempty(lin) ? "\n" : isspace(lin[1]) ?
false
replace(lin, r"\s+" => (s) -> "$(length(s)÷windent) ") * "\n" :
) : 'object' !== t ? (
'function'"0 !== t ? (" * lin * "\n"
end
a === b
return ret, " "^windent
) : a.toString() === b.toString()
end
) : (() => {
const kvs = Object.entries(a);
return kvs.length !== Object.keys(b).length ? (
false
) : kvs.every(([k, v]) => eq(v)(b[k]));
})();
};
 
function indenttonest(txt, indenttext)
// firstArrow :: (a -> b) -> ((a, c) -> (b, c))
ret = ""
const firstArrow = f => xy => Tuple(f(xy[0]))(
for lin in filter(x -> length(x) > 1, split(txt, "\n"))
xy[1]
(num, name) = split(lin, r"\s+", limit=2)
);
indentnum = parse(Int, num)
ret *= indentnum == 0 ? name * "\n" : indenttext^indentnum * name * "\n"
end
return ret
end
 
indenttext, itext = nesttoindent(nesttext)
// flip :: (a -> b -> c) -> b -> a -> c
restorednesttext = indenttonest(indenttext, itext)
const flip = f =>
1 < f.length ? (
(a, b) => f(b, a)
) : (x => y => f(y)(x));
 
println("Original:\n", nesttext, "\n")
// foldl1 :: (a -> a -> a) -> [a] -> a
println("Indent form:\n", indenttext, "\n")
const foldl1 = f => xs =>
println("Back to nest form:\n", restorednesttext, "\n")
1 < xs.length ? xs.slice(1)
println("original == restored: ", strip(nesttext) == strip(restorednesttext))
.reduce(uncurry(f), xs[0]) : xs[0];
</syntaxhighlight>{{out}}
<pre>
Original:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
// fst :: (a, b) -> a
const fst = tpl => tpl[0];
 
Indent form:
// isSpace :: Char -> Bool
0 RosettaCode
const isSpace = c => /\s/.test(c);
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
// Returns Infinity over objects without finite length.
// This enables zip and zipWith to choose the shorter
// argument when one is non-finite, like cycle, repeat etc
 
// length :: [a] -> Int
const length = xs =>
(Array.isArray(xs) || 'string' === typeof xs) ? (
xs.length
) : Infinity;
 
Back to nest form:
// lines :: String -> [String]
RosettaCode
const lines = s => s.split(/[\r\n]/);
rocks
code
comparison
wiki
mocks
trolling
 
// lt (<) :: Ord a => a -> a -> Bool
const lt = a => b => a < b;
 
original == restored: true
// minimum :: Ord a => [a] -> a
</pre>
const minimum = xs =>
0 < xs.length ? (
foldl1(a => x => x < a ? x : a)(xs)
) : undefined;
 
=={{header|Nim}}==
// showLog :: a -> IO ()
const showLog = (...args) =>
console.log(
args
.map(JSON.stringify)
.join(' -> ')
);
 
<syntaxhighlight lang="nim">import strformat, strutils
// span :: (a -> Bool) -> [a] -> ([a], [a])
const span = p => xs => {
const iLast = xs.length - 1;
return splitAt(
until(i => iLast < i || !p(xs[i]))(
succ
)(0)
)(xs);
};
 
// Compose a function (from a tuple to a tuple),
// (with separate transformations for fst and snd)
 
####################################################################################################
// splitArrow (***) :: (a -> b) -> (c -> d) -> ((a, c) -> (b, d))
# Nested representation of trees.
const splitArrow = f => g =>
# The tree is simply the first node.
tpl => Tuple(f(tpl[0]))(
g(tpl[1])
);
 
type
// splitAt :: Int -> [a] -> ([a], [a])
const splitAt = n => xs =>
Tuple(xs.slice(0, n))(
xs.slice(n)
);
 
NNode*[T] = ref object
// succ :: Enum a => a -> a
value*: T
const succ = x => 1 + x;
children*: seq[NNode[T]]
 
// uncurry :: (a -> b -> c) -> ((a, b) -> c)
const uncurry = f =>
function() {
const
args = Array.from(arguments),
a = 1 < args.length ? (
args
) : args[0];
return f(a[0])(a[1]);
};
 
proc newNNode*[T](value: T; children: varargs[NNode[T]]): NNode[T] =
// until :: (a -> Bool) -> (a -> a) -> a -> a
## Create a node.
const until = p => f => x => {
NNode[T](value: value, children: @children)
let v = x;
while (!p(v)) v = f(v);
return v;
};
 
// SAMPLE OUTLINES ------------------------------------
 
proc add*[T](node: NNode[T]; children: varargs[NNode[T]]) =
const strOutlineA = `Heilmeier catechism
## Add a list of chlidren to a node.
Objectives and benefits
node.children.add children
What are you trying to do?
Articulate your objectives using absolutely no jargon.
What are the problems you address ?
How is it done today,
and what are the limits of current practice?
What is your solution ?
What is new in your approach
and why do you think it will be successful?
Who cares? If you are successful, what difference will it make?
Costs
What are the risks?
How much will it cost?
How long will it take?
Indicators
What are the mid-term and final “exams” to check for success?`;
 
const strOutlineB = `Rosetta stone
is a granodiorite stele
engraved
with Greek and Egyptian texts
in different scripts.
which shed new light
on various homologies.`;
 
proc `$`*[T](node: NNode[T]; depth = 0): string =
// MAIN ---
## Return a string representation of a tree/node.
return main();
result = repeat(' ', 2 * depth) & $node.value & '\n'
})();</lang>
for child in node.children:
{{Out}}
result.add `$`(child, depth + 1)
<pre>Tree structure from outline:
 
[
[
"Rosetta stone",
[
[
"is a granodiorite stele",
[
[
"engraved",
[
[
"with Greek and Egyptian texts",
[]
]
]
],
[
"in different scripts.",
[]
]
]
],
[
"which shed new light",
[
[
"on various homologies.",
[]
]
]
]
]
]
]
 
####################################################################################################
Indent levels from tree structure:
# Indented representation of trees.
# The tree is described as the list of the nodes.
 
type
[
[
0,
"Rosetta stone"
],
[
1,
"is a granodiorite stele"
],
[
2,
"engraved"
],
[
3,
"with Greek and Egyptian texts"
],
[
2,
"in different scripts."
],
[
1,
"which shed new light"
],
[
2,
"on various homologies."
]
]
 
INode*[T] = object
Tree structure from indent levels:
value*: T
level*: Natural
 
ITree*[T] = seq[INode[T]]
[
 
[
 
"Rosetta stone",
proc initINode*[T](value: T; level: Natural): INode[T] =
[
## Return a new [node.
INode[T](value: value, level: level)
"is a granodiorite stele",
 
[
 
[
proc initItree*[T](value: T): ITree[T] =
"engraved",
## Return a new tree initialized with the first node (root node).
[
result = @[initINode(value, 0)]
[
 
"with Greek and Egyptian texts",
 
[]
proc add*[T](tree: var ITree[T]; nodes: varargs[INode[T]]) =
]
## Add a list of nodes to the tree.
for node in nodes:
if node.level - tree[^1].level > 1:
raise newException(ValueError, &"wrong level {node.level} in node {node.value}.")
tree.add node
 
 
proc `$`*[T](tree: ITree[T]): string =
## Return a string representation of a tree.
for node in tree:
result.add $node.level & ' ' & $node.value & '\n'
 
 
####################################################################################################
# Conversion between nested form and indented form.
 
proc toIndented*[T](node: NNode[T]): Itree[T] =
## Convert a tree in nested form to a tree in indented form.
 
proc addNode[T](tree: var Itree[T]; node: NNode[T]; level: Natural) =
## Add a node to the tree at the given level.
tree.add initINode(node.value, level)
for child in node.children:
tree.addNode(child, level + 1)
 
result.addNode(node, 0)
 
 
proc toNested*[T](tree: Itree[T]): NNode[T] =
## Convert a tree in indented form to a tree in nested form.
 
var stack: seq[NNode[T]] # Note that stack.len is equal to the current level.
var nnode = newNNode(tree[0].value) # Root.
for i in 1..tree.high:
let inode = tree[i]
if inode.level > stack.len:
# Child.
stack.add nnode
elif inode.level == stack.len:
# Sibling.
stack[^1].children.add nnode
else:
# Branch terminated.
while inode.level < stack.len:
stack[^1].children.add nnode
nnode = stack.pop()
stack[^1].children.add nnode
 
nnode = newNNode(inode.value)
 
# Empty the stack.
while stack.len > 0:
stack[^1].children.add nnode
nnode = stack.pop()
 
result = nnode
 
 
#———————————————————————————————————————————————————————————————————————————————————————————————————
 
when isMainModule:
 
echo "Displaying tree built using nested structure:"
let nestedTree = newNNode("RosettaCode")
let rocks = newNNode("rocks")
rocks.add newNNode("code"), newNNode("comparison"), newNNode("wiki")
let mocks = newNNode("mocks", newNNode("trolling"))
nestedTree.add rocks, mocks
echo nestedTree
 
echo "Displaying tree converted to indented structure:"
let indentedTree = nestedTree.toIndented
echo indentedTree
 
echo "Displaying tree converted back to nested structure:"
echo indentedTree.toNested
 
echo "Are they equal? ", if $nestedTree == $indentedTree.toNested: "yes" else: "no"</syntaxhighlight>
 
{{out}}
<pre>Displaying tree built using nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Displaying tree converted to indented structure:
0 RosettaCode
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Displaying tree converted back to nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Are they equal? yes</pre>
 
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
{$zerobasedstrings}
function NestedToIndented(nested: string): string;
begin
var lst := new List<string>;
foreach var line in Regex.Split(nested,NewLine) do
begin
var ind := Regex.Match(line,'[^\.]').Index;
lst.Add($'{ind div 4} {line[ind:]}');
end;
Result := lst.JoinToString(NewLine);
end;
 
function IndentedToNested(indented: string): string;
begin
var lst := new List<string>;
foreach var line in Regex.Split(indented,NewLine) do
begin
var ind := line.IndexOf(' ');
var level := line[:ind].ToInteger;
lst.Add((level*4) * '.' + line[ind+1:]);
end;
Result := lst.JoinToString(NewLine);
end;
 
begin
var initialNested := '''
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
''';
Writeln(initialNested,NewLine);
var indented := NestedToIndented(initialNested);
Writeln(indented,NewLine);
var nested := IndentedToNested(indented);
Writeln(nested,NewLine);
Writeln($'Initial = Restored: {initialNested = nested}');
end.
</syntaxhighlight>
{{ out }}
<pre>
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
 
0 Rosetta Code
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
 
Initial = Restored: True
</pre>
 
 
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
use JSON;
use Data::Printer;
 
my $trees = <<~END;
RosettaCode
encourages
code
diversity
comparison
discourages
golfing
trolling
emphasising execution speed
code-golf.io
encourages
golfing
discourages
comparison
END
 
my $level = ' ';
sub nested_to_indent { shift =~ s#^($level*)# ($1 ? length($1)/length $level : 0) . ' ' #egmr }
sub indent_to_nested { shift =~ s#^(\d+)\s*# $level x $1 #egmr }
 
say my $indent = nested_to_indent $trees;
my $nest = indent_to_nested $indent;
 
use Test::More;
is($trees, $nest, 'Round-trip');
done_testing();
 
# Import outline paragraph into native data structure
sub import {
my($trees) = @_;
my $level = ' ';
my $forest;
my $last = -999;
 
for my $branch (split /\n/, $trees) {
$branch =~ m/(($level*))*/;
my $this = $1 ? length($1)/length($level) : 0;
$forest .= do {
if ($this gt $last) { '[' . trim_and_quote($branch) }
elsif ($this lt $last) { ']'x($last-$this).',' . trim_and_quote($branch) }
else { trim_and_quote($branch) }
};
$last = $this;
}
sub trim_and_quote { shift =~ s/^\s*(.*\S)\s*$/"$1",/r }
 
eval $forest . ']' x (1+$last);
}
 
my $forest = import $trees;
say "Native data structure:\n" . np $forest;
say "\nJSON:\n" . encode_json($forest);</syntaxhighlight>
{{out}}
<pre>RosettaCode
1 encourages
2 code
3 diversity
3 comparison
1 discourages
2 golfing
2 trolling
2 emphasising execution speed
code-golf.io
1 encourages
2 golfing
1 discourages
2 comparison
 
ok 1 - Round-trip
1..1
 
Native data structure:
\ [
[0] "RosettaCode",
[1] [
[0] "encourages",
[1] [
[0] "code",
[1] [
[0] "diversity",
[1] "comparison"
]
],
[2] ["discourages",
[3] "in different scripts.",[
[0] "golfing",
[1] "trolling",
[2] "emphasising execution speed"
]
],
[2] ["code-golf.io",
[3] [
"which shed new light",
[0] "encourages",
[1] [
[0] "on various homologies.golfing",
[],
[2] ]"discourages",
[3] [
[0] "comparison"
]
]
]
]
]
 
(Reconstructed tree === parsed tree) -> true</pre>
JSON:
["RosettaCode",["encourages",["code",["diversity","comparison"]],"discourages",["golfing","trolling","emphasising execution speed"]],"code-golf.io",["encourages",["golfing"],"discourages",["comparison"]]]</pre>
 
=={{header|Phix}}==
{{libheader|Phix/basics}}
The standard Phix sequence is perfect for handling all of these kinds of structures.
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">function</span> <span style="color: #000000;">text_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">plain_text</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plain_text</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">no_empty</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">parents</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">line</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim_tail</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">text</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim_head</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">indent</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">line</span><span style="color: #0000FF;">)-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- remove any completed parents</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">parents</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">parents</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">parents</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">parents</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- append potential new parent</span>
<span style="color: #000000;">parents</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">indent</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">depth</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">parents</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">lines</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">depth</span><span style="color: #0000FF;">,</span><span style="color: #000000;">text</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">lines</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">indent_to_nested</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">lvl</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">text</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">lvl</span><span style="color: #0000FF;"><</span><span style="color: #000000;">level</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">children</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indent_to_nested</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">text</span><span style="color: #0000FF;">,</span><span style="color: #000000;">children</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nested_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">nested</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nested</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">string</span> <span style="color: #000000;">text</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">children</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nested</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">level</span><span style="color: #0000FF;">,</span><span style="color: #000000;">text</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">nested_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">children</span><span style="color: #0000FF;">,</span><span style="color: #000000;">level</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">text</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
RosettaCode
encourages
code
diversity
comparison
discourages
emphasising execution speed
code-golf.io
encourages
golfing
discourages
comparison"""</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">indent</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">text_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">nested</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indent_to_nested</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">n2ichk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nested_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nested</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Indent form:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nNested form:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nested</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nNested to indent:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n2ichk</span><span style="color: #0000FF;">==</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"same"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"***ERROR***"</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Indent form:
{{1, `RosettaCode`},
{2, `encourages`},
{3, `code`},
{4, `diversity`},
{4, `comparison`},
{2, `discourages`},
{3, `emphasising execution speed`},
{1, `code-golf.io`},
{2, `encourages`},
{3, `golfing`},
{2, `discourages`},
{3, `comparison`}}
 
Nested form:
{{`RosettaCode`,
{{`encourages`,
{{`code`,
{{`diversity`,
{}},
{`comparison`,
{}}}}}},
{`discourages`,
{{`emphasising execution speed`,
{}}}}}},
{`code-golf.io`,
{{`encourages`,
{{`golfing`,
{}}}},
{`discourages`,
{{`comparison`,
{}}}}}}}
 
Nested to indent:same
</pre>
You can also strictly enforce these structures, which is obviously useful for debugging.<br>
Admittedly this is somewhat more tedious, but at the same time infinitely more flexible and powerful than a "plain old struct".
<!--<syntaxhighlight lang="phix">-->
<span style="color: #008080;">type</span> <span style="color: #000000;">indent_struct</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">oi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">2</span>
<span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #004080;">integer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">type</span>
<span style="color: #008080;">type</span> <span style="color: #000000;">nested_struct</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">oi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">or</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">2</span>
<span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">or</span> <span style="color: #008080;">not</span> <span style="color: #000000;">nested_struct</span><span style="color: #0000FF;">(</span><span style="color: #000000;">oi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">type</span>
<span style="color: #000080;font-style:italic;">-- and as above except:</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">indent_to_nested</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indent_struct</span> <span style="color: #000000;">indent</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nested_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nested_struct</span> <span style="color: #000000;">nested</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- also make the output sequences better typed:</span>
<span style="color: #000000;">indent_struct</span> <span style="color: #000000;">indent</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">text_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">text</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nested_struct</span> <span style="color: #000000;">nested</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indent_to_nested</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">indent_struct</span> <span style="color: #000000;">r2ichk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nested_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nested</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
 
=={{header|Python}}==
===Procedural===
Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage.
 
<langsyntaxhighlight lang="python">from pprint import pprint as pp
from collections import namedtuple
 
def to_indent(node, depth=0, flat=None):
Line 1,066 ⟶ 1,535:
print('Start Nest format:')
nest = ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]),
('mocks', [('golfingtrolling', [])])])
pp(nest, width=25)
 
Line 1,078 ⟶ 1,547:
 
if nest != as_nest:
print("Whoops round-trip issues")</langsyntaxhighlight>
 
{{out}}
Line 1,088 ⟶ 1,557:
('wiki', [])]),
('mocks',
[('golfingtrolling', [])])])
 
... To Indent format:
Line 1,097 ⟶ 1,566:
(2, 'wiki'),
(1, 'mocks'),
(2, 'golfingtrolling')]
 
... To Nest format:
Line 1,106 ⟶ 1,575:
('wiki', [])]),
('mocks',
[('golfingtrolling', [])])])</pre>
 
===Functional={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2020.08.1}}
Code golf is a entertaining passtime, even if it isn't appropriate for this site. To a large extent, I agree with [[User:Hout|Hout]], I am not really on board with mocking anybody, especially espousing it as an official RosettaCode position. So, feel free to mark this incorrect.
 
<syntaxhighlight lang="raku" line>#`(
Using a Node constructor with '''root''' and '''nest''' keys for the value and sub-forest of each tree node, and serialising both trees and nesting-level lists to JSON-compatible formats.
Sort of vague as to what we are trying to accomplish here. If we are just
trying to transform from one format to another, probably easiest to just
perform string manipulations.
)
 
my $level = ' ';
Functional composition, as an alternative to '''.append()''' and '''.pop()''' mutations.
 
my $trees = q:to/END/;
(Initial tree constructed as the parse of an outline text)
RosettaCode
encourages
code
diversity
comparison
discourages
golfing
trolling
emphasising execution speed
code-golf.io
encourages
golfing
discourages
comparison
END
 
sub nested-to-indent { $^str.subst: / ^^ ($($level))* /, -> $/ { "{+$0} " }, :g }
{{Works with|Python|3.7}}
sub indent-to-nested { $^str.subst: / ^^ (\d+) \s* /, -> $/ { "{$level x +$0}" }, :g }
<lang python>'''Tree data structures'''
 
say $trees;
from itertools import chain, takewhile
say my $indent = $trees.&nested-to-indent;
import json
say my $nest = $indent.&indent-to-nested;
 
use Test;
is($trees, $nest, 'Round-trip equals original');
 
#`(
# Node :: a -> [Tree a] -> Tree a
If, on the other hand, we want perform more complex transformations; better to
def Node(v):
load it into a native data structure which will then allow us to manipulate it
'''Constructor for a Tree node which connects a
however we like.
value of some kind to a list of zero or
)
more child trees.
'''
return lambda xs: {'type': 'Tree', 'root': v, 'nest': xs}
 
# Import outline paragraph into native data structure
sub import (Str $trees, $level = ' ') {
my $forest;
my $last = -Inf;
 
for $trees.lines -> $branch {
# forestFromNestLevels :: [(Int, a)] -> [Tree a]
$branch ~~ / ($($level))* /;
def forestFromNestLevels(tuples):
my $this = +$0;
'''A list of trees derived from a list of values paired
$forest ~= do {
with integers giving their levels of indentation.
given $this cmp $last {
'''
when More { "\['{esc $branch.trim}', " }
def go(xs):
when Same { "'{esc $branch.trim}', " }
if xs:
when Less { "{']' x $last - $this}, '{esc $branch.trim}', " }
(intIndent, v) = xs[0]
(firstTreeLines, rest) = span(}
}
lambda x: intIndent < x[0]
$last = )(xs[1:])$this;
}
return [Node(v)(go(firstTreeLines))] + go(rest)
else:
return []
return go(tuples)
 
sub esc { $^s.subst( /(<['\\]>)/, -> $/ { "\\$0" }, :g) }
 
$forest ~= ']' x 1 + $last;
# nestLevelsFromForest :: [Tree a] -> [(Int, a)]
$forest.EVAL;
def nestLevelsFromForest(xs):
}
'''A flat list of (nest level, value) tuples,
representing a series of trees.
'''
def go(level):
return lambda node: [(level, node['root'])] + concatMap(
go(1 + level)
)(node['nest'])
return concatMap(go(0))(xs)
 
my $forest = import $trees;
 
say "\nNative data structure:\n", $forest.raku;
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Conversion from trees to flat lists of nest levels,
and back again, with each stage shown as a JSON
string.
'''
forestA = forestFromNestLevels(
indentLevelsFromLines(OUTLINE.splitlines())
)
nestLevels = nestLevelsFromForest(forestA)
forestB = forestFromNestLevels(nestLevels)
 
{
for x in [
use JSON::Fast;
'Parse tree from outline text:\n',
say "\nJSON:\n", $forest.&to-json;
forestJSON(forestA),
}
 
{
'\nNesting level list from tree:\n',
use YAML;
json.dumps(nestLevels, indent=2),
say "\nYAML:\n", $forest.&dump;
}</syntaxhighlight>
{{out}}
<pre>RosettaCode
encourages
code
diversity
comparison
discourages
golfing
trolling
emphasising execution speed
code-golf.io
encourages
golfing
discourages
comparison
 
0 RosettaCode
'\nTree rebuilt from nesting level list:\n',
1 encourages
forestJSON(forestB),
2 code
]:
3 diversity
print(x)
3 comparison
print(
1 discourages
'(Reconstructed forest == parsed forest) -> ' +
2 golfing
str(forestA == forestB)
2 trolling
)
2 emphasising execution speed
0 code-golf.io
1 encourages
2 golfing
1 discourages
2 comparison
 
RosettaCode
encourages
code
diversity
comparison
discourages
golfing
trolling
emphasising execution speed
code-golf.io
encourages
golfing
discourages
comparison
 
ok 1 - Round-trip equals original
# INITIAL TREE FROM PARSE OF OUTLINE TEXT -----------------
 
Native data structure:
# indentLevelsFromLines :: [String] -> [(Int, String)]
$["RosettaCode", ["encourages", ["code", ["diversity", "comparison"]], "discourages", ["golfing", "trolling", "emphasising execution speed"]], "code-golf.io", ["encourages", ["golfing"], "discourages", ["comparison"]]]
def indentLevelsFromLines(xs):
 
'''Each input line stripped of leading
JSON:
white space, and tupled with a preceding integer
[
giving its level of indentation from 0 upwards.
"RosettaCode",
'''
[
indentTextPairs = [
"encourages",
(n, s[n:]) for (n, s)
[
in ((len(list(takewhile(isSpace, x))), x) for x in xs)
"code",
[
"diversity",
"comparison"
]
],
"discourages",
[
"golfing",
"trolling",
"emphasising execution speed"
]
],
indentUnit = min(concatMap(
"code-golf.io",
lambda x: [x[0]] if x[0] else []
[
)(indentTextPairs))
return ["encourages",
[
(x[0] // indentUnit, x[1])
"golfing"
for x in indentTextPairs
],
"discourages",
[
"comparison"
]
]
]
 
YAML:
---
- RosettaCode
- - encourages
- - code
- - diversity
- comparison
- discourages
- - golfing
- trolling
- emphasising execution speed
- code-golf.io
- - encourages
- - golfing
- discourages
- - comparison
...</pre>
 
=={{header|Wren}}==
# JSON SERIALISATION --------------------------------------
{{trans|Go}}
{{libheader|Wren-dynamic}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./dynamic" for Struct
import "./fmt" for Fmt
 
var NNode = Struct.create("NNode", ["name", "children"])
# forestJSON :: [Tree a] -> JSON String
var INode = Struct.create("INode", ["level", "name"])
def forestJSON(trees):
'''A simple JSON serialisation of a list of trees, with
each tree node represented as a [value, nodes] pair.
'''
return json.dumps(
forestAsNestedPairs(trees),
indent=2
)
 
var sw = ""
 
var printNest // recursive
# forestAsNestedPairs :: [Tree a] -> NestedPair [(a, [NestedPair])]
printNest = Fn.new { |n, level|
def forestAsNestedPairs(xs):
if (level == 0) sw = sw + "\n==Nest form==\n\n"
'''A simple nested pair representation of a tree.'''
sw = sw + Fmt.swrite("$0s$s\n", " " * level, n.name)
def go(node):
for (c in n.children) {
return [node['root'], [go(x) for x in node['nest']]]
return [go sw = sw + (x)" for x" in* xs](level + 1))
printNest.call(c, level+1)
}
}
 
var toNest // recursive
toNest = Fn.new { |iNodes, start, level, n|
if (level == 0) n.name = iNodes[0].name
var i = start + 1
while (i < iNodes.count) {
if (iNodes[i].level == level + 1) {
var c = NNode.new(iNodes[i].name, [])
toNest.call(iNodes, i, level+1, c)
n.children.add(c)
} else if (iNodes[i].level <= level) return
i = i + 1
}
}
 
var printIndent = Fn.new { |iNodes|
# GENERIC -------------------------------------------------
sw = sw + "\n==Indent form==\n\n"
for (n in iNodes) sw = sw + Fmt.swrite("$d $s\n", n.level, n.name)
}
 
var toIndent // recursive
# concatMap :: (a -> [b]) -> [a] -> [b]
toIndent = Fn.new { |n, level, iNodes|
def concatMap(f):
iNodes.add(INode.new(level, n.name))
'''A concatenated list or string over which a function f
for (c in n.children) toIndent.call(c, level+1, iNodes)
has been mapped.
}
The list monad can be derived by using an (a -> [b])
function which wraps its output in a list (using an
empty list to represent computational failure).
'''
return lambda xs: (''.join if isinstance(xs, str) else list)(
chain.from_iterable(map(f, xs))
)
 
var n1 = NNode.new("RosettaCode", [])
var n2 = NNode.new("rocks", [NNode.new("code", []), NNode.new("comparison", []), NNode.new("wiki", [])])
var n3 = NNode.new("mocks", [NNode.new("trolling", [])])
n1.children.add(n2)
n1.children.add(n3)
 
printNest.call(n1, 0)
# isSpace :: Char -> Bool
var s1 = sw
# isSpace :: String -> Bool
System.print(s1)
def isSpace(s):
'''True if s is not empty, and
contains only white space.
'''
return s.isspace()
 
var iNodes = []
toIndent.call(n1, 0, iNodes)
sw = ""
printIndent.call(iNodes)
System.print(sw)
 
var n = NNode.new("", [])
# span :: (a -> Bool) -> [a] -> ([a], [a])
toNest.call(iNodes, 0, 0, n)
def span(p):
sw = ""
'''The longest (possibly empty) prefix of xs
printNest.call(n, 0)
that contains only elements satisfying p,
var s2 = sw
tupled with the remainder of xs.
System.print(s2)
span p xs is equivalent to (takeWhile p xs, dropWhile p xs).
'''
def go(xs):
prefix = list(takewhile(p, xs))
return (prefix, xs[len(prefix):])
return lambda xs: go(xs)
 
System.print("\nRound trip test satisfied? %(s1 == s2)")</syntaxhighlight>
 
{{out}}
# MAIN ---
<pre>
if __name__ == '__main__':
==Nest form==
OUTLINE = '''Rosetta stone
is a granodiorite stele
engraved
with Greek and Egyptian texts
in different scripts.
which shed new light
on various homologies.'''
 
RosettaCode
main()</lang>
rocks
{{Out}}
code
<pre>Parse tree from outline text:
comparison
wiki
mocks
trolling
 
[
[
"Rosetta stone",
[
[
"is a granodiorite stele",
[
[
"engraved",
[
[
"with Greek and Egyptian texts",
[]
]
]
],
[
"in different scripts.",
[]
]
]
],
[
"which shed new light",
[
[
"on various homologies.",
[]
]
]
]
]
]
]
 
==Indent form==
Nesting level list from tree:
 
0 RosettaCode
[
1 rocks
[
2 code
0,
2 comparison
"Rosetta stone"
2 wiki
],
1 mocks
[
2 trolling
1,
"is a granodiorite stele"
],
[
2,
"engraved"
],
[
3,
"with Greek and Egyptian texts"
],
[
2,
"in different scripts."
],
[
1,
"which shed new light"
],
[
2,
"on various homologies."
]
]
 
Tree rebuilt from nesting level list:
 
==Nest form==
[
 
[
RosettaCode
"Rosetta stone",
[rocks
[ code
"is a granodiorite stele",comparison
[wiki
[mocks
"engraved",trolling
 
[
 
[
Round trip test satisfied? true
"with Greek and Egyptian texts",
</pre>
[]
 
]
=={{header|zkl}}==
]
<syntaxhighlight lang="zkl">fcn nestToIndent(nestTree){
],
fcn(out,node,level){
[
out.append(List(level,node[0])); // (n,name) or ("..",name)
"in different scripts.",
if(node.len()>1){ // (name children), (name, (tree))
[]
level+=1;
]
foreach child in (node[1,*]){
]
if(String.isType(child)) out.append(List(level,child));
],
else self.fcn(out,child,level)
[
}
"which shed new light",
[}
[out
}(List(),nestTree,0)
"on various homologies.",
}
[]
fcn nestToString(nestTree,dot="."){
]
fcn(out,dot,node,level){
]
out.writeln(dot*level,node[0]); // (name)
]
if(node.len()>1){ // (name children), (name, (tree))
]
level+=1;
]
foreach child in (node[1,*]){
]
if(String.isType(child)) out.writeln(dot*level,child);
(Reconstructed forest == parsed forest) -> True</pre>
else self.fcn(out,dot,child,level)
}
}
out
}(Data(),dot,nestTree,0).text
}
 
fcn indentToNest(iTree,depth=0,nTree=List()){
while(iTree){ // (n,name)
d, name := iTree[0];
if(d==depth){
nTree.append(name);
iTree.pop(0);
}
else if(d>depth){ // assume can't skip levels down
if(nTree.len()>1 and not List.isType((nm:=nTree[-1]))){
nTree[-1]=(children:=List(nm));
indentToNest(iTree,d,children);
}else{
nTree.append(children:=List(name));
iTree.pop(0);
indentToNest(iTree,d+1,children);
}
}
else break; // d<depth
}
return(nTree)
}
fcn indentToString(indentTree){ indentTree.apply("concat"," ").concat("\n") }</syntaxhighlight>
<syntaxhighlight lang="zkl">tree:=L("RosettaCode",
L("rocks","code","comparison","wiki"),
L("mocks","golfing") );
 
println("Nest tree internal format:\n",tree.toString(*,*));
println("Formated:\n",nestToString(tree));
 
indentTree:=nestToIndent(tree);
println("To indent format:\n",indentToString(indentTree));
 
nestTree:=indentToNest(indentTree);
println("\nIndent to nested format:\n",nestTree);
println("Is this tree the same as what we started with? ",nestTree==tree);</syntaxhighlight>
{{out}}
<pre>
Nest tree internal format:
L("RosettaCode",L("rocks","code","comparison","wiki"),L("mocks","golfing"))
Formated:
RosettaCode
.rocks
..code
..comparison
..wiki
.mocks
..golfing
 
To indent format:
0 RosettaCode
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 golfing
 
Indent to nested format:
L("RosettaCode",L("rocks","code","comparison","wiki"),L("mocks","golfing"))
Is this tree the same as what we started with? True
</pre>
I'm choosing to only allow one root per tree/forest so the Raku example is coded differently:
<syntaxhighlight lang="zkl">rakutrees:=L(
L("RosettaCode",
L("encourages",
L("code",
"diversity","comparison")),
L("discourages",
"golfing","trolling","emphasising execution speed"),
),
L("code-golf.io",
L("encourages","golfing"),
L("discourages","comparison"),
)
);
println(rakutrees.apply(nestToString).concat());
iTrees := rakutrees.apply(nestToIndent);
println(iTrees.apply(indentToString).concat("\n"));
(iTrees.apply(indentToNest)==rakutrees).println();</syntaxhighlight>
{{out}}
<pre style="height:40ex">
RosettaCode
encourages
code
diversity
comparison
discourages
golfing
trolling
emphasising execution speed
code-golf.io
encourages
golfing
discourages
comparison
 
0 RosettaCode
1 encourages
2 code
3 diversity
3 comparison
1 discourages
2 golfing
2 trolling
2 emphasising execution speed
0 code-golf.io
1 encourages
2 golfing
1 discourages
2 comparison
True
</pre>
Miks1965
26

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/294503...364434"