ちょっと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用のシンタックスハイライトはありませんでした。