Re: [Bug-apl] Tree Traversal in gnu-apl

[Rowan Cannaday]

btw not correct, but at least its valid apl, which is a start.

On Thu, Oct 10, 2019 at 12:34 PM Rowan Cannaday <address@hidden> wrote:

Thank you Jürgen.

I found translating the late John Scholes APL videos on youtube from dyalog specific syntax to gnu-apl helpful.

For example, here is his "naive" algorithm for counting all the leaf nodes in a tree:

      dfs ← {⊃∇⍨/⌽(⊂⍺ ⍺⍺ ⍵),⍺ ⍵⍵ ⍵}

      0 {⍺+0=≡⍵} dfs {(0=≡⍵)↓,⍵} (1 2)(3 4)
4

I had a longer write up, but I seem to have solved it whilst troubleshooting.

Here is the translation if anybody else is interested:

      dfs ← {⊃(⍶ {⍺(⍶ dfs ⍹)⍵} ⍹)/⌽(⊂⍺ ⍶ ⍵),⍺ ⍹ ⍵}
      0 ({⍺+0=≡⍵} dfs {⍺⊢(0=≡⍵)↓,⍵}) (1 2)(3 4)
4

It seems dyalog does some implicit argument passing with the '∇'operator, as well seems to be less stringent than gnu-apl with regards to uninitialized arguments (needing '⍺⊢' in right operator function). No complaints by me, I prefer explicit to implicit.

I will likely continue on with this at some point, so don't be surprised if I use this thread as a journal.

- Rowan

On Thu, Oct 10, 2019 at 11:22 AM Dr. Jürgen Sauermann <mail@jürgen-sauermann.de> wrote:

Hi Rowan,

not sure if it helps, but the term accumulator makes me think of the reduction
operator rather than the rank operator:

      {⍺,1+⍵} / 1 2 3
 1 3 5

Not sure, though what you want to compute.

The syntax of the rank operator in the ISO standard is IMHO broken. The syntax:

Z←f ⍤ y B

has a rather ambiguous right argument j B with no rules as to where j end and B begins.
For example:

Z←f⍤1 2 3 4 5

could mean:

j = 1 and B = 2 3 4 5   or:
j = 1 2 and B = 3 4 5   or even:
j = 1 2 3 and B = 4 5

GNU APL uses some crude rules to resolve such cases, but in order
to get a predictable result, you need to properly use parentheses like this:

Z←(f⍤1) 2 3 4 5

or, as a cleaner though non-standard alternative syntax, make j an axis argument:

Z←f⍤[1] 2 3 4 5

It is very difficult to get all that right, therefore I never use ⍤.

Best Regards,
Jürgen Sauermann

On 10/9/19 9:44 PM, Rowan Cannaday wrote:

this seems to be behaving much better:
      foo ← {⍺,{((1+1↑⍵) foo 1↓⍵)}⍣(~0=⍴⍵)⊢⍵}
      ⍬ foo 1 2 3
2 3 4
      5 4 3 foo 1 2 3
5 4 3 2 3 4

On Wed, Oct 9, 2019 at 3:40 PM Rowan Cannaday <address@hidden> wrote:

somebody pointed out that the previous fn was failing because i wasn't calling 'foo' w/ dyadic arguments in the inner dfn

On Wed, Oct 9, 2019 at 2:16 PM Rowan Cannaday <address@hidden> wrote:

interestingly enough this is ok:
      foo ← {⍬{⍺,(1+1↑⍵),(foo 1↓⍵)}⍣(~0=⍴⍵)⍵}
      foo 1 2 3
2 3 4

but this isnt:
      foo ← {⍺{⍺,(1+1↑⍵),(foo 1↓⍵)}⍣(~0=⍴⍵)⍵}
      ⍬ foo 1 2 3
VALUE ERROR
foo[1]  λ←⍺ λ1⍣(∼0=⍴⍵)⍵
          ^
      ⎕CR 'foo'
λ←⍺ λ1 ⍵                        
λ←⍺{⍺,(1+1↑⍵),(foo 1↓⍵)}⍣(~0=⍴⍵)⍵

On Wed, Oct 9, 2019 at 1:29 PM Rowan Cannaday <address@hidden> wrote:

making progress...

      foo ← {{(1+1↑⍵),(foo 1↓⍵)}⍣(~0=⍴⍵)⍵}
      foo 1 2 3
2 3 4

On Wed, Oct 9, 2019 at 12:47 PM Rowan Cannaday <address@hidden> wrote:

this is a slightly better way of writing my (still broken) accumulator:
acc←{⍺{⍺ acc 1↑⍵}⍣(0=⍴⍵)⊢⍵}

On Wed, Oct 9, 2019 at 12:40 PM Rowan Cannaday <address@hidden> wrote:

Given a recursive factorial definition:
fact←{{⍵ × fact ⍵-1}⍣(⍵>2)⊢1⌈⍵}

[written by Kacper Gutowski in the 'Recursive Lambda' thread]

I am attempting to write a basic accumulator. This should take an empty vector as the left value argument, and a rank 1 array as the right value argument.

Every iteration it should drop a value from the right value, and append it to the left, until the right value is an empty vector.

I thought I'd be able to do something like the following:

acc←{⍺,{acc 1↑⍵}⍣(0=⍴⍵)⊢⍵}
⍬ acc 1 2 3

But modifying this to say, add a 1 to every number, still returns the input vector ⍵.

Thoughts?

On Fri, Sep 27, 2019 at 3:44 PM Rowan Cannaday <address@hidden> wrote:

Hello y'all.

I have been attempting to learn function composition & higher-order functions in gnu-apl, and how to use it to perform tree traversal.

https://en.wikipedia.org/wiki/Function_composition_(computer_science)#APL
https://en.wikipedia.org/wiki/Higher-order_function#APL
https://rosettacode.org/wiki/Tree_traversal#APL

Unfortunately a lot of the syntax used is dyalog & dfn specific, so working out some of the examples is a bit tricky for myself.

(the main inconsistencies are '∇' as a recursive function definition, ⍺⍺ & ⍵⍵ to refer to left and right operands, '@' as the 'at' operator, '⍣' operator differences, as well as possibly others).

Has anybody done 'idiomatic' tree traversal in gnu-apl? Does anybody use primitive composition functions in their code?

Trying to figure out what works and feels natural in the language. Any examples or guidance would be appreciated.

Examples:

Higher order fns in gnu-apl:
∇Z ← (L twice) B
    Z ← L L B
∇

∇Z ← plusthree B
    Z ← B + 3
∇

∇Z ← g B
    Z ← plusthree twice B
∇