Leftist Tree in Dyalog APL -- can it be made more compact/idiomatic?

Question

Following great feedback given in response to my previous question, I was encouraged to consider a different type of heap structure, the Leftist Tree. It lends itself better to a functional implementation. It's already shorter, but is there anything else I should consider in order to make this more idiomatic APL? Many thanks.

⍝ APL implementation of a leftist tree.
⍝ 
⍝ https://en.wikipedia.org/wiki/Leftist_tree
⍝ http://typeocaml.com/2015/03/12/heap-leftist-tree/

⎕io←0
Insert←{ ⍝ Insert item into leftist tree, returning the resulting tree
    (tree item)←⍵
    1 item ⍬ ⍬ Merge tree 
}

Pop←{ ⍝ Pop off smallest element from a leftist tree
    0=≢⍵:⍬
    (v l r)←1↓⍵                 ⍝ value left right
    (l Merge r) v               ⍝ Return the resulting tree and the value
}

Merge←{ ⍝ Merge two leftist trees, t1 and t2
    t1←⍺ ⋄ t2←⍵
    0=≢t1:t2 ⋄ 0=≢t2:t1                          ⍝ If either is a leaf, return the other
    (key1 left right)←1↓t1 ⋄ key2←1⌷t2
    key1>key2:t2∇t1                              ⍝ Flip to ensure smallest is root of merged
    merged←right∇t2                              ⍝ Merge rightwards
    (⊃left)≥⊃merged:(1+⊃merged) key1 left merged ⍝ Right is shorter
    (1+⊃left) key1 merged left                   ⍝ Left is shorter; make it the new right
}

⍝ Example heap merge from http://typeocaml.com/2015/03/12/heap-leftist-tree/
h←Insert ⍬ 2
h←Insert h 10
h←Insert h 9

s←Insert ⍬ 3
s←Insert s 6

h Merge s
┌→─────────────────────────────────────────────────────────────┐
│     ┌→────────────────────────────────────┐ ┌→─────────────┐ │
│ 2 2 │     ┌→────────────┐ ┌→────────────┐ │ │      ┌⊖┐ ┌⊖┐ │ │
│     │ 2 3 │     ┌⊖┐ ┌⊖┐ │ │     ┌⊖┐ ┌⊖┐ │ │ │ 1 10 │0│ │0│ │ │
│     │     │ 1 6 │0│ │0│ │ │ 1 9 │0│ │0│ │ │ │      └~┘ └~┘ │ │
│     │     │     └~┘ └~┘ │ │     └~┘ └~┘ │ │ └∊─────────────┘ │
│     │     └∊────────────┘ └∊────────────┘ │                  │
│     └∊────────────────────────────────────┘                  │
└∊─────────────────────────────────────────────────────────────┘

Answer 1

I think your code generally looks good.

Comments

I recommend annotating functions with what the structure of their argument(s) and result are, especially when not just simple arrays, at the top of the function, rather than relying on code comments to reveal this.

Take benefit of dyadic functions

If you define Insert and Pop as dyadic functions both code and usage can be simplified. You can even let ⍬ be the default left argument, allowing easy initialisation of a tree.

Insert←{ ⍝ Insert item ⍵ into leftist tree ⍺, returning the resulting tree
    ⍺←⍬              ⍝ default to init
    1 ⍵ ⍬ ⍬ Merge ⍺ 
}

h←Insert 2
h Insert←10
h Insert←9

s←Insert 3
s Insert←6

Full variable names or not?

This is a personal style thing. Some people prefer mathematical-looking single-letter variables, others like full variable names that obviate comments. However, at least be consistent. (I've also moved the first element of ⍵ to become ⍺, as per above.)

Pop←{ ⍝ Pop off smallest element from a leftist tree
    0=≢⍺:⍬
    (value left right)←⍵
    (left Merge right) value
}

Unnecessary naming

⍺ and ⍵ are well understood to be the left and right arguments. I don't think renaming them t1 and t2 brings much, other than the ability to create matching keyN variables. However, here you only ever use key2 once, and its definition is very simple, and in fact as short or shorter than any appropriate name, so you might as well use it inline, freeing up key to only apply to ⍵:

Merge←{ ⍝ Merge leftist trees ⍺ and ⍵
    0=≢⍺:⍵ ⋄ 0=≢⍵:⍺                              ⍝ If either is a leaf, return the other
    (key left right)←1↓⍺
    key>1⌷⍵:⍵∇⍺                                  ⍝ Flip to ensure smallest is root of merged
    merged←right∇⍵                               ⍝ Merge rightwards
    (⊃left)≥⊃merged:(1+⊃merged) key left merged  ⍝ Right is shorter
    (1+⊃left) key merged left                    ⍝ Left is shorter; make it the new right
}

Answer 2

APL-specific

Keep the nesting levels consistent

At this line:

(key1 left right)←1↓t1 ⋄ key2←1⌷t2

key1 is effectively disclosed one level, while key2 is not. It doesn't matter in this code because both key1 and key2 are assumed to be scalars, but they are semantically different:

    ⍝ Assume ⎕IO←1
    (a b c)←nested←(1 2 3)(4 5 6)(7 8 9)
    1 2 3≡a
1
    (⊂1 2 3)≡1⌷nested
1
    1 2 3≡1⊃nested
1

Semantically correct one would be key2←1⊃t2 instead.

---

General tips

Give a name to algorithm-wise important constant(s)

In this code, ⍬ is being used to signify the empty heap. It appears in Insert and Pop, and is also used as the initial heap in the testing code. You can give it a meaningful name:

empty←⍬

That way, you can make several parts of the code easier to understand, and you can even write empty≡t1:... to test if a (sub-)tree is empty, instead of a roundabout way 0=≢t1:....

Name meaningful intermediate values

At the bottom of Merge:

    (⊃left)≥⊃merged:(1+⊃merged) key1 left merged
    (1+⊃left) key1 merged left

Both ⊃left and ⊃merged are used twice in the code, and both have a good meaning -- the rank of the corresponding tree. We can name both:

    leftRank←⊃left ⋄ mergedRank←⊃merged
    leftRank≥mergedRank:(1+mergedRank) key1 left merged
    (1+leftRank) key1 merged left

Check the time complexity of your function

Algorithm is all about correctness and performance. If you checked that your implementation gives correct results, the next step is to measure its time complexity. Dyalog APL provides multiple ways to measure it:

• dfns.time, dfns.cmpx, and dfns.profile
• User commands ]runtime and ]profile (IIRC)

Learn how and when to use them.