APLでクイックソート

ちょっとAPLなんていう言語を見つけて、その見た目に惹かれたので、勉強がてらクイックソートを実装してみようと思います。

入門のページを1個か2個程度は読んで、`f←{⍵}`くらいの関数の定義くらいは知っているものとして進めます。僕がそのレベルですので。

# 実行環境

WindowsのNARS2000を使いました。
http://www.nars2000.org/download/

# 文法

クイックソートに必要な記法を確認します。

##  並べる

`n`、`m`を配列でない整数値、`n/m`とすると、`n`を`m`個並べます。

```
入力：      3 / 4
出力：4 4 4  
```

## 乱数
`? n` とすると $[1,n]$ からランダムに整数を１つ得ます。

```
入力：      ?6
出力：3
```

配列に対して行うとそれぞれの要素に対して乱数を得て、同次元の配列を返します。

```
入力：      x ← ? 20 / 100
```
以降、この配列`x`を使って遊びます。

```
入力：      x
出力：26 18 95 3 14 59 42 9 64 95 98 98 4 73 56 100 39 7 65 87 
```
## 要素の取り出し

よくある`x[i]`か、squad演算子`i⌷x`を使います。Fortranと同じく`1`オリジンです。
IO用のquad演算子`⎕`と混同しないように注意しましょう。
`i`として空集合を渡すと`x`をそのまま返します。

```
入力：      x[1]
出力：26 
入力：      3⌷x
出力：95
入力：      x[]
出力：26 18 95 3 14 59 42 9 64 95 98 98 4 73 56 100 39 7 65 87 
```
## 比較演算子

普通の`>`などですが、FortranやNumpyのようにブロードキャストされます。

```
      x > x[1]
0 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1
```

## マスク

並べるときの`/`について、`L/R`としたとき、`L`がbool値（0, 1）の配列で、`R`が配列のとき、`L`が`1`の要素を抽出した配列を取り出すことができます。
`L`と`R`は同じshapeを持つ必要があります。

```
      (x>x[1])/x
95 59 42 64 95 98 98 73 56 100 39 65 87 
```

この例では`x`から`26`より大きい要素を取り出して配列として得ました。

これも数を並べる方の演算子としてブロードキャストされていて、
０のところでは要素を０個並べ、１のところでは要素を１個並べるとしているので、
１のところの要素だけを抽出出来たのではないかと思います。

ということで試してみました。

```
      a ← ⍳ 4
      a
1 2 3 4
      a/a
1 2 2 3 3 3 4 4 4 4
```

やっぱり。

## 要素の個数

`≢x`とすると、(多分)要素数を返します。`⍴x`もあるのですが、こちらはnumpyで言うところの`shape`タプルを返します。

```
      ≢x
20
```

今回の１次元配列のソートではどっちでもいいです。

## ベクトルの結合

`,`か`⍪`があり、ベクトルか行列で違うのですが、今回はどっちでもいいです。

```
      (3/4),(5/6)
4 4 4 6 6 6 6 6
```

## 条件分岐

関数の中でしかできませんでした。

```
      f ← {⍵:"true"⋄"false"}
```

として定義してやると、

```
      f 0
false
      f 1
true
```

という感じで条件分岐ができます。正直`:`と`⋄`の詳細は知らないままやっています。
ちなみに、この`f`に負または２以上の数を渡すと`DOMAIN ERROR`になります。

## 交換子

`f`を演算子、`L,R`を変数として、`Lf⍨R`は`R f L`となります。
今回は括弧の数を減らすために使いました。

# 実装開始

最低限の部品は揃ったので、実装を始めます。

## 対象

まず、並べる対象の配列は上の文法で出てきた`x`です。

```
      x
26 18 95 3 14 59 42 9 64 95 98 98 4 73 56 100 39 7 65 87 
```

## マスク関数

要素数が１より多ければ、最初の要素より大きい要素を取り出していく関数を作ります。
そうでなければそのまま返すとします。

```
      f ← {1<≢⍵:(⍵>⍵[1])/⍵⋄⍵}
```

```
      x
26 18 95 3 14 59 42 9 64 95 98 98 4 73 56 100 39 7 65 87 
      f x
95 59 42 64 95 98 98 73 56 100 39 65 87 
      f f x
98 98 100 
      f f f x
100 
      f f f f x
100
``` 

ここで交換子`⍨`を使うと、`(⍵>⍵[1])/⍵`が`⍵/⍨⍵>⍵[1]`と書けるので、丸括弧が１つ減ります。

```
      f ← {1<≢⍵:⍵/⍨⍵>⍵[1]⋄⍵}
```

## 結合関数

続いて、ひとつ目の要素を取り出し、それより小さいもの、同じもの、大きいものという３つの配列を作り、それを結合して同じサイズの配列を返す関数を作ります。


```
      g ← {(⍵/⍨⍵<⍵[1]),(⍵/⍨⍵=⍵[1]),(⍵/⍨⍵>⍵[1])}
```

`g`の中の丸括弧３つが、小同大それぞれの配列に対応しています。これを`,`で結合しています。

```
      x
26 18 95 3 14 59 42 9 64 95 98 98 4 73 56 100 39 7 65 87 
      g x
18 3 14 9 4 7 26 95 59 42 64 95 98 98 73 56 100 39 65 87 
      g g x
3 14 9 4 7 18 26 95 59 42 64 95 98 98 73 56 100 39 65 87 
      g g g x
3 14 9 4 7 18 26 95 59 42 64 95 98 98 73 56 100 39 65 87 
```

クイックソートのピボット選択１回に相当しますね。

## クイックソート関数

あとは、`g`の丸括弧のうち、小さいもの、大きいものを再帰的にソートするようにすればよいです。

僕の書き方では以下のようになりました。

```
      q ← {1<≢⍵:(q ⍵/⍨⍵<⍵[1]),(⍵/⍨⍵=⍵[1]),(q ⍵/⍨⍵>⍵[1])⋄⍵}
```

ちゃんと昇順にならびました。

```
      q x
3 4 7 9 14 18 26 39 42 56 59 64 65 73 87 95 95 98 98 100 
```

# 参考

1980年頃に日立がその生産性について、COBOLと比較している記事を見かけました。
http://www.hitachihyoron.com/jp/pdf/1980/12/1980_12_15.pdf

ライフゲームを実装。条件分岐なしで書けるとは。
https://www.youtube.com/watch?v=a9xAKttWgP4

APLのクイックソートはこちらにもあります。
https://www.dyalog.com/blog/2014/12/quicksort-in-apl/

APLの単項・二項演算子の表。
http://sheet.shiar.nl/apl


# その他

案の定QiitaにAPL用のシンタックスハイライトはありませんでした。