head

A B<Raku> (rooted) tree data structure modelled on B<Haskell>'s L<Data.Tree|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html>.



#| RTree: rooted tree containing data and children (other rooted trees)
class RTree is export {
    has $.data is rw;
    has RTree @.children is rw = [];
}

#| Forest: container class for an array of trees
class Forest is export {
    has RTree @.trees is rw;
}



Using L<zef|https://github.com/ugexe/zef>: clone this repo and


item

The examples below are run in a C<Raku> REPL with access to this module. So assume you've run C<use Data::Tree> successfully in your REPL session. 


Construct a tree from a nested list structure (list-of-lists, or lol) and then draw it:


code

=begin code
> [1,[2,4,[5,6,7,8]],3].&lol2tree.&drawTree
1
|
+-2
| |
| +-4
| |
| `-5
|   |
|   +-6
|   |
|   +-7
|   |
|   `-8
|
`-3
=end code


"Unfold" a tree using a function C<&f> that produces leaves from a seed, and then draw it:


=begin code
> sub f($x) {
* 2*$x+1 > 7 && return ($x, []);
* return ($x, [2*$x, 2*$x+1]);
* }
&f

> unfoldTree(&f,1).&drawTree
1
|
+-2
| |
| +-4
| |
| `-5
|
`-3
  |
  +-6
  |
  `-7
=end code 


Show the levels of that same last tree, as a list of lists:


=begin code
> unfoldTree(&f,1).&levels
[[1] [2 3] [4 5 6 7]]
=end code


Or flatten it into a pre-order-traversal list:


=begin code
> unfoldTree(&f,1).&flatten
[1 2 4 5 3 6 7]
=end code


Or compute the sum of its vertex values, by folding it with a summation "folder" function:


=begin code
> sub folder($head, @rest) { $head + @rest.sum }
&folder

> foldTree(&folder, unfoldTree(&f,1))
28
=end code


(sanity check: yes, 1+2+3+4+5+6+7 equals 7 * 8 / 2 = 28). 


Finally, here is a list of exported (or exportable) functions, with links to their cousins' documentation from B<Haskell> or B<Perl>.



#| lol2tree
sub lol2tree(@a --> RTree) is export {
    (! @a.elems) && return RTree.new();
    return RTree.new(data => @a[0], children => @a.[1..*].map({ ($_ ~~ Array) ?? ($_) !! ([$_]) }).map(*.&lol2tree).Array);
}



L<original inspiration|https://metacpan.org/pod/Tree::DAG_Node#lol_to_tree($lol)>



