OCaml Golf 最速マスター - λx. x K S K ＠はてな

OCaml Meeting 2010 の 3 日前である本日 14:30 から，OCaml Golf Competition が開催されます．
テクニックの紹介を連載すると言いながら，全然できていなくてすみません．昨年のスライドを修正した内容を掲載します．

ユーザ定義関数・変数は1文字で

これはゴルフでは当たり前ですね．

空白・括弧の省略

バイト数を短くするには，空白の除去は必須です．除去してよいか迷ったときは「とりあえず省略して動かしてみる」というのが原則です．

if i>1then i*2else 6

のように，キーワードの直前の空白は大抵省略可能です．意外な空白も省略できるので，取りあえず消してみましょう．また，括弧についても「取りあえず消してみる」というのが有効です．

;; (ダブルセミコロン) の省略

OCaml では，文と文の間に「;;」というセパレータを入れることがありますが，これは全て省略可能です．

let f x=x+1
let g x=x*2
let()=print_int(f(g 3))

ただし，大抵のプログラムの最後の文は式の実行だけなので let 文でなく式を直書きしますが，この際には「;;」が必要です．

let f x=x+1
let g x=x*2;;print_int(f(g 3))

式同士は「;」で繋ぐので，プログラム全体で「;;」が現れるのは高々 1 回になります．また，式の中で let による束縛が必要になる場合は let ... in を使いましょう．

よく使うモジュールは open

文字列系の問題の場合，String モジュールの関数を何度も利用することがあるかもしれません．関数を2箇所以上使っていたら open するようにしましょう．

let x=... String.make ... String.sub ...

を

open String
let x=... make ... sub ...

とすれば，2Bほど稼げます．ただし，List モジュールなどのように短いモジュール名の場合は open しない方が短いこともあるので注意しましょう．また，ダブルセミコロンが増えたりして短くならない場合もあります．

原則的には if 式は禁止

返り値を必要としない if 式は，& 演算子によって短く書くことができます．

if x>0then print_string"positive"
if x=0then print_char 'O'else print_int x

は，それぞれ

x>0&()=print_string"positive"
x=0&()=print_char 'O'||()=print_int x

と書けます．& 演算子の引数は bool 型なので，unit 型の () と比較することで型を合わせています．else 節には || を使いましょう．

返り値を必要とする場合には bool 型では困るので，このテクニックは使えません．

let rec f x=if x>0then x*f(x-1)else 1;;print_int(f 10)

ただし，返り値を使う側 (上の例では print_int) の部分を関数定義に組み込んでしまえば，if 式が省略できることがあります．

let rec f x y=x>0&f(x-1)(x*y)||()=print_int y;;f 10 1

なお，else 節の部分を実行した後にエラーなどで終了してしまう場合に || が不要になることがあります．

配列を使って

if n mod 2=0then f(n/2)else f(n*3+1)

を

f[|n/2;n*3+1|].(n mod 2)

のように if 式を代用する方法もありますが非常に稀です．ただ，配列の場合は全ての要素が評価されてしまうので，

let rec f n=if n mod 2=0then f(n/2)else n*3+1

という else 節を再帰させたくない場合に，

let rec f n=[|f(n/2);n*3+1|].(n mod 2)

のようには書けないことに注意してください．

let rec は一つで十分

OCaml では相互再帰関数を let rec と and で表現できますが，相互再帰でなくても and で繋いでしまいましょう

let rec f x=...
let rec g x=...
let rec h x=...

なら

let rec f x=...
and g x=...
and h x=...

と書けます．f と g の順序を変えることで短くなることもあります．

let rec f x=...1 and g x=...();;f 3
let rec g x=...()and f x=...1;;f 3

let も節約

let による変数定義短くできる場合があります．

let x=...
let y=...

なら

let x,y=...,...

と書けます．ただし，y が x に依存する場合はこのような変更はできません．

Printf, Scanf の利用

