2010/8/28(土) に開催された OCaml Meeting 2010 in Nagoya の簡単な参加メモとその中のイベントである Golf コンテストの解説というか思考の軌跡についてである。プログラム、発表者については公式サイトを参照のこと。

やってみようOCaml

OCaml の紹介セッション。帰りの電車で少し話をさせて頂いたのだが、初学者向けのセッションも 1 つは入れよう、という位置づけのセッションだったそうである。が、そもそも会場に初学者がほとんど居なさそうな感じでイベントの性格を表していたような気がする。ただこれも帰りの電車での話だが、新しい人が入ってこないとコミュニティが広がって行かないというのはその通りである。OCaml ユーザーは比較的狭いコミュニティで顔見知りが多いとも言われていたが、その場合、しばしば逆に外からは入りにくかったりする。自分も C++ → template → 関数型 → OCaml と来て大学とか会社とかのバックグラウンドなしで来ている人間である。GC 本読書会に参加しているので CSNagoya の人とは顔見知りという点でまだ救われているが。ということで、OCaml に興味があるけど知人が居ないという方、仲良くしましょう(ここだけ敬体)。

内容については、題材的には Twitter の bot というのは興味を引きやすいネタだったかと。レベルについては正直良く分からなくて本当の初学者の人は付いて来られていないかもしれない。いっそのこと Golf のネタで全く短縮していない素直なコードを作るところまで、を導入セッションにするというのも良いかもしれないとも思う。

F# の流技

OCaml.NET とも言われる F# について。ぶっちゃけ VS2010 入れたまま放置だったりするが。パイプライン演算子(|>)をネタに型推論を絡めつつ。なかなか面白かった。だが、F# にまで手を出してる余裕はないか。

OCaml 3.12における第一級モジュールと合成可能なシグネチャについて

3.12 の目玉として盛んに言われていた第一級モジュールについて。かなり興味を引かれていたのだがハイレベル過ぎて付いていけず。雰囲気は分かるかも、くらい。そもそも Functor の辺りから自体ちゃんと理解していないし。一度じっくり勉強したいところではある。

デザインレシピ、モジュール、抽象データ型

「プログラミングの基礎」著者のセッション。内容としては「プログラミングの基礎」に書かれている話なので略。この本は OCaml の勉強だけでなくプログラミング一般に対して学ぶ上での良本なので文法を学んでもうまくコーディングできないという人は是非購入をお勧めする。

Spot Your White Caml

OCaml 使って働く上での心構えとツール紹介といった感じか。ツールとか語れるレベルまで常用してないので具体的なコメントはしない。

OCaml でプログラミングコンテスト

どのコンテストだろうかと思ったら ICFP だった。ほとんど名前ぐらいしか聞いた事が無くて噂に聞くレベルでは凄いコンテストっぽいと思っていたが本当に凄かった。とりあえず内容を知って参加しようと思えるだけで既にレベルが違う気がする。

LT: FFTW/genfft誰得ハッキングガイド

正に誰得。だが OCaml on Windows の秘密、とかで FlexDLL 関連のネタとかどうだろうとか考えていた自分には何とも言えないところ。

LT: OCaml版Hoogle、OCamlAPISearchの紹介

記号を含む検索でぐぐるさんが頼りにならない現状、非常に素晴らしいかと。後はモジュールの追加・登録ができればよいと思う。もちろんローカルで立てれば自由ではあるのだが。

LT: どーOCaml

これも(ネタとして)素晴らしい。自分には関数型言語のバックグラウンドがないし、言語としては、なまじっか破壊的に書けたり自由度が高いので、OCaml 的にはどう書くのがいいのか悩む時がある(ほとんど OCaml でコード書かないけど)。ということでエキスパートの人はばんばんコード例を追加して欲しい。

LT: ゴルフ用楽打モジュール

ゴルフとしてこの辺があると嬉しい、というのはすごい良く分かるのだが実際のユースケースがよく分からない。どうせコピペして埋め込んだ上でさらに短縮するんだろ、という気が。

Golf

ということで本記事のメインネタ、Golf である。問題と結果はここ。簡単に説明すると改行区切りの単語リストを入力としソートしたリストを出力。ただしソートは文字数でまず比較し、同一文字数の場合に文字コード順で比較する、という問題。結果は 全体 9 位、出席者中 3 位。で、どういう思考の元こういうコードになったかを解説してみようと思う。なお、単調減少しているかのように書くがその裏で試行錯誤しまくっているのでその点は注意。ちなみに自分は他言語においても Golf はしないし(前回の OCaml Meeting 以来)、上でも書いているが OCaml も常用していないレベルなので普通の人でも Web 上の資料のみで全然余裕のはず。当然、中野さんの資料、OCaml Meeting 2009とOCaml Golf 最速マスターは必修である。

さて、まず最初の方針として、自前でソート用比較関数を書くと長くて話にならないだろうから書かない。じゃ、どうするかというと (単語の文字数, 単語自体) の tuple を作って Pervasives.compare 等を使ってソート、その後 tuple の 2 項目目を出力する。この段階で「そんなの思いつくのは無理ゲーじゃないのか」と思った人もいるかもしれないが、自分にとっては割と自然だった。なぜなら、Perl のシュワルツ変換(Schwartzian Transform)というイディオムを知っていたからである。ソートする時にキーの算出コストが高い場合などに使う技法で多分ラクダ本とかにも載っていたと思う。今回のに合わせて簡単に例を書くとこんな感じになる。

