Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementation of a function object "power" operator in Raku

In APL there is the power operator , which if applied to a function f superimposes the application of f. How to implement that operator in Raku?

For example, with this definition of f:

sub f(Int:D $i){ $i + 1 }

the command say (f ⍣ 4)(10); should be equivalent to say f(f(f(f(10))));.

My implementation below is for a function with one argument.

Questions

  1. How one should extend or replace it with a better implementation that works on multiple (or any) signatures?

  2. How to define "high precedence" of that new power operator?

  3. Is there are better way to define the "identity function" result for f ⍣ 0?

Reference links

Here is a description of APL's : "Power Operator".

( is a "star with two dots", or more formally "Apl Functional Symbol Star Diaeresis".)

Attempt

Here is an attempt of an implementation:

sub infix:<⍣>( &func, Int:D $times where $times >= 0 ) {
    if $times == 0  {
      sub func2($d) {$d}
    } else {
      sub func2($d) {
        my $res = &func($d);
        for 2..$times -> $t { $res = &func($res) }
        $res
      }
    }
}

sub plus1(Int:D $i){ $i + 1 }

say 'Using (&plus1 ⍣ 0) over 4 :';
say (&plus1 ⍣ 0)(4);

say 'Using (&plus1 ⍣ 10) over 4 :';
say (&plus1 ⍣ 10)(4);

# Using (&plus1 ⍣ 0) over 4 :
# 4
# Using (&plus1 ⍣ 10) over 4 :
# 14

