Why not reduction?

So it's been a while since I posted here but a post on the Weekly Challenge number 131 made me want to share my solution. The blog post by glfdex was inspired by this one by Falvio. Anyway I looked at both of these and wondered... "Why didn't they use reduction?"

An Aside

For those of you who don't know, reduction is one of the core list processing utilities. I tend to use it alot in the form of the Reduction Meta operator which works something like this.

Given a list a,b,c,d,e apply the operation to a and b, then apply the operation to the result of that and C and so one. So an example :

say [+] 1,2,3,4,5,6

is the same as writing :

say (((((1+2)+3)+4)+5)+6)

but as well as the reduction operator Raku also has the reduce method which takes a pair of inputs and returns a single result.

Back to the challenge

So I want to use reduce to solve this. Lets start with a simple wrapper :

sub MAIN( *@vals where *.all ~~ Int() ) {
    @vals.reduce(
        ... # Insert reduction here
    ).say;
}

So if we want to use reduce we want it to return an Array of Arrays, but this means our reduction is going to receive such an array for it's first value. But not at the start of the list... Still that's not too hard to deal with.

sub MAIN( *@vals where *.all ~~ Int() ) {
    @vals.reduce(
        -> $v1 is copy, $v2 {
            if $v1 ~~ Int(Str) {
                $v1 = [[$v1],]
            }
            ...
            $v1
        }
    ).say;
}

So we make our first value a copy so we can modify it (other wise it's immutable, which is good generally). If it's an Integer (or more generally an IntStr allomorph) we turn it into an Array with a single element (an Array containing the value). We need the trailing comma there or we fall foul to the single argument rule.

Now we can do the bulk of our code. Which is pretty simple really. If $v2 is equal to 1 more than the last item in the last array in $v1 which append it to the list. Otherwise we append a new array containing $v2.... that was simple right... Look here's the code.

sub MAIN( *@vals where *.all ~~ Int() ) {
    @vals.reduce(
        -> $v1 is copy, $v2 {
            if $v1 ~~ Int(Str) {
                $v1 = [[$v1],]
            }
            if $v1[*-1][*-1] ~~ $v2-1 {
                $v1[*-1].push($v2)
            } else {
                $v1.push( [ $v2, ] )
            }
            $v1
        }
    ).say;
}

And there we go. A nice simple reduction that goes through the list... But looking at it I think it can be better. Really we don't want to be copying and pushing to lists, that reduces our ability to split it into multiple jobs. Which isn't an issue with a few items but what if we had a list of 100,000? Wouldn't it be nice to just add a hyper and let all our cores do something with it?

... So I did a bit of experimenting and it doesn't play as nice with hyper as I hoped but here's a more purely functional version of the reduction.

sub group-vals (@vals) {
    return lazy @vals.map( { (($_,),) } ).reduce(&join-list);
}

sub join-list( \l1, \l2 ) {
    if ( l1[*-1][*-1]+1 ~~ l2[0][0] ) {
        (
            |(l1.elems > 1 ?? l1[0..^*-1] !! Empty),
            (|l1[*-1], |l2[0],),
            |(l2.elems > 1 ?? l2[1..*] !! Empty )
        );
    } else {
        (|l1, |l2);
    }
}

So firstly we assume that the caller handles the printing and instead return a lazy list (so if we don't need all of it we can skip it). Then we make our list into a list of lists and now we can reduce it.

Our reduction now takes two lists of lists. We either want to join them or not depending on the items at the end and start of each. For example :

((1,2),(3)) and ((4))

Here the 3 and 4 are in sequence so we join them into :

((1,2),(3,4))

Note that this code can handle if the second list is longer than a single character. So I think for big lists (up to 10,000 hyper does fine) I need to break it into small lists and reduce each of them then do a second final reduction on the result.

Anyway.... that how I handled it. Enjoy.