Keyword::Treefold - Add keyword for an FP tree-fold.


    use Keyword::TreeFold;

    # result of block is assigned to @_ while @_ > 1.
    # block consumes the stack.

    tree_fold tree_hash
        my $last    = @_ / 2 - 1;

                    my $i   = 2 * $_;

                    sha256 @_[ $i, 1 + $i ]
                ( 0 .. $last )
            @_ % 2
            ? $_[-1]
            : ()

    # same result as above with wrapper code extracting the
    # lexical variables. block can extract any number of 
    # variables > 1.

    tree_fold tree_hash ( $left, $rite )
        ? sha256 $left, $rite
        : $left

    # in all cases an exception will be raised if the stack does
    # not shrink after each iteration (e.g., if a block with two
    # parameters outputs two values for each iteration).


The "fold" pattern is common in FP languages. It is commonly seen as a "Right Fold" in the form of reduce, which takes a single value and iterates it with the stack to form a single value (e.g., with an addition to get a sum). A recursive solution to reduce combines the first two items from the stack (e.g., by adding them) and then calls itself with the result and the remaining stack. This chews through the stack one item at a time.

Tree Fold is a bit different in that it iterates the entire stack each time before recursing. For example the AWS "tree hash" used with Glacier uploads does an SHA of every pair of items on the stack then recurses a new stack half the size.

One issue with the recursive solution is consuming a huge amount of stack. The solution to this is tail call elimination, which is a built-in part of most FP lanuages. While quite doable in Perl5 the fix is somewhat ugly, requiring an assignment to @_ and use of goto to restart the current subroutine recycling the stack.

This module implements a tree_fold keyword which wraps the input block in code that checks the scak, re-assigns @_, and uses goto to recurse. This avoids the overhad of multiple stack frames with minimal overhead.

Simple Blocks

If the block using tree_fold does not include any parameters it gets wrapped in code like:

    sub $name
        @_ > 1 or return $_[0];

        @_ = do { code block };

        goto __SUB__

In this case it is up to the block to consume @_ for itself. For example, the glacier tree hash might look like:

    tree_fold glacier_hash
        my $count
        = @_ % 2
        ? @_ / 2 + 1
        : @_ / 2
            @_ > 1
            ? sha256 splice @_, 0, 2
            : shift
        ( 1 .. $count )

which will convert the current stack into a set of SHA256 values for each pair of items on the stack.

Using Parameters

Instead of managing the stack itself, the block can use parameters. The glacier hash might look like:

    tree_fold glacier_hash( $left, $rite )
        ? sha256 $left, $rite
        : $left

which leaves the wrapper produced by tree_fold to splice off the stack contents and assign them to $left & $rite for each iteration.



Which describes how this module constructs the wrapper for each block.


Examples of reduce.

Neatly Folding a Tree

Talk describing FP solution to a tree-hash including use of tail call elimination and constant values:


Combined talk with Damian Conway on tail call elimination in Perl5 and Perl6:



Steven Lembark <>


This module is licensed under the same terms as Perl-5.22 itself or any later version of Perl.

1 POD Error

The following errors were encountered while parsing the POD:

Around line 258:

'=item' outside of any '=over'