view release on metacpan or  search on metacpan

docs/blog/perl-weekly-challenges-113.md  view on Meta::CPAN

Check the [functional-perl website](http://functional-perl.org/) for
properly formatted versions of these documents.

---

# The Perl Weekly Challenges, #113

### Solving The Perl Weekly Challenges with FunctionalPerl

<small><i>[Christian J.](mailto:ch@christianjaeger.ch), 23 May 2021</i></small>

I've started solving [The Perl Weekly
Challenges](https://perlweeklychallenge.org/), and of course my main
attention is on seeing how FunctionalPerl fits. Sometimes a functional
approach will be a clear match (or so I think), sometimes solutions
without FunctionalPerl will be just as good and I won't contest it,
sometimes I won't see how it's going to be useful and I might end up
just using the repl and some bits during developments but not in the
final solutions, sometimes I might be using FunctionalPerl just
because I can.

Since I'm the author of `FunctionalPerl` and it's not widely used yet,
my main task here will have to be to explain the bits of the
`FunctionalPerl` libraries that I'm using in my solutions.

I already solved one task from [The Weekly Challenge -
111](https://perlweeklychallenge.org/blog/perl-weekly-challenge-111/),
[111-1-search_matrix](../../examples/perl-weekly-challenges/111-1-search_matrix),
but didn't submit it. It led me to create a new module
`FP::SortedPureArray`, which represents an array sorted according to
some comparison function, and offers a method for a binary search that
was what that challenge required (for efficiency with large matrices,
anyway).

On to [the new tasks](https://perlweeklychallenge.org/blog/perl-weekly-challenge-113/).

<with_toc>

## Task #2: Recreate Binary Tree

I solved this task first, so I'm also going to write about it
first. The task description is
[here](https://perlweeklychallenge.org/blog/perl-weekly-challenge-113/#TASK2),
my solution is
[here (functional-perl repository)](../../examples/perl-weekly-challenges/113-2-recreate_binary_tree) and
[here (perlweeklychallenge repository)](https://github.com/manwar/perlweeklychallenge-club/blob/master/challenge-113/christian-jaeger/perl/ch-2.pl).
I'm going to copy the important pieces of the script only, for the
full context open one of these links.

Trees and functional progamming are a good match if the trees don't
have circular links. In this case, the nodes can be immutable data
structures, for changes new node instances can be allocated which
share the unmodified children with the previous instance, thus only
little data needs to be copied, while still leaving the old version
of the tree around unmodifed, which is what functional
programming requires. Often trees in the imperative
world have links back to the parents, though, i.e. cycles, which
aren't a problem in Perl if weakening or destructors are used
correctly, but which violate the purely functional approach—how would
you re-use the child nodes if you create a new modified parent, but
the children are still pointing to the previous version of the parent? But
algorithms that need access to the parent nodes can instead maintain
linked lists to the parents while diving down the tree (separate from
the tree), thus parent links don't actually need to be stored in the
tree even if you think you need them. Anyway, this is a digression,
the given task is very simple, none of this parent business applies.

    package PFLANZE::Node {
        use FP::Predicates qw(is_string maybe instance_of);
        *is_maybe_Node = maybe instance_of("PFLANZE::Node");

        use FP::Struct [
            [\&is_maybe_Node, "left"],
            [\&is_string,     "value"],
            [\&is_maybe_Node, "right"]
        ] => ("FP::Struct::Show", "FP::Struct::Equal");
        
        ...

I'm using `FP::Struct` for class construction like I do for all of my
current functional code—I'm still improving and gaining experience
with it and it's too early for me to know whether or how to introduce
the features I want into `Moose` or another class builder. I like its
simplicity, but obviously I'm very biased. The `FP::Struct` importer
simply takes an array of field definitions, each of which can either
be a string (the field name), or an array of `[\&predicate,
"fieldname"]`, where the predicate is a function of one argument that
must return true for any value that is to be stored in field
`fieldname` (otherwise `FP::Struct`'s constructor and setters will
throw an exception).

After the field definitions come parent classes; `FP::Struct::Show`
automatically implements the `show` function from `FP::Show`, which
shows Perl code that creates the data in question, which is useful in
the repl (from `FP::Repl`) during development; `FP::Struct::Equal`
implements the `equal` function from `FP::Equal`, which is used in the
tests.

You might be asking why I'm not using `overload` for these: for `show`
my answer is that it is stringification specifically for debugging,
not for the general case. Say you've got a class `Path` representing a
file system path, you construct it via `Path("/foo/bar")` (`Path` is a
constructor function here, as I'm about to explain), and you want that
path be stringified to `"/foo/bar"` so you can transparently use it in
Perl's `open` or whatever. But the repl should show you
`Path("/foo/bar")`, as that is what constructs such an object, and not
`"/foo/bar"`, as the latter would evaluate to a plain string, and if
you entered that back into the repl passing it to some function call
it would likely behave differently.

With regards to `equal`, one answer is that I'm gaining experience to
see. Partial other answers could be that Perl has just numeric and
string comparison to overload, and numeric comparison doesn't apply in
general and string comparison is going to be suffering from the same
issue as above.

        use FP::Predicates qw(is_string maybe instance_of);
        *is_maybe_Node = maybe instance_of("PFLANZE::Node");

docs/blog/perl-weekly-challenges-113.md  view on Meta::CPAN

that fails, three, etc., like:

    use FP::Stream qw(stream_cartesian_product)
    # stream_cartesian_product only works on `list` or `stream`,
    # so convert the purearray to list first:
    my $ns = $ns->list;
    check(stream_cartesian_product $ns, $ns)
    or check(stream_cartesian_product $ns, $ns, $ns)
    or check(stream_cartesian_product $ns, $ns, $ns, $ns)
    ...

Instead, I just basically hand coded a cartesian product that
automatically extends itself to additional levels until that level is
shown to be exhausted (finds no match):

    sub maybe_choose_brute ($N, $ns) {
        __ 'Choose a combination of numbers from $ns (repetitions allowed)
            that added together equal $N; undef if not possible. This
            solution is brute force in that it is picking additional
            numbers from the left end of $ns, one after another,
            depth-first.';

        sub ($chosen) {
            my $check = __SUB__;
            warn "check (brute): " . show($chosen) if $verbose;
            my $sum = $chosen->sum;
            if ($sum == $N) {
                $chosen
            } elsif ($sum > $N) {
                undef
            } else {
                $ns->any(
                    sub ($n) {
                        $check->(cons($n, $chosen))
                    }
                )
            }
            }
            ->(null)
    }

<small>(I don't know why `perltidy` chooses not to put the `}` on the
third-last line 4 spaces further to the left, so that it would line up
with the `sub ($chosen) {` line. Anyone knows how to improve this?
Please tell.)</small>

#### `__SUB__`

You may not be familiar with `__SUB__` from `use feature
'current_sub'`—if you are, skip this section. 

This is the best way for a local function to get access to itself, so
that it can be self-recursive. Note that the following wouldn't work
as the sub is evaluated in the context before `$check` is introduced
and thus wouldn't have access to it:

    my $check= sub ($chosen) { ... sub { .. $check .. } .. };
    $check->(null)

This would work but leads to a cycle and thus memory leak (which
could be remedied by using an additional variable and then `weaken`ing
the self-referential variable, but `__SUB__` is going to be faster and
less to write):

    my $check;
    $check= sub ($chosen) { ... sub { .. $check .. } .. };
    $check->(null)

Same problem with `my sub check ($chosen) { ... }`.

Also note that `__SUB__` *has* to be assigned to a lexical variable
(`$check`) here, as we're only using it inside *another* nested sub,
thus `__SUB__` in *there* would be that other sub instead.

(Maybe Perl should introduce something like this

    my rec $check = sub ($chosen) { ... sub { .. $check .. } .. };
    $check->(null)

but I haven't thought about it deeply. Or perhaps make the `my sub`
syntax self-recursive but work without the cycle?)

#### The algorithm

The idea is to check a set of chosen numbers: if their sum is equal to
`$N`, we have found the solution and simply return that set. If the
sum is larger than `$N`, then there is no point adding any additional
number, and we can return `undef` to signal that there is no solution
with those choices. If we haven't reached `$N` yet, we need to add
another number from `$ns` and check again. We do this for *all*
numbers from `$ns` until we find a match. That latter bit is being
carried out by the `any` method which is implemented for all types
implementing `FP::Abstract::Sequence`, which includes the purearray
that `$ns` is. Shown again here:

            $ns->any(
                sub ($n) {
                    $check->(cons($n, $chosen))
                }
            )

What `any` does is, it iterates through the object (`$ns` in this
case), passes each of the elements to the function that was passed to
the method (`sub ($n) { .. }` in this case), and if that function
returns a true value, returns that same value itself (i.e. stopping
the iteration). Examples:

    purearray(20, 30, 40)->any(sub($v) { $v == 30 }) # returns 1
    purearray(20, 30, 40)->any(sub($v) { $v == 31 }) # returns ''
    purearray(20, 30, 40)->any(sub($v) { $v == 30 and "y" }) # returns "y"

Our local `$check` function is returning `undef` if there is no
result, and the set of numbers making a successful search in the other
case. Thus `any` returns the same. Thus `maybe_choose_brute` returns
the same, which is what we want. (I should perhaps have used a better
name for `$check`, perhaps `$maybe_choose`, to maintain the Hungarian
notation locally, too.)

#### Linked lists

The remaining bit to explain here is `cons`: this is from `FP::List`