map { $_->[1] } # 単語の取り出し
sort { $a->[0] <=> $b->[0] || $a->[1] cmp $b->[1] } # (1)
map { [ length($_), $_ ] } # [単語の文字数, 単語自体]となるリストの生成
@words # 単語のリスト
# (1) 比較関数を渡してソート。$a $b が比較関数に渡される要素。
#     <=>, cmp は a<b なら負、a=b なら 0、a>b なら正を返す演算子の数値比較版と文字列比較版。
#     ->[0], ->[1] は 0 番目の要素、1 番目の要素へのアクセスである。
#     なお、|| は C/C++ と違って 0,1 only にはならない(0 || -1 は -1 になる)

どうだろうか。ほぼ上述の「最初の方針」と同じことをやっているのが分かるだろうか。この基本方針を元に最初の稼働例(多分)を書いたのが以下になる。

let _=let r=ref[]in(try[while 1>0 do let p=read_line()in r:=(String.length p,p)::!r done]with _->List.map(fun(_,x)->print_endline x)(List.sort compare!r))

先頭の let _= とか、while を囲む [] とか意味のないコードがあるがとりあえず動作はする(はず)。while で無限ループしつつ、(単語の文字数, 単語自体) の tuple のリストを r に蓄積していき例外(実際には End_of_file になるが _ で受ける)を受けたら、ソートと出力を行う。特に難しいところはないはずである。とりあえず while ループは向いてなさそうなので再帰関数で書き直してみる。

let _=let rec f l=try let p=read_line()in f((String.length p,p)::l) with _->l in List.map(fun(_,x)->print_endline x)(List.sort compare (f[]))

資料に基づき変数束縛をオプション引数に移すとこうなる。この時点でようやく先頭の let _= が不要だという点に気付いている。

let rec f?(p=read_line())l=(String.length p,p)::try f l with _->l in List.map(fun(_,x)->print_endline x)(List.sort compare(f[]))

try の位置が関数呼び出しに移動し、かつ、結果を蓄積するために使っていた l が使われていない点に注意。ただしオプション引数を末尾に置くと省略できないので l は残してある。

再度、資料に基づき演算子化するとこうなる。

let rec(!)?(p=read_line())l=(String.length p,p)::try(!l)with _->l in List.map(fun(_,x)->print_endline x)(List.sort compare![])

open List して split 使ってみたのが以下。

open List;;let rec(!)?(p=read_line())l=(String.length p,p)::try(!l)with _->l in map print_endline(snd(split(sort compare![])))

(a,b)::l より [a,b]@l の方が(効率が悪いが)文字数が少ない点、かつ l を使っていないなら [] でも () でもなく(文字数が少ないので) 0 を渡せばいいじゃないというのを反映させたものが次。

open List;;let rec(!)?(p=read_line())l=[String.length p,p]@try!0with _->[]in map print_endline(map snd(sort compare!0))

let in 使う必要がないってのが次。

コード1

open List
let rec(!)?(p=read_line())l=[String.length p,p]@try!0with _->[];;map print_endline(map snd(sort compare!0))

これで 117 byte で最終回答と同じ。ここからも試行錯誤しているのだがより良い解を出すのに有効な方法(で活用できなかったもの)だけ挙げる。とりあえず自分で考えている分には無理そうだったので他の問題の回答を眺めてみる。有用そうな技法として map の演算子化と Sort.list の利用が見つかった(何度も言うが裏ではもっと試行錯誤している)。

map の演算子化をしてみたのが次で、117 byte。

コード2

open List
let rec(!)?(p=read_line())l=[String.length p,p]@try!0with _->[]and(&)=map;;print_endline&snd&sort compare!0

Sort.list を使ってみたのが次で、やっぱり 117 byte。ちなみに補足しておくと open List しているので sort compare!0 と Sort.list(<)!0 の文字数差はない。これが !0 でなく a だったりすると区切りの空白が必要となり sort compare a と Sort.list(<)a となって Sort.list の方が短くなる。さらに言えば仕様上は (<=) を渡すのが正しいはずだが同一単語がないので (<) で良く 1 文字短縮できている。

コード3

open List
let rec(!)?(p=read_line())l=[String.length p,p]@try!0with _->[];;map print_endline(map snd(Sort.list(<)!0))

この辺で呪われてるの？って感じであと少し試行錯誤して諦めてしまったのだが材料自体は既にそろっていたわけでちゃんと組み合わせて試行錯誤しておくべきだったというところか。open List 削除まで思い至らなかったところが大きな敗因の一つかもしれない。で、コード 1～3 を統合し open List を削除してやると次のようになり kinaba さんのコードと等価になる。

let rec(!)?(p=read_line())l=[String.length p,p]@try!0with _->[]and(&)=List.map;;print_endline&snd&Sort.list(<)!0

この記事で多少なりとも OCaml Golfer の拡大に貢献できればこれに勝る喜びはない。自分は Golf しないけど。