Data::Tree

A Raku (rooted) tree data structure modelled on Haskell's Data.Tree.

class Tree::RTree

RTree: rooted tree containing data and children (other rooted trees)

class Tree::Forest

Forest: container class for an array of trees

Installation

Using zef: clone this repo and

• run zef install <path-to-repo>;

• or cd into it and run zef install ..

Usage

The examples below are run in a Raku REPL with access to this module. So assume you've run 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:

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

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

> 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

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

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

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

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

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

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

> foldTree(&folder, unfoldTree(&f,1))
28

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

There's also a map method that both the classes overload, which does what (I think) you think it should. Using that same &f I have been in this running example:

> unfoldTree(&f,1).map(* ** 2).&drawTree
1
|
+-4
| |
| +-16
| |
| `-25
|
`-9
  |
  +-36
  |
  `-49

Ditto for grep:

> unfoldTree(&f,1).grep({ $_.data != 2|3 }).&drawForest
1
|
+-4
|
+-5
|
+-6
|
`-7

grep always returns a Forest, hence the need to call &drawForest on the result.

What happened there is that

• The predicate I passed identified via a junction which nodes have their data attrebute equal to either 2 or 3;

• Those nodes were eliminated;

• The remaining nodes got stitched together into a forest (consisting of a single tree in this case) via the closest-ancestor relationship.

Whether this is what grep should be doing to a tree is debatable: it could, for instance, simply throw out the relevant nodes and leave it at that, without re-attaching (hence producing a bunch of isolated nodes in this case).

In any case, this is the built-in behavior at present.

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

Creation

sub lol2tree

sub lol2tree(
    @a
) returns Tree::RTree

lol2tree

original inspiration

sub unfoldTree

sub unfoldTree(
    &unFolder,
    $root
) returns Tree::RTree

unfoldTree

original inspiration

sub unfoldForest

sub unfoldForest(
    &unFolder,
    @roots
) returns Tree::Forest

unfoldForest

original inspiration

Reduction

sub foldTree

sub foldTree(
    &folder,
    Tree::RTree $t
) returns Mu

foldTree

original inspiration

sub flatten

sub flatten(
    Tree::RTree $t
) returns Array

flatten

original inspiration

sub levels

sub levels(
    Tree::RTree $t
) returns Array

levels

original inspiration

Display

sub drawTree

sub drawTree(
    Tree::RTree $t
) returns Str

drawTree

original inspiration

sub drawTreeLines

sub drawTreeLines(
    Tree::RTree $t
) returns Array

drawTreeLines

original inspiration

multi sub drawSubTrees

multi sub drawSubTrees(
    @ ()
) returns Mu

drawSubTrees

original inspiration

sub drawForest

sub drawForest(
    Tree::Forest $f
) returns Str

drawForest

original inspiration