Tree datastructures: Difference between revisions
m (→{{header|Haskell}}: Tidied one function.) |
(New post.) |
||
(43 intermediate revisions by 13 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
The following shows a tree of data with nesting denoted by visual levels of indentation: |
The following shows a tree of data with nesting denoted by visual levels of indentation: |
||
<pre>RosettaCode |
<pre>RosettaCode |
||
Line 7: | Line 7: | ||
wiki |
wiki |
||
mocks |
mocks |
||
trolling</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'''. |
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: | Line 34: | ||
;Note: |
;Note: |
||
* It's all about showing aspects of the contrasting datastructures as they hold the tree. |
* 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. |
* Comparing nested datastructures is secondary - saving formatted output as a string then a string compare would suffice for this task, if its easier. |
||
<br> |
<br> |
||
Line 40: | Line 39: | ||
Show all output on this page. |
Show all output on this page. |
||
=={{header| |
=={{header|11l}}== |
||
{{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) -> N |
|||
@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 |
|||
stack.append(nnode) |
|||
E I inode.level == stack.len |
|||
stack.last.children.append(nnode) |
|||
bool(a, n, n < a and 0 < n) |
|||
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) |
|||
return children_.back(); |
|||
} |
|||
set acc to acc & (|λ|(item i of xs, i, xs)) |
|||
void print(std::ostream& out) const { |
|||
end repeat |
|||
print(out, 0); |
|||
end tell |
|||
} |
|||
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 |
|||
from_nest(n, 0); |
|||
} |
|||
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 |λ| |
|||
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) |
|||
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 |
|||
rocks |
|||
code |
|||
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} |
|||
comparison |
|||
wiki |
|||
mocks |
|||
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 |
|||
Are initial and final nest formats equal? true |
|||
-- map :: (a -> b) -> [a] -> [b] |
|||
</pre> |
|||
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 |
|||
-- minimum :: Ord a => [a] -> a |
|||
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}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
"fmt" |
"fmt" |
||
"io" |
|||
"os" |
|||
"strings" |
"strings" |
||
) |
) |
||
Line 448: | Line 311: | ||
} |
} |
||
func printNest(n nNode, level int) { |
func printNest(n nNode, level int, w io.Writer) { |
||
if level == 0 { |
if level == 0 { |
||
fmt. |
fmt.Fprintln(w, "\n==Nest form==\n") |
||
} |
} |
||
fmt. |
fmt.Fprintf(w, "%s%s\n", strings.Repeat(" ", level), n.name) |
||
for _, c := range n.children { |
for _, c := range n.children { |
||
fmt. |
fmt.Fprintf(w, "%s", strings.Repeat(" ", level+1)) |
||
printNest(c, level+1) |
printNest(c, level+1, w) |
||
} |
} |
||
} |
} |
||
Line 474: | Line 337: | ||
} |
} |
||
func printIndent(iNodes []iNode) { |
func printIndent(iNodes []iNode, w io.Writer) { |
||
fmt. |
fmt.Fprintln(w, "\n==Indent form==\n") |
||
for _, n := range iNodes { |
for _, n := range iNodes { |
||
fmt. |
fmt.Fprintf(w, "%d %s\n", n.level, n.name) |
||
} |
} |
||
} |
} |
||
Line 491: | Line 354: | ||
n1 := nNode{"RosettaCode", nil} |
n1 := nNode{"RosettaCode", nil} |
||
n2 := nNode{"rocks", []nNode{{"code", nil}, {"comparison", nil}, {"wiki", nil}}} |
n2 := nNode{"rocks", []nNode{{"code", nil}, {"comparison", nil}, {"wiki", nil}}} |
||
n3 := nNode{"mocks", []nNode{{" |
n3 := nNode{"mocks", []nNode{{"trolling", nil}}} |
||
n1.children = append(n1.children, n2, n3) |
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 |
var iNodes []iNode |
||
toIndent(n1, 0, &iNodes) |
toIndent(n1, 0, &iNodes) |
||
printIndent(iNodes) |
printIndent(iNodes, os.Stdout) |
||
var n nNode |
var n nNode |
||
toNest(iNodes, 0, 0, &n) |
toNest(iNodes, 0, 0, &n) |
||
sb.Reset() |
|||
printNest(n, 0, &sb) |
|||
}</lang> |
|||
s2 := sb.String() |
|||
fmt.Print(s2) |
|||
fmt.Println("\nRound trip test satisfied? ", s1 == s2) |
|||
}</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
Line 512: | Line 386: | ||
wiki |
wiki |
||
mocks |
mocks |
||
trolling |
|||
==Indent form== |
==Indent form== |
||
Line 522: | Line 396: | ||
2 wiki |
2 wiki |
||
1 mocks |
1 mocks |
||
2 trolling |
|||
2 golfing |
|||
==Nest form== |
==Nest form== |
||
Line 532: | Line 406: | ||
wiki |
wiki |
||
mocks |
mocks |
||
trolling |
|||
Round trip test satisfied? true |
|||
</pre> |
</pre> |
||
=={{header|Haskell}}== |
=={{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: |
|||
{-# LANGUAGE TypeApplications #-} |
|||
import |
import Data.List (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 (Nest (Just a) s) = 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 |
|||
indentUnit = |
|||
foldr |
|||
(\x a -> |
|||
let w = (T.length . fst) x |
|||
in bool a w (w < a && 0 < w)) |
|||
maxBound |
|||
pairs |
|||
in first (flip div indentUnit . T.length) <$> pairs |
|||
-- class for isomorphic types |
|||
-- DISPLAY OF JSON SERIALISATION -------------------------- |
|||
class Iso b a => Iso a b where |
|||
showJSON |
|||
:: |
from :: a -> b |
||
=> a -> T.Text |
|||
showJSON = E.decodeUtf8 . encode . toJSON |
|||
-- A bijection from nested form to indent form |
|||
-- TEST --------------------------------------------------- |
|||
instance Iso (Nest a) (Indent a) where |
|||
forestA :: Forest T.Text |
|||
from = go (-1) |
|||
forestA = (forestFromNestLevels . nestLevelsFromLines) (T.lines outline) |
|||
where |
|||
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 |
|||
nestLevels :: [(Int, T.Text)] |
|||
instance Iso (Indent a) (Nest a) where |
|||
nestLevels = nestLevelsFromForest forestA |
|||
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) |
|||
forestB :: [Tree T.Text] |
|||
forestB = forestFromNestLevels nestLevels |
|||
-- 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 ------- |
|||
forestFromNestLevels :: [(Int, String)] -> Forest String |
|||
forestFromNestLevels = go |
|||
where |
|||
go [] = [] |
|||
go ((n, v) : xs) = |
|||
uncurry (:) $ |
|||
bimap (Node v . go) go (span ((n <) . fst) xs) |
|||
indentLevelsFromLines :: [String] -> [(Int, String)] |
|||
indentLevelsFromLines xs = |
|||
let pairs = first length . span isSpace <$> xs |
|||
indentUnit = maybe 1 fst (find ((0 <) . fst) pairs) |
|||
in first (`div` indentUnit) <$> pairs |
|||
outlineFromForest :: |
|||
(String -> String -> String) -> |
|||
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 :: IO () |
||
main = do |
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}} |
{{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 |
|||
// Lines indented under this line, |
|||
| reduce ($n.children[], null) as $c ( . + "\((" " * $level) // "")\($n.name)\n"; |
|||
if $c == null then . |
|||
const [firstTreeLines, rest] = Array.from( |
|||
else . + (" " * ($level + 1)) | printNest($c; $level + 1) |
|||
end ); |
|||
printNest($nested; 0); |
|||
// This first tree, and then the rest. |
|||
return [Node(s)(go(firstTreeLines))] |
|||
.concat(go(rest)); |
|||
})() : []; |
|||
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: (start + 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 ([]; |
|||
); |
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 |
|||
// div :: Int -> Int -> Int |
|||
</syntaxhighlight> |
|||
const div = x => y => Math.floor(x / y); |
|||
{{output}} |
|||
As for [[#Wren|Wren]]. |
|||
=={{header|Julia}}== |
|||
// eq (==) :: Eq a => a -> a -> Bool |
|||
<syntaxhighlight lang="julia">const nesttext = """ |
|||
const eq = a => b => { |
|||
RosettaCode |
|||
const t = typeof a; |
|||
rocks |
|||
return t !== typeof b ? ( |
|||
code |
|||
comparison |
|||
wiki |
|||
mocks |
|||
a === b |
|||
trolling |
|||
) : a.toString() === b.toString() |
|||
""" |
|||
) : (() => { |
|||
const kvs = Object.entries(a); |
|||
return kvs.length !== Object.keys(b).length ? ( |
|||
false |
|||
) : kvs.every(([k, v]) => eq(v)(b[k])); |
|||
})(); |
|||
}; |
|||
function nesttoindent(txt) |
|||
// firstArrow :: (a -> b) -> ((a, c) -> (b, c)) |
|||
ret = "" |
|||
const firstArrow = f => xy => Tuple(f(xy[0]))( |
|||
windent = gcd(length.([x.match for x in eachmatch(r"\s+", txt)]) .- 1) |
|||
xy[1] |
|||
for lin in split(txt, "\n") |
|||
); |
|||
ret *= isempty(lin) ? "\n" : isspace(lin[1]) ? |
|||
replace(lin, r"\s+" => (s) -> "$(length(s)÷windent) ") * "\n" : |
|||
"0 " * lin * "\n" |
|||
end |
|||
return ret, " "^windent |
|||
end |
|||
function indenttonest(txt, indenttext) |
|||
// flip :: (a -> b -> c) -> b -> a -> c |
|||
ret = "" |
|||
for lin in filter(x -> length(x) > 1, split(txt, "\n")) |
|||
(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) |
|||
// foldl1 :: (a -> a -> a) -> [a] -> a |
|||
restorednesttext = indenttonest(indenttext, itext) |
|||
const foldl1 = f => xs => |
|||
1 < xs.length ? xs.slice(1) |
|||
.reduce(uncurry(f), xs[0]) : xs[0]; |
|||
println("Original:\n", nesttext, "\n") |
|||
// fst :: (a, b) -> a |
|||
println("Indent form:\n", indenttext, "\n") |
|||
const fst = tpl => tpl[0]; |
|||
println("Back to nest form:\n", restorednesttext, "\n") |
|||
println("original == restored: ", strip(nesttext) == strip(restorednesttext)) |
|||
</syntaxhighlight>{{out}} |
|||
<pre> |
|||
Original: |
|||
RosettaCode |
|||
rocks |
|||
code |
|||
comparison |
|||
wiki |
|||
mocks |
|||
trolling |
|||
// isSpace :: Char -> Bool |
|||
const isSpace = c => /\s/.test(c); |
|||
Indent form: |
|||
// Returns Infinity over objects without finite length. |
|||
0 RosettaCode |
|||
// This enables zip and zipWith to choose the shorter |
|||
1 rocks |
|||
// argument when one is non-finite, like cycle, repeat etc |
|||
2 code |
|||
2 comparison |
|||
2 wiki |
|||
1 mocks |
|||
2 trolling |
|||
// length :: [a] -> Int |
|||
const length = xs => |
|||
(Array.isArray(xs) || 'string' === typeof xs) ? ( |
|||
xs.length |
|||
) : Infinity; |
|||
// lines :: String -> [String] |
|||
const lines = s => s.split(/[\r\n]/); |
|||
Back to nest form: |
|||
// minimum :: Ord a => [a] -> a |
|||
RosettaCode |
|||
const minimum = xs => |
|||
rocks |
|||
0 < xs.length ? ( |
|||
code |
|||
foldl1(a => x => x < a ? x : a)(xs) |
|||
comparison |
|||
wiki |
|||
mocks |
|||
trolling |
|||
// 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); |
|||
}; |
|||
original == restored: true |
|||
// splitAt :: Int -> [a] -> ([a], [a]) |
|||
</pre> |
|||
const splitAt = n => xs => |
|||
Tuple(xs.slice(0, n))( |
|||
xs.slice(n) |
|||
); |
|||
=={{header|Nim}}== |
|||
// succ :: Enum a => a -> a |
|||
const succ = x => 1 + x; |
|||
<syntaxhighlight lang="nim">import strformat, strutils |
|||
// uncurry :: (a -> b -> c) -> ((a, b) -> c) |
|||
const uncurry = f => |
|||
(x, y) => f(x)(y); |
|||
// until :: (a -> Bool) -> (a -> a) -> a -> a |
|||
const until = p => f => x => { |
|||
let v = x; |
|||
while (!p(v)) v = f(v); |
|||
return v; |
|||
}; |
|||
#################################################################################################### |
|||
// SAMPLE OUTLINES ------------------------------------ |
|||
# Nested representation of trees. |
|||
# The tree is simply the first node. |
|||
type |
|||
const strOutlineA = `Heilmeier catechism |
|||
Objectives and benefits |
|||
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?`; |
|||
NNode*[T] = ref object |
|||
const strOutlineB = `Rosetta stone |
|||
value*: T |
|||
is a granodiorite stele |
|||
children*: seq[NNode[T]] |
|||
engraved |
|||
with Greek and Egyptian texts |
|||
in different scripts. |
|||
which shed new light |
|||
on various homologies.`; |
|||
// MAIN --- |
|||
return main(); |
|||
})();</lang> |
|||
{{Out}} |
|||
<pre>Tree structure from outline: |
|||
proc newNNode*[T](value: T; children: varargs[NNode[T]]): NNode[T] = |
|||
[ |
|||
## Create a node. |
|||
[ |
|||
NNode[T](value: value, children: @children) |
|||
"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: |
|||
proc add*[T](node: NNode[T]; children: varargs[NNode[T]]) = |
|||
[ |
|||
## Add a list of chlidren to a node. |
|||
[ |
|||
node.children.add children |
|||
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." |
|||
] |
|||
] |
|||
Tree structure from indent levels: |
|||
proc `$`*[T](node: NNode[T]; depth = 0): string = |
|||
[ |
|||
## Return a string representation of a tree/node. |
|||
[ |
|||
result = repeat(' ', 2 * depth) & $node.value & '\n' |
|||
"Rosetta stone", |
|||
for child in node.children: |
|||
[ |
|||
result.add `$`(child, depth + 1) |
|||
[ |
|||
"is a granodiorite stele", |
|||
[ |
|||
#################################################################################################### |
|||
[ |
|||
# Indented representation of trees. |
|||
"engraved", |
|||
# The tree is described as the list of the nodes. |
|||
[ |
|||
type |
|||
"with Greek and Egyptian texts", |
|||
[] |
|||
INode*[T] = object |
|||
] |
|||
value*: T |
|||
level*: Natural |
|||
ITree*[T] = seq[INode[T]] |
|||
proc initINode*[T](value: T; level: Natural): INode[T] = |
|||
## Return a new node. |
|||
INode[T](value: value, level: level) |
|||
proc initItree*[T](value: T): ITree[T] = |
|||
## Return a new tree initialized with the first node (root node). |
|||
result = @[initINode(value, 0)] |
|||
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|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] [ |
|||
[] |
[0] "golfing", |
||
] |
[1] "trolling", |
||
[2] "emphasising execution speed" |
|||
] |
] |
||
], |
|||
[2] "code-golf.io", |
|||
[3] [ |
|||
"which shed new light", |
|||
[ |
[0] "encourages", |
||
[1] [ |
|||
" |
[0] "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}}== |
=={{header|Python}}== |
||
===Procedural=== |
|||
Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage. |
Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage. |
||
< |
<syntaxhighlight lang="python">from pprint import pprint as pp |
||
from collections import namedtuple |
|||
def to_indent(node, depth=0, flat=None): |
def to_indent(node, depth=0, flat=None): |
||
Line 1,036: | Line 1,461: | ||
print('Start Nest format:') |
print('Start Nest format:') |
||
nest = ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), |
nest = ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), |
||
('mocks', [(' |
('mocks', [('trolling', [])])]) |
||
pp(nest, width=25) |
pp(nest, width=25) |
||
Line 1,048: | Line 1,473: | ||
if nest != as_nest: |
if nest != as_nest: |
||
print("Whoops round-trip issues")</ |
print("Whoops round-trip issues")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,058: | Line 1,483: | ||
('wiki', [])]), |
('wiki', [])]), |
||
('mocks', |
('mocks', |
||
[(' |
[('trolling', [])])]) |
||
... To Indent format: |
... To Indent format: |
||
Line 1,067: | Line 1,492: | ||
(2, 'wiki'), |
(2, 'wiki'), |
||
(1, 'mocks'), |
(1, 'mocks'), |
||
(2, ' |
(2, 'trolling')] |
||
... To Nest format: |
... To Nest format: |
||
Line 1,076: | Line 1,501: | ||
('wiki', [])]), |
('wiki', [])]), |
||
('mocks', |
('mocks', |
||
[(' |
[('trolling', [])])])</pre> |
||
== |
=={{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] |
|||
} |
|||
} |
|||
lambda x: intIndent < x[0] |
|||
$last = $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)) |
|||
"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']]] |
|||
sw = sw + (" " * (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 |
|||
comparison |
|||
wiki |
|||
mocks |
|||
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> |
Revision as of 19:11, 14 March 2024
You are encouraged to solve this task according to the task description, using any language you may know.
The following shows a tree of data with nesting denoted by visual levels of indentation:
RosettaCode rocks code comparison wiki mocks trolling
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.
# E.g. if child nodes are surrounded by brackets # and separated by commas then: RosettaCode(rocks(code, ...), ...) # But only an _example_
Another datastructure for trees is to construct from the root an ordered list of the nodes level of indentation and the name of that node. The indentation for the root node is zero; node 'rocks is indented by one level from the left, and so on. Lets call this the indent form.
0 RosettaCode 1 rocks 2 code ...
- Task
- Create/use a nest datastructure format and textual representation for arbitrary trees.
- Create/use an indent datastructure format and textual representation for arbitrary trees.
- Create methods/classes/proceedures/routines etc to:
- Change from a nest tree datastructure to an indent one.
- Change from an indent tree datastructure to a nest one
- Use the above to encode the example at the start into the nest format, and show it.
- transform the initial nest format to indent format and show it.
- transform the indent format to final nest format and show it.
- Compare initial and final nest formats which should be the same.
- Note
- It's all about showing aspects of the contrasting datastructures as they hold the tree.
- Comparing nested datastructures is secondary - saving formatted output as a string then a string compare would suffice for this task, if its easier.
Show all output on this page.
11l
T NNode
String value
[NNode] children
F (value)
.value = value
F add(node)
.children.append(node)
F.const to_str(depth) -> String
V result = (‘ ’ * depth)‘’(.value)"\n"
L(child) .children
result ‘’= child.to_str(depth + 1)
R result
F String()
R .to_str(0)
T INode
String value
Int level
F (value, level)
.value = value
.level = level
F to_indented(node)
[INode] result
F add_node(NNode node, Int level) -> N
@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)
[NNode] stack
V nnode = NNode(tree[0].value)
L(i) 1 .< tree.len
V inode = tree[i]
I inode.level > stack.len
stack.append(nnode)
E I inode.level == stack.len
stack.last.children.append(nnode)
E
L inode.level < stack.len
stack.last.children.append(nnode)
nnode = stack.pop()
stack.last.children.append(nnode)
nnode = NNode(inode.value)
L stack.len > 0
stack.last.children.append(nnode)
nnode = stack.pop()
R nnode
print(‘Displaying tree built using nested structure:’)
V nestedTree = NNode(‘RosettaCode’)
V rocks = NNode(‘rocks’)
rocks.add(NNode(‘code’))
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:’)
V indentedTree = to_indented(nestedTree)
L(node) indentedTree
print((node.level)‘ ’(node.value))
print()
print(‘Displaying tree converted back to nested structure:’)
print(to_nested(indentedTree))
print(‘Are they equal? ’(I String(nestedTree) == String(to_nested(indentedTree)) {‘yes’} E ‘no’))
- Output:
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
C++
#include <iomanip>
#include <iostream>
#include <list>
#include <string>
#include <vector>
#include <utility>
#include <vector>
class nest_tree;
bool operator==(const nest_tree&, const nest_tree&);
class nest_tree {
public:
explicit nest_tree(const std::string& name) : name_(name) {}
nest_tree& add_child(const std::string& name) {
children_.emplace_back(name);
return children_.back();
}
void print(std::ostream& out) const {
print(out, 0);
}
const std::string& name() const {
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 {
public:
explicit indent_tree(const nest_tree& n) {
items_.emplace_back(0, n.name());
from_nest(n, 0);
}
void print(std::ostream& out) const {
for (const auto& item : items_)
std::cout << item.first << ' ' << item.second << '\n';
}
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() {
nest_tree n("RosettaCode");
auto& child1 = n.add_child("rocks");
auto& child2 = n.add_child("mocks");
child1.add_child("code");
child1.add_child("comparison");
child1.add_child("wiki");
child2.add_child("trolling");
std::cout << "Initial nest format:\n";
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? "
<< std::boolalpha << n.equals(n2) << '\n';
return 0;
}
- Output:
Initial nest format: RosettaCode rocks code comparison wiki mocks trolling Indent format: 0 RosettaCode 1 rocks 2 code 2 comparison 2 wiki 1 mocks 2 trolling Final nest format: RosettaCode rocks code comparison wiki mocks trolling Are initial and final nest formats equal? true
Go
package main
import (
"fmt"
"io"
"os"
"strings"
)
type nNode struct {
name string
children []nNode
}
type iNode struct {
level int
name string
}
func printNest(n nNode, level int, w io.Writer) {
if level == 0 {
fmt.Fprintln(w, "\n==Nest form==\n")
}
fmt.Fprintf(w, "%s%s\n", strings.Repeat(" ", level), n.name)
for _, c := range n.children {
fmt.Fprintf(w, "%s", strings.Repeat(" ", level+1))
printNest(c, level+1, w)
}
}
func toNest(iNodes []iNode, start, level int, n *nNode) {
if level == 0 {
n.name = iNodes[0].name
}
for i := start + 1; i < len(iNodes); i++ {
if iNodes[i].level == level+1 {
c := nNode{iNodes[i].name, nil}
toNest(iNodes, i, level+1, &c)
n.children = append(n.children, c)
} else if iNodes[i].level <= level {
return
}
}
}
func printIndent(iNodes []iNode, w io.Writer) {
fmt.Fprintln(w, "\n==Indent form==\n")
for _, n := range iNodes {
fmt.Fprintf(w, "%d %s\n", n.level, n.name)
}
}
func toIndent(n nNode, level int, iNodes *[]iNode) {
*iNodes = append(*iNodes, iNode{level, n.name})
for _, c := range n.children {
toIndent(c, level+1, iNodes)
}
}
func main() {
n1 := nNode{"RosettaCode", nil}
n2 := nNode{"rocks", []nNode{{"code", nil}, {"comparison", nil}, {"wiki", nil}}}
n3 := nNode{"mocks", []nNode{{"trolling", nil}}}
n1.children = append(n1.children, n2, n3)
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)
sb.Reset()
printNest(n, 0, &sb)
s2 := sb.String()
fmt.Print(s2)
fmt.Println("\nRound trip test satisfied? ", s1 == s2)
}
- Output:
==Nest form== RosettaCode rocks code comparison wiki mocks trolling ==Indent form== 0 RosettaCode 1 rocks 2 code 2 comparison 2 wiki 1 mocks 2 trolling ==Nest form== RosettaCode rocks code comparison wiki mocks trolling Round trip test satisfied? true
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.
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE UndecidableSuperClasses #-}
{-# LANGUAGE TypeApplications #-}
import Data.List (span)
-- A nested tree structure.
-- Using `Maybe` allows encoding several zero-level items
-- or irregular lists (see test example)
data Nest a = Nest (Maybe a) [Nest a]
deriving Eq
instance Show a => Show (Nest a) where
show (Nest (Just a) []) = show a
show (Nest (Just a) s) = show a ++ show s
show (Nest Nothing []) = "\"\""
show (Nest Nothing s) = "\"\"" ++ show s
-- An indented tree structure.
type Indent a = [(Int, a)]
-- class for isomorphic types
class Iso b a => Iso a b where
from :: a -> b
-- A bijection from nested form to indent form
instance Iso (Nest a) (Indent a) where
from = go (-1)
where
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
Testing:
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
λ> 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
And less satisfyingly and instructively – just relying a little passively on the existing Data.Tree,
we might also write something like:
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 -------
forestFromNestLevels :: [(Int, String)] -> Forest String
forestFromNestLevels = go
where
go [] = []
go ((n, v) : xs) =
uncurry (:) $
bimap (Node v . go) go (span ((n <) . fst) xs)
indentLevelsFromLines :: [String] -> [(Int, String)]
indentLevelsFromLines xs =
let pairs = first length . span isSpace <$> xs
indentUnit = maybe 1 fst (find ((0 <) . fst) pairs)
in first (`div` indentUnit) <$> pairs
outlineFromForest ::
(String -> String -> String) ->
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"
putStrLn $ drawTree $ Node "" nativeForest
let levelPairs = indentLevelsFromLines test
putStrLn "\n[(Level, Text)] list from lines:\n"
mapM_ print levelPairs
putStrLn "\n\nTrees from indented text:\n"
let trees = forestFromNestLevels levelPairs
putStrLn $ drawTree $ Node "" trees
putStrLn "Indented text from trees:\n"
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" []
]
]
- Output:
Tree representation parsed directly: | +- RosettaCode | | | +- rocks | | | | | +- code | | | | | +- comparison | | | | | `- wiki | | | `- mocks | | | `- trolling | `- Some lists | +- may | +- be | `- irregular [(Level, Text)] list from lines: (0,"RosettaCode") (1,"rocks") (2,"code") (2,"comparison") (2,"wiki") (1,"mocks") (2,"trolling") (0,"Some lists") (3,"may") (2,"be") (1,"irregular") Trees from indented text: | +- RosettaCode | | | +- rocks | | | | | +- code | | | | | +- comparison | | | | | `- wiki | | | `- mocks | | | `- trolling | `- Some lists | +- may | +- be | `- irregular Indented text from trees: RosettaCode rocks code comparison wiki mocks trolling Some lists may be irregular
Java
public class TreeDatastructures {
public static void main(String[] args) {
String initialNested = """
Rosetta Code
....rocks
........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 );
System.out.println("initialNested = finalNested ? " + equal);
}
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) {
StringBuilder result = new StringBuilder();
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";
}
- Output:
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 initialNested = finalNested ? true
jq
Adapted from Wren
Also works with gojq, the Go implementation of jq
# node of a nested representation
def NNode($name; $children): {$name, $children};
# node of an indented representation:
def INode($level; $name): {$level, $name};
# Output: string representation of an NNode structure
def printNest:
. as $nested
# input: string so far
| def printNest($n; $level):
if ($level == 0) then "\n==Nest form==\n\n" else . end
| reduce ($n.children[], null) as $c ( . + "\((" " * $level) // "")\($n.name)\n";
if $c == null then .
else . + (" " * ($level + 1)) | printNest($c; $level + 1)
end );
printNest($nested; 0);
# input: an INode structure
# output: the corresponding NNode structure
def toNest:
. as $in
| def toNest($iNodes; start; level):
{ i: (start + 1),
n: (if (level == 0) then .name = $iNodes[0].name else . end)
}
| 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
def printIndent:
"\n==Indent form==\n\n"
+ reduce .[] as $n ("";
. + "\($n.level) \($n.name)\n") ;
# output: representation using INode
def toIndent:
def toIndent($n; level):
. + [INode(level; $n.name)]
+ reduce $n.children[] as $c ([];
toIndent($c; level+1) );
. as $in
| [] | toIndent($in; 0);
### Example
def n: NNode(""; []);
def n1: NNode("RosettaCode"; []);
def n2: NNode("rocks"; [NNode("code"; []), NNode("comparison"; []), NNode("wiki"; [])] );
def n3: NNode("mocks"; [NNode("trolling"; [])]);
def n123:
n1
| .children += [n2]
| .children += [n3];
### The task
def nested:
n123
| printNest ;
def indented:
n123
| toIndent
| printIndent;
def roundtrip:
n123
| toIndent
| toNest
| printNest;
def task:
nested as $nested
| roundtrip as $roundtrip
| $nested, indented, $roundtrip,
"\nRound trip test satisfied? \($nested == $roundtrip)" ;
task
- Output:
As for Wren.
Julia
const nesttext = """
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
"""
function nesttoindent(txt)
ret = ""
windent = gcd(length.([x.match for x in eachmatch(r"\s+", txt)]) .- 1)
for lin in split(txt, "\n")
ret *= isempty(lin) ? "\n" : isspace(lin[1]) ?
replace(lin, r"\s+" => (s) -> "$(length(s)÷windent) ") * "\n" :
"0 " * lin * "\n"
end
return ret, " "^windent
end
function indenttonest(txt, indenttext)
ret = ""
for lin in filter(x -> length(x) > 1, split(txt, "\n"))
(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)
restorednesttext = indenttonest(indenttext, itext)
println("Original:\n", nesttext, "\n")
println("Indent form:\n", indenttext, "\n")
println("Back to nest form:\n", restorednesttext, "\n")
println("original == restored: ", strip(nesttext) == strip(restorednesttext))
- Output:
Original: RosettaCode rocks code comparison wiki mocks trolling Indent form: 0 RosettaCode 1 rocks 2 code 2 comparison 2 wiki 1 mocks 2 trolling Back to nest form: RosettaCode rocks code comparison wiki mocks trolling original == restored: true
Nim
import strformat, strutils
####################################################################################################
# Nested representation of trees.
# The tree is simply the first node.
type
NNode*[T] = ref object
value*: T
children*: seq[NNode[T]]
proc newNNode*[T](value: T; children: varargs[NNode[T]]): NNode[T] =
## Create a node.
NNode[T](value: value, children: @children)
proc add*[T](node: NNode[T]; children: varargs[NNode[T]]) =
## Add a list of chlidren to a node.
node.children.add children
proc `$`*[T](node: NNode[T]; depth = 0): string =
## Return a string representation of a tree/node.
result = repeat(' ', 2 * depth) & $node.value & '\n'
for child in node.children:
result.add `$`(child, depth + 1)
####################################################################################################
# Indented representation of trees.
# The tree is described as the list of the nodes.
type
INode*[T] = object
value*: T
level*: Natural
ITree*[T] = seq[INode[T]]
proc initINode*[T](value: T; level: Natural): INode[T] =
## Return a new node.
INode[T](value: value, level: level)
proc initItree*[T](value: T): ITree[T] =
## Return a new tree initialized with the first node (root node).
result = @[initINode(value, 0)]
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"
- Output:
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
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);
- Output:
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] [ [0] "golfing", [1] "trolling", [2] "emphasising execution speed" ] ], [2] "code-golf.io", [3] [ [0] "encourages", [1] [ [0] "golfing" ], [2] "discourages", [3] [ [0] "comparison" ] ] ] JSON: ["RosettaCode",["encourages",["code",["diversity","comparison"]],"discourages",["golfing","trolling","emphasising execution speed"]],"code-golf.io",["encourages",["golfing"],"discourages",["comparison"]]]
Phix
The standard Phix sequence is perfect for handling all of these kinds of structures.
function text_to_indent(string plain_text) sequence lines = split(plain_text,"\n",no_empty:=true), parents = {} for i=1 to length(lines) do string line = trim_tail(lines[i]), text = trim_head(line) integer indent = length(line)-length(text) -- remove any completed parents while length(parents) and indent<=parents[$] do parents = parents[1..$-1] end while -- append potential new parent parents &= indent integer depth = length(parents) lines[i] = {depth,text} end for return lines end function function indent_to_nested(sequence indent, integer idx=1, level=1) sequence res = {} while idx<=length(indent) do {integer lvl, string text} = indent[idx] if lvl<level then exit end if {sequence children,idx} = indent_to_nested(indent,idx+1,level+1) res = append(res,{text,children}) end while return {res,idx} end function function nested_to_indent(sequence nested, integer level=1) sequence res = {} for i=1 to length(nested) do {string text, sequence children} = nested[i] res = append(res,{level,text}) res &= nested_to_indent(children,level+1) end for return res end function constant text = """ RosettaCode encourages code diversity comparison discourages emphasising execution speed code-golf.io encourages golfing discourages comparison""" sequence indent = text_to_indent(text), nested = indent_to_nested(indent)[1], n2ichk = nested_to_indent(nested) puts(1,"Indent form:\n") pp(indent,{pp_Nest,1}) puts(1,"\nNested form:\n") pp(nested,{pp_Nest,8}) printf(1,"\nNested to indent:%s\n",{iff(n2ichk==indent?"same":"***ERROR***")})
- Output:
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
You can also strictly enforce these structures, which is obviously useful for debugging.
Admittedly this is somewhat more tedious, but at the same time infinitely more flexible and powerful than a "plain old struct".
type indent_struct(object o) if sequence(o) then for i=1 to length(o) do object oi = o[i] if not sequence(oi) or length(oi)!=2 or not integer(oi[1]) or not string(oi[2]) then return false end if end for return true end if return false end type type nested_struct(object o) if sequence(o) then for i=1 to length(o) do object oi = o[i] if not sequence(oi) or length(oi)!=2 or not string(oi[1]) or not nested_struct(oi[2]) then return false end if end for return true end if return false end type -- and as above except: function indent_to_nested(indent_struct indent, integer idx=1, level=1) function nested_to_indent(nested_struct nested, integer level=1) -- also make the output sequences better typed: indent_struct indent = text_to_indent(text) nested_struct nested = indent_to_nested(indent)[1] indent_struct r2ichk = nested_to_indent(nested)
Python
Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage.
from pprint import pprint as pp
def to_indent(node, depth=0, flat=None):
if flat is None:
flat = []
if node:
flat.append((depth, node[0]))
for child in node[1]:
to_indent(child, depth + 1, flat)
return flat
def to_nest(lst, depth=0, level=None):
if level is None:
level = []
while lst:
d, name = lst[0]
if d == depth:
children = []
level.append((name, children))
lst.pop(0)
elif d > depth: # down
to_nest(lst, d, children)
elif d < depth: # up
return
return level[0] if level else None
if __name__ == '__main__':
print('Start Nest format:')
nest = ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]),
('mocks', [('trolling', [])])])
pp(nest, width=25)
print('\n... To Indent format:')
as_ind = to_indent(nest)
pp(as_ind, width=25)
print('\n... To Nest format:')
as_nest = to_nest(as_ind)
pp(as_nest, width=25)
if nest != as_nest:
print("Whoops round-trip issues")
- Output:
Start Nest format: ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), ('mocks', [('trolling', [])])]) ... To Indent format: [(0, 'RosettaCode'), (1, 'rocks'), (2, 'code'), (2, 'comparison'), (2, 'wiki'), (1, 'mocks'), (2, 'trolling')] ... To Nest format: ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), ('mocks', [('trolling', [])])])
Raku
(formerly Perl 6)
Code golf is a entertaining passtime, even if it isn't appropriate for this site. To a large extent, I agree with 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.
#`(
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 = ' ';
my $trees = q:to/END/;
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 }
sub indent-to-nested { $^str.subst: / ^^ (\d+) \s* /, -> $/ { "{$level x +$0}" }, :g }
say $trees;
say my $indent = $trees.&nested-to-indent;
say my $nest = $indent.&indent-to-nested;
use Test;
is($trees, $nest, 'Round-trip equals original');
#`(
If, on the other hand, we want perform more complex transformations; better to
load it into a native data structure which will then allow us to manipulate it
however we like.
)
# Import outline paragraph into native data structure
sub import (Str $trees, $level = ' ') {
my $forest;
my $last = -Inf;
for $trees.lines -> $branch {
$branch ~~ / ($($level))* /;
my $this = +$0;
$forest ~= do {
given $this cmp $last {
when More { "\['{esc $branch.trim}', " }
when Same { "'{esc $branch.trim}', " }
when Less { "{']' x $last - $this}, '{esc $branch.trim}', " }
}
}
$last = $this;
}
sub esc { $^s.subst( /(<['\\]>)/, -> $/ { "\\$0" }, :g) }
$forest ~= ']' x 1 + $last;
$forest.EVAL;
}
my $forest = import $trees;
say "\nNative data structure:\n", $forest.raku;
{
use JSON::Fast;
say "\nJSON:\n", $forest.&to-json;
}
{
use YAML;
say "\nYAML:\n", $forest.&dump;
}
- Output:
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 RosettaCode encourages code diversity comparison discourages golfing trolling emphasising execution speed code-golf.io encourages golfing discourages comparison ok 1 - Round-trip equals original Native data structure: $["RosettaCode", ["encourages", ["code", ["diversity", "comparison"]], "discourages", ["golfing", "trolling", "emphasising execution speed"]], "code-golf.io", ["encourages", ["golfing"], "discourages", ["comparison"]]] JSON: [ "RosettaCode", [ "encourages", [ "code", [ "diversity", "comparison" ] ], "discourages", [ "golfing", "trolling", "emphasising execution speed" ] ], "code-golf.io", [ "encourages", [ "golfing" ], "discourages", [ "comparison" ] ] ] YAML: --- - RosettaCode - - encourages - - code - - diversity - comparison - discourages - - golfing - trolling - emphasising execution speed - code-golf.io - - encourages - - golfing - discourages - - comparison ...
Wren
import "./dynamic" for Struct
import "./fmt" for Fmt
var NNode = Struct.create("NNode", ["name", "children"])
var INode = Struct.create("INode", ["level", "name"])
var sw = ""
var printNest // recursive
printNest = Fn.new { |n, level|
if (level == 0) sw = sw + "\n==Nest form==\n\n"
sw = sw + Fmt.swrite("$0s$s\n", " " * level, n.name)
for (c in n.children) {
sw = sw + (" " * (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|
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
toIndent = Fn.new { |n, level, iNodes|
iNodes.add(INode.new(level, n.name))
for (c in n.children) toIndent.call(c, level+1, iNodes)
}
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)
var s1 = sw
System.print(s1)
var iNodes = []
toIndent.call(n1, 0, iNodes)
sw = ""
printIndent.call(iNodes)
System.print(sw)
var n = NNode.new("", [])
toNest.call(iNodes, 0, 0, n)
sw = ""
printNest.call(n, 0)
var s2 = sw
System.print(s2)
System.print("\nRound trip test satisfied? %(s1 == s2)")
- Output:
==Nest form== RosettaCode rocks code comparison wiki mocks trolling ==Indent form== 0 RosettaCode 1 rocks 2 code 2 comparison 2 wiki 1 mocks 2 trolling ==Nest form== RosettaCode rocks code comparison wiki mocks trolling Round trip test satisfied? true
zkl
fcn nestToIndent(nestTree){
fcn(out,node,level){
out.append(List(level,node[0])); // (n,name) or ("..",name)
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)
}
}
out
}(List(),nestTree,0)
}
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);
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") }
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);
- Output:
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
I'm choosing to only allow one root per tree/forest so the Raku example is coded differently:
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();
- Output:
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