#| unfoldTree
sub unfoldTree(&unFolder, $root --> RTree) is export {
    my $data = $root.&unFolder.[0];
    my @subTrees = $root.&unFolder.[1].map({ unfoldTree(&unFolder, $_) });
    return RTree.new(data => $data, children => @subTrees);
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html#v:unfoldTree>



#| unfoldForest
sub unfoldForest(&unFolder, @roots --> Forest) is export {
    my @trees = @roots.map({ unfoldTree(&unFolder, $_) });
    return Forest.new(trees => @trees);
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html#v:unfoldForest>



#| foldTree
sub foldTree(&folder, RTree $t) is export {
    return &folder($t.data, $t.children.map({ foldTree(&folder, $_) }))
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html#v:foldTree>



#| flatten
sub flatten(RTree $t) is export {
    return [$t.data, |$t.children.map({ $_.&flatten }).map(|*) ]
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html#v:flatten>



#| levels
sub levels(RTree $t) is export {
    (! $t.data) && return [];
    return [[$t.data], |roundrobin($t.children.map({ $_.&levels })).map(*.map(|*).Array).Array]
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html#v:levels>



#| drawTree
sub drawTree(RTree $t) is export {
    return $t.&drawTreeLines.join("\n");
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html#v:drawTree>



#| drawTreeLines
sub drawTreeLines(RTree $t) {
    return [|$t.data.Str.lines, |drawSubTrees($t.children)]
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/src/Data.Tree.html#draw>



#| drawSubTrees
multi sub drawSubTrees([]) { return [] }
multi sub drawSubTrees([$t]) {
    return ["|", |(("`-", "  ", {$_} ... *) Z~ ($t.&drawTreeLines))]
}
multi sub drawSubTrees(@ts) {
    return ["|", |(("+-", "| ", {$_} ... *) Z~ (@ts.[0].&drawTreeLines)), |(drawSubTrees(@ts[1..*]))]
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/src/Data.Tree.html#local-6989586621679098624>



#| drawForest
sub drawForest(Forest $f --> Str) is export {
    return $f.trees.map({ .&drawTree }).join("\n");
}



L<original inspiration|https://hackage.haskell.org/package/containers-0.6.4.1/docs/Data-Tree.html#v:drawForest>


root

README

React

=begin React :component<HeaderCol> :id<menu> 
=para L<Documentation|/doc/introduction>
=para L<Modules| /mods>
=para L<Examples| file:../examples/index.podlite>
=para L<Download |file:../download/index.podlite>
=para L<About|file:../about/index.podlite>
=para 🔍 K<⌘K>/K<ctrl-K>
=end React


=begin React :component<HeaderCol> :id<footer>  
=begin nested :!nested
=item1 B<Language>
    =item2 L<Get started|file:../getting-started/getting-started.podlite>
    =item2 L<Why Raku?|/doc/language/faq#Why-should-I-learn-Raku-What's-so-great-about-it>
    =item2 L<Try Raku|https://glot.io/new/raku>
    =item2 L<Raku cheat sheet|https://github.com/Raku/mu/blob/master/docs/Perl6/Cheatsheet/cheatsheet.txt>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<Raku on Exercism|https://exercism.org/tracks/raku>
    =item2 L<Wikipedia|https://en.wikipedia.org/wiki/Raku_(programming_language)>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=begin nested :!nested

=item1 B<L<Documentation|/doc>>
    =item2 L<Getting started, Migration guides from other languages, & Tutorials | file:../doc/introduction.podlite>
    =item2 L<Language References|file:../doc/reference.podlite>
    =item2 L<Type Reference| file:../doc/types.podlite>
    =item2 L<Miscellaneous| file:../doc/miscellaneous.podlite>
    =item2 L<FAQs (Frequently Asked Questions)|/doc/language/faq>
    =item2 L<Community|/doc/language/community>
    =item2 L<The list of all documents|file:../doc/index.podlite>

=item1 B<Resources>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>

=end nested
=begin nested :!nested

=item1 B<Resoures>
    =item2 L<Download | file:../download/index.podlite>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=item1 B<Learning>
    =item2 L<The Raku Guide|https://raku.guide/>
    =item2 L<Wikibook |https://en.wikibooks.org/wiki/Raku_Programming>
    =item2 L<Books |https://perl6book.com/>
    =item2 L<Rosetta Code | https://www.raku.org/community/rosettacode>
    =item2 L<Learn Raku in Y minutes|https://learnxinyminutes.com/docs/raku/>
    =item2 L<Golfing |https://github.com/AlexDaniel/raku-golf-cheatsheet>
=end nested
=begin nested :!nested

=item1 B<Explore>
    =item2 L<Raku Blog Aggregator|https://planet.raku.org/>
    =item2 L<Rakudo Weekly|https://rakudoweekly.blog/>
    =item2 L<The Weekly Challenge |https://perlweeklychallenge.org/>
    =item2 L<Raku Advent Calendar|https://raku-advent.blog/>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>
    =item2 L<empty|#>

=end nested
=end React


=begin React :component<CookieConsent> :id<CookieConsent> :buttonCaption("Got it!")
=para
This website uses cookies for analytics.
=end React


Tree

Data::Tree

Installation

Usage

Creation

Reduction

Display

Data::Tree v0.1

Authors

License

Dependencies

Test Dependencies

Provides

Documentation