Zenn
🕌

Standard MLでAtCoderを始める

2021/01/05に公開
AtCoder
sml
Standard ML
tech

はじめに

この記事はStandard ML (SML) でAtCoderを始めてみようと考えている人のための記事です。最初に言っておくと、タイトルは壮大な感じですが、2021年1月5日時点では、SML環境の構築と標準入力についてしか記載していません。気が向いたら、もうちょっと書こうかなと思っています。

また、fetburnerさんのAtCoderに登録したら解くべき精選過去問10問をStandard MLで解いてみたの方がはるかに情報量が多いです。ぜひこちらの記事を参考にしてください。

そもそもStandard MLって何よ？って方は、ググって見てください。いわゆる関数型プログラミング言語の一種ですが、非常にマイナな言語です。体系的・網羅的に勉強してみたい方は、貴重なSML入門書であるプログラミング言語Standard ML入門をご参照ください。

SML環境の構築

AtCoderで使用されているSML処理系はMLtonという凄まじく最適化をしてくれるコンパイラなのですが、実際にAtCoderの問題を解いていくときには対話的な環境を持っているStandard ML of New Jersey (SML/NJ) を使うのが簡単だと思います。

どちらにしても、Ubuntuであればパッケージマネージャを使って簡単にインストールできますので、みなさんUbuntuを使いましょう。（ちなみに私は、SML/NJ：公式Webサイトからソースをダウンロードしてビルド、MLton：公式Webサイトからバイナリをダウンロードしてインストールしています。）

// MLtonをインストールする場合
$ sudo apt install mlton

// SML/NJをインストールする場合
$ sudo apt install smlnj

インストールできているかどうかを、以下のテスト用ファイル（hello.sml）を使って確かめてください。

hello.sml
val _ = print "Hello World!\n"

ファイルが作成できたら、端末で以下のコマンドを実行してください。Hello World!の文字が表示されたら環境構築完了です。

// MLtonをインストールした場合
$ mlton hello.sml
$ ./hello
Hello World!

// SML/NJをインストールする場合
$ sml hello.sml
Standard ML of New Jersey ~~~
Hello World!

AtCoderにチャレンジ

SML環境も構築できたので、早速AtCoderにチャレンジしましょう！あとは自由にコードを書くだけです！と言いたいのですが、どのプログラミング言語を使うにしろ、一番の難関は標準入力です。

正直、標準入力さえ乗り切れば、あとはメジャーな関数型プログラミング言語とそう大差なくできるのではないかと思っています。

標準入力

AtCoderの入力はおおよそ空白区切りないし改行区切りで与えられるので、JavaのScannerが持つnextメソッドのように、next関数を呼び出す度に次のトークンを切り出して来てくれると使い勝手が良いです。

そこで、TextIOストラクチャのscanStream関数を利用してnext関数を作成します。canStream関数の型は以下の通りです。

scanStream: ( (Char.char, StreamIO.instream) StringCvt.reader ->
              ('a, StreamIO.instream) StringCvt.reader ) ->
            instream ->
            'a option`

型からなんとなくわかることは、「readerを受け取ってreaderを返す関数とinstreamを受け取って、'aをオプションつけて返す」ということですね。「readerを受け取ってreaderを返す関数」とはすなわちscan関数に他ならないので、これを別部品として作ります。また、instreamは今回標準入力のため、TextIO.stdInです。

よって、TextIO.scanStream scan TextIO.stdInでscan関数を利用して標準入力からトークンを切り出す（そしてオプションで包む）動作となります。

あとは、scan関数を作るだけですが、今回の目的では空白で区切りたいので、StringCvtストラクチャのsplitl関数、skipWS関数およびCharストラクチャのisSpace関数を利用して、パズルのように組み立てます。

ここまでのことをコードに記述すると、以下の通りとなります（おまけでnextInt関数も記述しています）。

(* fn : (char,'a) StringCvt.reader -> (string, 'a) StringCvt.reader *)
fun scan reader stream = SOME (StringCvt.splitl (not o Char.isSpace) reader (StringCvt.skipWS reader stream))

(* fn : unit -> string *)
fun next () = valOf (TextIO.scanStream scan TextIO.stdIn)

(* fn : unit -> int *)
fun nextInt () = valOf (TextIO.scanStream (Int.scan StringCvt.DEC) TextIO.stdIn)

あとは、定義した関数を利用してやれば、簡単に入力を取り込めます。

まとめ

みなさんも2021年はStandard MLを始めましょう！

Discussion