文字列の扱いに弱い (ゴルフ的にコード量が多い) 言語である OCaml において，入出力の際にさまざまな処理ができる Printf, Scanf モジュールが有効です．マニュアルをざっと眺めておくとよいでしょう．

中置演算子のユーザ定義の利用

このテクニックは多くの問題で有効です．OCaml では，一部の記号 (列) を中置演算子として利用することができますが，ゴルフでは重要な機能の一つです．先ほど定義した階乗を計算して表示する関数なら，

let rec($)x y=x>0&x-1$x*y||()=print_int y;;10$1

となり，括弧や空白が省略できて 6B も少なくなります．この例では ($) を使いましたが，(@) や (^) が使われることも多いようです．OCaml では先頭の記号によって優先順位が決まるので，問題ごとに使い分けるとよいと思います．ちなみに，優先順位は高い方から順に以下のようになっています．

! や ~ などの前置演算子 
関数適用     (L)
コンストラクタ
-, -.
**           (R)
*, /, %, mod (L)
+,-          (L)
::           (R)
@, ^         (R)
=, <, >, $   (L)
not
&, &&        (L)
or, ||       (L)
,
<-, :=       (R)
if
;            (R)

L や R は左優先か右優先かを表しますが，ゴルフではこれも重要だったりします．他のところで使わない演算子であれば，(+)だろうと(-)だろうと何でも上書きしてしまいましょう．

また，(!) を使った前置演算子が有効な場合もあります．たとえば

let(!)=Char.chr;;Printf.printf"%c%c%c"!107!115!107

は，

let f=Char.chr;;Printf.printf"%c%c%c"(f 107)(f 115)(f 107)

と比べると，括弧も空白も省略できて大幅にバイト数を減らせることがよくわかります．

なお，前置演算子を 2 引数関数に利用したり，中置演算子を 3 引数関数に利用したりすることで短くなることもあります．

let f x y z=x+y+z;;f 1 2 3
let($)x y z=x+y+z;;(1$2)3

再帰 vs. ループ

OCaml では繰り返しの処理を let rec や for / while ループで表現できますが，原則的には以下のように使い分けができます．

記憶する変数が多いときには let rec
繰り返し回数が決まっていれば for
(エラーが出るまで) 無限に繰り返したい場合は while

といった具合です．ただし，これはあくまで「原則」なので，とりあえず試してみて短いものを選ぶのがよいと思います．let rec を使った場合には中置演算子の利用を考慮できることを忘れずに．

また，再帰やループの終了条件を書く代わりにエラーを利用して強制的に終了させるテクニックも有効です．

let rec f x=print_int x;x>0&f(x-1)
let rec f i=print_char"hoge".[i];x>0&f(x-1)

は，それぞれ，

let rec f x=print_int x;f(x-x/x)
let rec f i=print_char"hoge".[i];f(x-1)

と書けます．1 つめは 0 除算によるエラー，2 つめは文字列への不正アクセスによるエラーを利用して終了しています．また，標準入力に対する eof エラーによる強制終了も有効です．

while 0=0do print_endline(read_line())done

オプショナル引数の利用

オプショナル引数はゴルフのために OLabl に取り込まれ，その後 OCaml に追加されました．というのは嘘ですが，そういっても過言ではないくらい重要なテクニックの一つです．関数内でローカル変数を定義したい場合に有効です．たとえば，

let f x=let y=read_int()in ...

という関数定義は，

let f?(y=read_int())x=...

と書けます．y が x に依存する場合は，

let f x?(y=read_int())_=...

のように無理矢理 2 引数関数にしてしまうと短くなるかもしれません．さらに，f を中置演算子にできる余地も出てくるでしょう．

その他のテクニック

手抜きですみませんが，その他のテクニックについては昨年の OCaml Meeting で発表したスライドが参考になれば幸いです．

さいごに

これは，あくまでゴルフ向けのテクニックです．OCaml で普通のプログラミングをしたいときにこれらを使うのは絶対にやめましょう．複数人でのプロジェクトなどで多用すると間違いなく嫌がられるのでご注意を．