Perl 6 - Curried Function Hangs

Question

So, I wanted to be able to write a function that will figure out all the ways that you could make change for a specific amount of money, using coins of different values.

So, I wrote a function coin that tells you for a given amount, how many ways you can make change for that value, given a certain value coin, and a function that will calculate how many ways you could make change, with the same kinds of parameters for the next smaller coin.

I then tried to write a function ladder that I want to return a function that for an @array of coin values will return a function takes a single formal parameter $amt that calculates the number of ways that you could make change for that amount given the values of the coins specified in the array.

I tried to use the &coin function with an .assuming method to add in the values of coins and build up the appropriate ladder. Unfortunately, it hangs when I try to run the resulting function.

my @values = 2, 5, 10, 20, 50, 100, 200;
#the coin of value 1 is assumed as a base case

my &test = ladder(@values);

say &test(5);

sub ladder(@values) {
        my &base = sub () { return @values.shift };
        for @values {
                &base = &coin.assuming(*,$_,&base);
        }
        return &base;
}

sub coin($amt,$value,&lesser) {
        if $amt >= $value {
                return &coin($amt-$value,$value,&lesser) + &lesser($amt);
        } else {
                return &lesser($amt);
        }
}

To give an idea it &ladders should produce the equivalent of &twopd in the below series of functions.

sub twopd($amt) { return &coin($amt,200,&onepd) };

sub onepd($amt) { return &coin($amt,100,&fifp) };

sub fifp($amt) { return &coin($amt,50,&twep) };

sub twep($amt) { return &coin($amt,20,&tenp) };

sub tenp($amt) { return &coin($amt,10,&fivp) };

sub fivp($amt) { return &coin($amt,5,&twop) };

sub twop($amt) { return &coin($amt,2,&onep) };

sub onep($amt) { return 1 };

I was wondering if anyone might have an idea what I am doing wrong.

Answer 1

• sub () { return @values.shift } will remove a value from @values everytime it gets called, which is not what you want.

• &coin.assuming(*,$_,&base) needs to do something with the &base so that it gets the current value in &base and not what is left in it at the end of the loop. One option is to add | in front of it and another is to use <> to decontainerize the value.

It is probably a good idea to add some caching to coin as it will get called with the same arguments many times for larger values.

sub ladder ( +@ ($initial, *@values) ) {
    my &base = -> $ { $initial };
    for @values {
        &base = &coin.assuming: *,  $_, &base<>;
    }
    return &base;
}

use experimental :cached;

sub coin ( $amt, $value, &lesser ) is cached {
    if $amt >= $value {
        coin( $amt - $value, $value, &lesser ) + lesser($amt);
    } else {
        lesser( $amt );
    }
}