(I followed this tutorial page: https://docs.raku.org/language/optut .)

Tests

The definition provided by Brad Gilbert's answer passes all of the tests below.

use Test;

sub infix:<⍣> ( &func, UInt $repeat ) is tighter( &[∘] ) { [∘] &func xx $repeat }

proto plus1(|) {*}
multi plus1(Int:D $i){ $i + 1 }
multi plus1(Bool:D $b){ $b.Int + 1 }
multi plus1(Int:D $i, Bool:D $b){ $i + $b.Int + 1 }
multi plus1(Int:D $i, Int:D $j){ $i + $j + 1 }
multi plus1(@j){ ([+] @j) + 1}
multi plus1(Int:D $i, @j){ plus1($i) + plus1(@j) - 1 }
multi plus1(%h){ ([+] %h.values) + 1 }

plan 9;

is plus1([1, 3, 5, 3]), 13, 'plus1([1, 3, 5, 3])';

is plus1(3, [1, 3, 5, 3]), 16, 'plus1(3, [1, 3, 5, 3])';

is plus1(3, True), 5, 'plus1(3, True)';

is (&plus1 ⍣ 0)(4), 4, '(&plus1 ⍣ 0)(4)';

is (&plus1 ⍣ 10)(4), 14, '(&plus1 ⍣ 10)(4)';

is (&plus1 ⍣ 10)([1, 3, 5, 3]), 22, '(&plus1 ⍣ 10)([1, 3, 5, 3])';

is (&plus1 ⍣ 3)(4, True), 8, '(&plus1 ⍣ 3)(4, True)';

is (&plus1 ⍣ 3)(3, [1, 3, 5, 3]), 18, '(&plus1 ⍣ 3)(3, [1, 3, 5, 3])';

is (&plus1 ⍣ 3)({a => 1, b => 3, c => 5}), 12, '(&plus1 ⍣ 3)({a => 1, b => 3, c => 5})';

done-testing;
like image 925
Anton Antonov Avatar asked May 01 '21 13:05

Anton Antonov


People also ask

What is an routine in raku?

Routines are one of the means Raku has to reuse code. They come in several forms, most notably methods, which belong in classes and roles and are associated with an object; and functions (also called subroutines or sub s, for short), which can be called independently of objects.

How to implement the power function without using multiplication and Division?

Given two positive integers, implement the power function without using multiplication and division operators. For example, for given two integers, x and y, pow (x, y) should return x raised to the power of y, i.e., x y. We know that pow (x, y) can be recursively written as:

How do you use lexical variables in raku?

All code objects in Raku are closures, which means they can reference lexical variables from an outer scope. Here, $y is a lexical variable inside generate-sub, and the inner subroutine that is returned uses it. By the time that inner sub is called, generate-sub has already exited.

How do you implement a power function efficiently?

Efficiently implement power function | Recursive and Iterative. Given two integers x and n where n is non-negative, efficiently compute the value of power function pow(x, n). For example, pow(-2,10) = 1024. pow(-3,4) = 81. pow(5,0) = 1. pow(-2,3) = -8. A simple solution to calculate pow(x, n) would be multiply x exactly n times.


Video Answer


2 Answers

  1. How one should extend or replace it with a better implementation that works on multiple (or any) signatures?

Raku actually has an operator that's not too far away from the APL's built in: xx, the list repetition operator. (Lists of functions are still lists, after all!). Using xx, we can define in a single line:

sub infix:<⍣>(&fn, $count) { &{($^ω, |(&fn xx $count)).reduce({$^b($^a)})} };

And then use it just as in your &plus1 example:

sub plus1(Int:D $i){ $i + 1 }

say 'Using (&plus1 ⍣ 0) over 4 :';
say (&plus1 ⍣ 0)(4);

say 'Using (&plus1 ⍣ 10) over 4 :';
say (&plus1 ⍣ 10)(4);

# Using (&plus1 ⍣ 0) over 4 :
# 4
# Using (&plus1 ⍣ 10) over 4 :
# 14

If you want to be more elaborate (supporting both monadic and dyadic functions and accepting a function as your second operand the way APL does as you mentioned), then you could expand that to something like this:


#| Monadic repetition
multi infix:<⍣>(&fn:($), $count) { 
    &{($^ω, |(&fn xx $count)).reduce({$^b($^a)})} };
#| Dyadic repetition
multi infix:<⍣>(&fn, $i) { 
    sub (|c){(|c[0], |(&fn xx $i)).reduce: -> $sum, &f { f $sum, |c[*-1]}}};

#| "until" function operand
multi infix:<⍣>(&fn1, &fn2) {
    sub ($a, $b) { given fn1($a, $b) { when .&fn2($a) { $a }
                                       default        { .&?ROUTINE($b) }}}}

sub plus1(Int:D $i, Bool:D $b) { $i + $b.Int + 1 }
say (&plus1 ⍣ 6)(1, True);                  # OUTPUT: «13»

say (&{$^b + 1 ÷ $^a} ⍣ &infix:<≅>)(1, 1);  # OUTPUT: «1.618033989»
# equivalent to  1+∘÷⍣=1 ⍝ fixpoint: golden mean.

(Note that you could expand the second multi to take functions with an arity above 2, but you'd need to decide what semantics you want in those cases. Note also that Raku has an &infix:<∘> operator, but it doesn't play the same role as APL's because it doesn't pass on the calling argument.)

The only thing this does not get us from Dyalog's power operator is the ability to provide a negative integer operand to apply the inverse of the function operand. We could write that multi, but Raku (like nearly all non-APL languages) does not create inverse functions nearly as systematically, so it doesn't seem very worthwhile.

  1. How to define "high precedence" of that new power operator?

You can specify precedence with the is tighter/is equiv/is looser precedence traits. I'm not sure exactly how high you want the precedence, but you can essentially get it as high as you want.

  1. Is there are better way to define the "identity function" result for f ⍣ 0?

This falls out naturally by defining as a reduction.

Bonus Raku/APL info:

This isn't necessary to answer your question, but seems like something you might want to know if you're interested in both Raku and APL: all Raku functions can be called in infix form, which makes them very similar to APL dyadic functions. So we could have written:

my &f = &plus1 ⍣ 6;
say 1 [&f] True;

with the same effect as say (&plus1 ⍣ 6)(1, True);.

Also, if I understand correctly, one of the ways the APL power operator is used most often is with "conditional function application" by using a Boolean operand. Raku supports a very similar idiom with the &infix:<xx> list repetition operator. So, you might have this in APL:

SquareIfNegative ← { (*∘2⍣(⍵<0)) ⍵ }

In Raku, that might be

my &square-if-negative = &{ $_² xx ($_ < 0)};
like image 190
codesections Avatar answered Oct 10 '22 23:10

codesections


TL;DR

(Too Long; Didn't Read)
This works fantastically.

sub infix:<⍣> ( &func, UInt $repeat ) { [∘] &func xx $repeat }

Repeated composition

In math, multiplication × is a lot like repeated addition +.

2 × 5   =   2 + 2 + 2 + 2 + 2

There are other ways to write that in Raku.

[+] 2,2,2,2,2
[+] 2 xx 5

Raku also has a function combinator that is a lot like function addition .
(ASCII version is just o.)

sub A (|) {…}
sub B (|) {…}
my \var = …;

A( B( var ))   eqv   (&A ∘ &B).(var)

Here's a first look at how we could use that operator with your code.

sub plus1(Int:D $i){ $i + 1 }

my &combined = &plus1 ∘ &plus1;

say combined 0; # 2

Just like we could define multiplication as actually being repeated addition.

{
  sub infix:<×> ( $val, $repeat ) {
    &CORE:infix:<×>(
      [+]( $val xx $repeat.abs ), # <--
      $repeat.sign
    )
  }

  say 2 × 5;
}

We can do the same thing for your operator, define it in terms of repeated function composition.

sub infix:<⍣> ( &func, UInt $repeat ) {
  [∘] &func xx $repeat
}

sub plus1(Int:D $i){ $i + 1 }

say (&plus1 ⍣  1)(0); # 1
say (&plus1 ⍣ 10)(0); # 10

Identity

I didn't specifically take care of the case where $repeat is 0.
It still does something sensible though.

say (&plus1 ⍣ 0)(5); # 5

That is because the no argument form of [∘]() just returns a function that just returns its inputs unchanged.

say (&plus1 ⍣ 0)('foobar'); # foobar

say [∘]().('foobar'); # foobar

Basically, the identity result already does what you want it to.


You may be wondering how [∘] … knows what to return when there are zero arguments.

say ( [∘]      ).(4); # 4

The thing is that it really doesn't.
Or rather [ ] … doesn't, but &infix:<∘> does.

.say for &infix:<∘>.candidates».signature;
# ()
# (&f)
# (&f, &g --> Block:D)

It's the same reason both of these return something sensible.

say [+]  ; # 0
say [×]  ; # 1

Precedence

The best way you would set the precedence level is to first figure out what other operator has a similar precedence level.

I'm going to define it in terms of as an example.

  • You can set it to the same precedence level with is equiv. (Also sets the associativity to be the same.)

      sub sub infix:<⍣> ( &func, UInt $repeat ) is equiv( &infix:<∘> ) {…}
    

    Note that since Raku has a lot of places where you are referring to an existing infix operator there is a shorter way to refer to them.

      sub sub infix:<⍣> ( &func, UInt $repeat ) is equiv( &[∘] ) {…}
      #                                                   ^--^
    
  • You can set it to have a looser precedence level with is looser.

      sub sub infix:<⍣> ( &func, UInt $repeat ) is looser( &[∘] ) {…}
    
  • Or you can set it to have a tighter precedence level with is tighter.
    (Makes more sense in this case since × is tighter than +, so too should be tighter than .)

      sub sub infix:<⍣> ( &func, UInt $repeat ) is tighter( &[∘] ) {…}
    

The default precedence level is the same as the + operator.


Signature

As for the signatures, just passes each result on to the next.

sub A ( \a ) {
  a + 1
}
sub B ( \a, \b ) {
  a + b
}

say A(B(4, 5)); # 10

say (&A ∘ &B).(4, 5); # 10

Let's say that A above instead expected two values, and B provided two values as a list.

sub A ( \a, \b ) {
  a + b
}
sub B ( \a, \b ) {
  a + b, 1
}

Then this line fails.
It actually fails to even compile.

say A(B(4, 5));

This line does not fail, in fact it returns the correct value

say (&A ∘ &B).(4, 5); # 10

It would also just work if you gave it multi subs.

So then overall, just using [∘] and xx works fantastically.

sub infix:<⍣> ( &func, UInt $repeat ) {
  [∘] &func xx $repeat
}

say (&plus1 ⍣ 3)(4);

Really your operator wouldn't be making such code much shorter than the code we used to implement your operator. (Only 4 characters shorter.)

say [∘](&plus1 xx 3)(4);
like image 11
Brad Gilbert Avatar answered Oct 10 '22 23:10

Brad Gilbert