A heap queue in Dyalog APL

Question

I am learning Dyalog APL. I implemented a binary heap, which seems to work. How could I make it look more like APL (and less like Python)?

⎕io←0
heappush←{(⍺,⍵)siftdown 0(≢⍺)}

heappop←{
 heap←⍵
 last←⊃¯1↑heap ⋄ rest←¯1↓heap
 0=≢rest:rest last
 r←heap[0]
 (((last@0)rest)siftup 0)r
}

siftdown←{
 heap←⍺
 start pos←⍵
 item←pos⌷heap
 newpos←{
  ⍵≤start:⍵
  parentpos←⌊(⍵-1)÷2
  parent←parentpos⌷heap
  item<parent:∇ parentpos⊣heap[⍵]←parent
  ⍵
 }pos
 (item@newpos)heap
}

siftup←{
  heap←⍺
  p←{
   pos←⍵
   chp←1+2×pos
   chp≥≢heap:pos
   rpos←1+chp
   chp←((rpos<≢heap)∧~heap[chp]<heap[rpos])⊃chp rpos
   heap[pos]←heap[chp]
   ∇ chp
  }⍵
  heap[p]←⍺[⍵]
  heap siftdown ⍵ p
 }

heap←0 1 2 5 6 8 9
heappop heap

┌→────────────────┐
│ ┌→──────────┐   │
│ │1 5 2 9 6 8│ 0 │
│ └~──────────┘   │
└∊────────────────┘

heap heappush 3
┌→──────────────┐
│0 1 2 3 6 8 9 5│
└~──────────────┘

Answer 1

How could I make it look more like APL (and less like Python)?

Assuming you mean "in a more functional and less imperative way" by this line,

I don't think you can largely achieve that, for a good reason.

Basically, the array-based heap (and other common algorithms you see on algorithm textbooks) is designed for imperative languages. Translating it into a language whose main strength isn't imperative makes the code feel awkward and unfitting. It may also lead to code whose time complexity is actually worse than designed. See how it looks like when a similar algorithm is written in Haskell.

APL is not 100% functional, but definitely is more functional than imperative (especially when you mainly use dfns). If you want, search for "functional algorithms" and try implementing those. In the case of a heap, leftist tree isn't too complex, and supports one more \$O(\log n)\$ operation (heap merge) compared to an imperative binary heap. You can check out a nice illustration too.

But you can still improve some parts of the code.

Improvement in the algorithm

• Use ⎕IO←1 instead.

Array-based heap uses 0-based indexing by default, so the parent-child relationship is slightly awkward:

$$ \begin{align} \text{left child}&=1+2\times\text{parent} \\ \text{right child}&=2+2\times\text{parent} \\ \text{parent}&=\Bigl\lfloor \frac{\text{child} - 1}2 \Bigr\rfloor \end{align} $$

If you use 1-based indexing instead, it becomes slightly cleaner:

$$ \begin{align} \text{left child}&=2\times\text{parent} \\ \text{right child}&=1+2\times\text{parent} \\ \text{parent}&=\Bigl\lfloor \frac{\text{child}}2 \Bigr\rfloor \end{align} $$

I don't have other better ideas to utilize the strengths of APL, due to the underlying algorithm being purely imperative.

General tips for writing APL code

• Let the right argument of dyadic functions be the primary one (i.e. the heap).
• If you see a negation of a comparison (e.g. ~heap[chp]<heap[rpos]), use a single equivalent function (e.g. heap[chp]≥heap[rpos]).
• Prefer concatenation (e.g. 0,≢⍺) over stranding (e.g. 0(≢⍺)) when you concatenate two scalars.
• Try not to modify existing variable's contents (e.g. avoid chp←((rpos<≢heap)∧~heap[chp]<heap[rpos])⊃chp rpos which refers to chp and then modifies it) when it isn't essential in implementing the algorithm. Try to choose a separate and meaningful name instead.
• Parenthesize stranding assignments (e.g. (start pos)←⍵ instead of start pos←⍵).
• Consider following a naming convention, and a little more descriptive names. (e.g. I can't easily see what chp stands for.)
• Consider adding comments to each function which briefly describe the input(s) and the output.