2009-12-09

Haskell binding for MessagePack

Haskell

MessagePack の Haskell binding を作りました。

MessagePackとは

http://msgpack.sourceforge.jp/
id:viver さんが開発された高速なバイナリシリアライザです。
http://d.hatena.ne.jp/viver/20080816/p1 や http://d.hatena.ne.jp/nobu-q/20091209 が詳しいです。

インストール方法

githubにレポジトリを置いています。http://github.com/tanakh/hsmsgpack にあります。
パッケージをHackageにアップロードしています。http://hackage.haskell.org/package/msgpack-0.1.0 にて公開されています。

インストールは、MessagePackをインストールしてから、

$ cabal install msgpack

で行えます。

使い方

http://fxp.hp.infoseek.co.jp/doc/msgpack/
ここにhaddockドキュメントがあります（Hackageでのビルドがこけているため、Hackageにドキュメントが生成されていないので、暫定的にここに置いています。将来的には移動する可能性が高いです）。

Low Levelなインターフェースとして、MessagePackのC APIがほぼすべて一対一対応の関数が Data.MessagePack.Base にありますので、これを使えばだいたい何でもできるはずです。 http://msgpack.sourceforge.jp/c:doc.ja こちらが参考になるはずです。

import Control.Monad
import Data.MessagePack

main = do
  sb <- newSimpleBuffer -- Packerが使うバッファ作成
  pc <- newPacker sb -- Packer作成
  
  packArray  pc 3     -- 三要素の配列をパックしますよ
  packS32    pc 12345 -- 整数
  packDouble pc 3.14  -- 浮動小数
  packTrue   pc       -- Bool
  
  bs <- simpleBufferData sb -- バッファにたまったデータを取り出す

  print bs -- > "\147\205\&09\203@\t\RS\184Q\235\133\US\195"
  
  up <- newUnpacker defaultInitialBufferSize -- Unpacker作成
  unpackerFeed up bs -- Unpackerにデータを食わせる
  
  resp <- unpackerExecute up -- デシリアライズ実行
  guard $ resp==1 -- 成功すると1が返る
  obj <- unpackerData up -- デシリアライズされたデータを取り出す
  
  print obj -- > ObjectArray [ObjectInteger 12345,ObjectDouble 3.14,ObjectBool True]

Low Levelなインターフェースの上に、High Levelなインターフェースを作っています。今のところ、汎用的なpack関数と、単一のpack, unpackを簡単に行う関数があります。

main = do
  sb <- newSimpleBuffer
  pc <- newPacker sb
  
  -- OBJECTクラスの値を適当にpackする
  pack pc [(1, 2), (3, 4), (5::Int, 6::Int)]

  ...

main = do
  bs <- packb [1,2,3::Int] -- お手軽pack
  Right dat <- unpackb bs  -- お手軽unpack
  print (dat :: [Int]) -- > [1,2,3]

main = do
  let bs = packb' [1,2,3::Int] -- pure版
  let Right dat = unpackb' bs -- pure版
  print (dat :: [Int]) -- > [1,2,3]

ObjectとHaskellのデータの相互変換は toObject、 fromObject で行えます。

main = do
  bs <- packb [1,2,3::Int]
  Right (_, obj) <- withZone $ \z -> unpackObject z bs
  let Right dat = fromObject obj
  print (dat :: [Int])

2009-11-29

Haskellerのためのプレゼンツール"MonadPoint"

Haskell

去る11月20日、Haskellナイトというイベント ( http://hop.timedia.co.jp/ )で、"HaskellerのHaskellによるHaskellerのためのプレゼン"というなんだかよくわからないタイトルで発表してきました。

遅くなりましたが、作った物の公開と発表の補足をしておきます。

概要

Haskellでプレゼンツールを作りました。

Haskellで記述され、
スクリプトもHaskellで書く

ようなプレゼンツールです。

プレゼンをモナディックに書くので、MonadPointと名付けました。略称は「モナポ」です。

レポジトリ

http://github.com/tanakh/MonadPoint にてMonadPointを公開しています。
http://github.com/tanakh/haskell-night にて当日使ったスライドのソースとWindowsバイナリを公開しています。

使い方

まず、MonadPointをcabalでインストールしてください(Windowsに入れる場合、依存ライブラリのFTGLを入れるのが大変だと思いますので、前回のエントリを参照していただければ幸いです)。それから、てきとうな.hsファイルを作って、import MonadPoint してプレゼンをモナドでゴリゴリと書いて、runPresentation に渡せばいい感じになると思います。レポジトリにあるサンプルが参考になると思います。

http://github.com/tanakh/MonadPoint/blob/master/test/Main.hs

若干説明

今のところサポートしているのは、

矩形の中にそれっぽく文字列を書く
矩形を書く
画像ファイルの表示
矩形をレイアウトする

のような機能です。

基本的に、scaleでスケーリングして、縦横に並べてスライドを作ります。自動で高さとか幅を調節することはできないので、手でやらないといけません。

scale d $ do ... - 縦横に縮小。中央に配置。
scalehu d $ do ... -- 縦方向に縮小。上に配置。
scalehd d $ do ... -- 縦方向に縮小。下に配置。
scalevl d $ do ... -- 横方向に縮小。左に配置。
scalevr d $ do ... -- 横方向に縮小。右に配置。

txtc str -- 文字列。中央揃え。
txtl str -- 文字列。左揃え。
txtr str -- 文字列。右揃え。

pict filename -- 画像を表示。

txtarea strs -- 文字列リストを等幅フォントで表示。

他にも色々あるので、ソースをご参照下さい。

スライドによくつかわれるリスト記法は書きやすくする関数を提供しています。

list $ do ... -- 引数に与えられたリスト要素をうまいことレイアウトして表示する

list $ do
  li "hoge"
  ul $ do
    li "moge"

ちなみに、liなどは型が違うので、listの外側には置けません。うーん、型ですね。

何がいいのか？

基本的に誰得ではありますが…。

抽象化能力

テンプレートを作りやすいとか。プレゼン=Haskellソースなので、なんとでもできます。

プラグインをHaskellで書ける

ニコニコ動画風Twitter プラグインみたいなのも簡単に書けます。

今後の予定

実装がやっつけで、完成度が低すぎるので、まだまだ色々改良したいところです。

ソースをきれいにする
GLUT使うのやめる(フルスクリーンから復帰する手段がないとか…)
フォントをきれいにする(フルシーンAAとかでどうにかなるのだろうか)
もっといろいろカスタマイズできるようにする(ページ遷移時のアニメーションとか)
アニメーション実装
賢いレイアウト
GHC API対応 (毎回コンパイルするのはさすがにめんどい)

イベントの感想

Haskellerの人たちがこんなに集まってるのはなかなかすごかったです。普段は肩身の狭い私も、Haskellの話ばかり出来て楽しかったです。本買ってサインもらいました。値段を安く抑えた苦労話とか。日本語版Real World Haskellは安くてバグも直っててお買い得です。カクテルの名前がHaskellぽくてよかった。遅延評価らしく、あとから効いてくる。発表は皆さん面白かった。総じてすごく刺激になりました。Haskellコミュニティーがもっと盛り上がっていけばいいなと思いました。

2009-11-07

FTGL on GHC on Windows

Haskell

http://hackage.haskell.org/package/FTGL これをWindowsで使いたいという話。泣きそうなほど苦労したのでここに書いとく。

GHCのインストール

まずは、GHCのインストールです。WindowsだとHaskell Platform(http://hackage.haskell.org/platform/)を入れるのが楽。cabal-installが入ってパスもとおってうれしい。

MinGWのインストール

いきなりcabal installしても、ftglがなくて入るはずがないので、まずそっちを何とかする。そもそもWindowsで外部ライブラリの必要なcabalパッケージってどうやってインストールするのかよく知らない。調べたところ、cygwinかMinGWがあればいいらしい。cygwinの場合、cygwinをインストールして、その上にftglをインストールしてそこでcabal installすると結構簡単にインストール自体は成功したのだが、いざ動かそうとすると、cygwinとGHCのMinGWの食い合わせが悪いのか、うまく動かない(CPU100%食って固まる)。なので、cygwinは没となった。

まずはMinGWをインストールする。http://sourceforge.net/projects/mingw/files/ から、Automated MinGW Installerと、MSYS Base Systemをインストールする。msysのインストールの際にmingwの場所を教えて、msysのシェルからMinGWが参照できるようにする。

ftglのインストール

http://sourceforge.net/projects/ftgl/files/ から 2.1.3~rc5をダウンロードして、MinGWにインストールする。./configure; make; make install でいいのだが、./configureが、FreeType2が見つけられないと言ってこけるはずである。

FreeType2のインストール

http://ftp.twaren.net/Unix/NonGNU/freetype/ ここから、一番新しそうなのをダウンロードしてMinGWにインストールする。これはすんなり入ってくれるはず。

再びftglのインストール

freetypeをインストールして再度ftglの./configrueを実行すると、今度はGL libraryが見つからないとかでこける。GL libraryって何ぞ？という話だが、どうやら-lGLのことらしい。MinGWにはあらかじめopenglとGLUのライブラリがインストールされているので、見つけられないのはスクリプトがおかしいから。--with-gl-libでライブラリの場所を指定せよとのエラーメッセージが出てきているが、そもそもMinGWでのopenglのライブラリの名前は-lGLじゃなくて-lopengl32なので指定してもどうやっても見つからない。幸いm4ファイルが同梱されているので、これを書き換えることにする。m4/gl.m4というファイルがあって、これでopenglライブラリのチェックをしているので、これを書き換える。LIBSの-lGLとなっているところを書き換えればいいと思いきや、MinGW環境ではOpenGLに対するAC_LANG_CALLマクロがそもそもうまく動かないので(AC_LANG_CALLはmainの中に指定した関数を呼び出すコードを生成してコンパイルを試みるようだが、MinGWでのopenglの呼び出しはcdeclではないようなので、リンクがどうやっても成功しない)これを成功させることはあきらめ、失敗したときのコードを、無理やり成功したことにさせる。72行目付近：

if test "x$HAVE_GL" = xyes ; then
    AC_MSG_RESULT([yes])
    GL_LIBS=$LIBS
else
#    AC_MSG_RESULT([no])
#    AC_MSG_ERROR([GL library could not be found, please specify its location with --with-gl-lib.  If this still fails, please contact henryj@paradise.net.nz, include the string FTGL somewhere in the subject line and provide a copy of the config.log file that was left behind.])
    AC_MSG_RESULT([yes])
    GL_LIBS="-lopengl32"
fi

また、同様の理由で-lGLUの検出もこけるので、そこも書き換えておく。116行目付近：

if test "x$HAVE_GLU" = xyes ; then
    AC_MSG_RESULT([yes])
    GL_LIBS="$LIBS"
else
#    AC_MSG_RESULT([no])
#    AC_MSG_ERROR([GLU library could not be found, please specify its location with --with-gl-lib.  If this still fails, please contact henryj@paradise.net.nz, include the string FTGL somewhere in the subject line and provide a copy of the config.log file that was left behind.])
    AC_MSG_RESULT([yes])
    GL_LIBS="-lglu32 $GL_LIBS"
fi

autotoolsのインストール

m4/gl.m4を書き換えた後に、./autogen.shを実行しなければならないが、このときにautotoolsが必要になる。http://sourceforge.net/projects/mingw/files/ から、MSYS Supplementary ToolsのmsysDTK-1.0.1をインストールする。

msysDTKに入っているautoconfのバージョンは2.56だが、ftglが2.58以上を要求するので、http://ftp.gnu.org/gnu/autoconf/ ここからautoconfの新しいのを持ってきてインストールする。

さらにlibtoolもバージョンが古いといわれるので、1.4.2以上のを http://ftp.gnu.org/gnu/libtool/ ここから拾ってきて入れる。

三度ftglのインストール

./autogen.shを実行すると今度は成功するはずなので、続いて./configureする。これもようやくうまくいくはずである。make; make installでftglのインストール完了。

FTGL(Haskellのほう)のインストール

ようやくFTGLパッケージをインストールできる準備がととのったので、インストールする。

cabal install FTGL --user --extra-include-dirs=/usr/local/include --extra-lib-dirs=/usr/local/lib

http://blog.mestan.fr/2009/09/24/3d-text-rendering-in-haskell-with-ftgl/ ここにいいサンプルがあるので、実行してみる。すると、大量のリンクエラーメッセージが出るはずである。FTGLが使っているfreetypeとlibstdc++の関数がどうやらリンクできていないらしい。ghcのコマンドラインに--optl-lstdc++とかやってもうまくコンパイルできない(順序が大切？)。きっとftglかFTGLかのどちらかを書き換えないといけないのだろう。個人的に書き換えやすいFTGLのほうを書き換えることにする。

http://hackage.haskell.org/package/FTGL ここからアーカイブを取ってきて、FTGL.cabalの最後のほうのを

Library
   Build-Depends: OpenGL, base
   Exposed-Modules:
      Graphics.Rendering.FTGL
   extra-libraries: ftgl

から

Library
   Build-Depends: OpenGL, base
   Exposed-Modules:
      Graphics.Rendering.FTGL
   extra-libraries: ftgl stdc++ freetype

に変える。それから、

$ cabal configure --user --extra-include-dirs=/usr/local/include --extra-lib-dirs=/usr/local/lib
$ cabal build
$ cabal install --user --extra-include-dirs=/usr/local/include --extra-lib-dirs=/usr/local/lib

で、インストール。

テスト

再度先ほどのサンプルプログラムをコンパイルすると今度はリンクに成功する。実行するとglut32.dllがないといわれるので、http://jp.dll-download-system.com/dlls-download-g-/glut32.dll.html この辺から適当に拾ってきて同じディレクトリに入れる。

実行してみると、、、

動いたー

utf8-stringのencodeStringすれば日本語も出たー

2009-10-28

C++向け簡易コマンドラインパーザ cmdline

Program

を作りました。

http://github.com/tanakh/cmdline

何か

コマンドライン引き数の解析を助けるライブラリです。同じ目的のライブラリに、Cの標準関数であるgetoptやgoogleのgflagsなどがありますが、cmdlineは適当に使えてそこそこ便利というのを目指しています。getoptは使いにくいし、usageも自分で書く必要がある。gflagsはライブラリをインストールしたり、リンクしたりちょっと大掛かり。cmdlineは、1ヘッダファイルで、コピーするだけで使えて、修正BSDライセンスで公開しているので、自由にプログラムに取り込んでいただけます。

コードサンプル

#include "cmdline.h"

int main(int argc, char *argv[])
{
  cmdline::parser p;
  p.add("hoge", 'h', "hoge flag with no value");
  p.add<int>("moge", 'm', "moge flag with int value", false, 123);
  p.add("help", 0, "print help");
  // add other flags...

  if (!p.parse(argc, argv)||p.exist("help")){
    std::cout<<p.error_full()<<p.usage();
    return 0;
  }

  // main code...

  if (p.exist("hoge"))
     std::cout<<"there is hoge flag"<<std::endl;

  std::cout<<"moge value: "<<p.get<int>("moge")<<std::endl;

  // ...
}

上プログラムのように、cmdline::parserのオブジェクトを生成してやり、parser::add()によりフラグを追加し、parser::parse()を呼び出します。実行例です。

> ./a.out --help
usage: ./a.out [options] ...
options:
  -h, --hoge    hoge flag with no value
  -m, --moge    moge flag with int value (int [=123])
      --help    print help

> ./a.out --moge=777 -h
there is hoge flag
moge value: 777

>  ./a.out --moge=huga
option value is invalid: --moge=huga
usage: ./a.out [options] ...
options:
  -h, --hoge    hoge flag with no value
  -m, --moge    moge flag with int value (int [=123])
      --help    print help

マニュアル

parser::add(const string &name, char short_name, const string &description)

値を持たないフラグを定義します。フルネーム、短縮名、フラグの説明、の順です。短縮名に0を指定すると、短縮名なしになります。

template void parser::add(const std::string &name, char short_name=0, const std::string &desc="", bool need=true, const T def=T())

値を持つフラグを定義します。必須なのは、フルネーム、短縮名、フラグの説明(と、テンプレートパラメータである型)です。オプショナルな引き数として、そのフラグが必須か(必須ならば、コマンドラインで与えられないときにparseがエラーになります)と、フラグ値が与えられなかったときのデフォルトの値があります。短縮名を0にすると短縮名なしになるのは上と同じです。

template void parser::add(const std::string &name, char short_name=0, const std::string &desc="", bool need=true, const T def=T(), F reader=F())

上と同じく、値を持つフラグを定義します。値に対するカスタムreaderをセットできます。上のメソッドでは、デフォルトのreaderとして、lexical_castが使われます。stringから型Tへの任意の関数もしくは関数オブジェクトが渡せます。この関数が例外を投げる場合、失敗とみなされ、parser::parse()は失敗になります。

bool parser::parse(int argc, char *argv[])

コマンドライン引き数を解析します。mainの引き数をそのまま渡します。失敗したらfalse、成功したらtrueが返ります。失敗した場合、parser::error()で具体的なエラーメッセージが取得できます。

bool parser::exist(const string &name)

コマンドライン引き数に与えられたフラグが存在していたかを返します。parser::parse()した後に使います。

template const T &parser::get(const std::string &name)

与えられたフラグの値を返します。parser::parse()した後に使います。フラグ名が不正(addされていない)、もしくは型がaddしたときとかみ合わない場合、cmdline::cmdline_error例外が投げられます。

const std::vector &parser::rest()

コマンドライン引き数のうち、コマンドラインオプションと認識されなかった引き数が格納される配列が返されます。オプションのほかにファイル名などを引き数として取りたい場合などに使えます。

std::string parser::error()

一つ目のエラーメッセージを返します。

std::string parser::error_full()

すべてのエラーメッセージを返します。

std::string parser::usage()

usageを返します。

void parser::footer(const std::string &f)

usageが返す文字列のusageの行の後ろに文字列を追加できます。

void parser::set_progam_name(const std::string &name)

usageのusageの行に表示されるプログラム名をセットできます。この関数でセットしない場合、プログラム名としてはargv[0]が使われます。

カスタムreader

デフォルトでは、フラグの値を読むのに、lexical_cast(のような自前のもの)が使われます。このため、addなどとすると、コマンドライン引き数が10進整数として読まれ、不正な値ならばparseが失敗するなどの動作になります。この処理はオプションで変更することができ、lexical_castの代わりに任意の関数オブジェクトを渡すことができます。なので、16進で読ませることや、特定のレンジにある値、のような指定もできます。cmdlineでは、簡便のために、レンジ付き値、択一などのreaderがあらかじめ用意されています。デフォルトの動作は、cmdline::default_readerとして参照できます。

  p.add<int>("hoge", 'h', "int value (100 - 999)", cmdline::range(100, 999));
  p.add<string>("moge", 'm', "one of abd, def, ghi", cmdline::oneof<string>("abc", "def", "ghi"));

関数合成的な演算子を用意して、ごりごりと合成できるほうがいいかなとも思いましたが、独自の演算子を定義して、それを覚えてもらうのもよくないかなと思ってやめました。とにかく覚えること少なくて、ぬるく使えるように。

2009-10-27

ICFP2009 ソースコード

ICFP

ICFP飲み会でソースコードを公開するといいよ、みたいなことを
しきりに言われて、そうか、ソースコードを公開するべきなんだな、って
その時はとてもそういう気分になっていたのですが、すっかり忘れていました。
この度思い出したので、忘れないうちにアップロードしておくことにします。
ソースコードはHaskell/C++で書かれていて、基本的にはHaskellです。

http://fxp.infoseek.ne.jp/tmp/icfp2009.tar.gz

仮想マシンのコンパイラと、シミュレーションの重い部分がC++です。
ここ最近、私のコードにはコメントは書かれなくなったので、
コメントはありません。あしからず。
なので、本人も詳しいことは覚えておりません。
方針などの概要は前回のスライドを参照してください。

2009-09-09

ICFP Programming Contest 2009

ICFP

すっかり文章を書くのを忘れてたのをICFPが終わって思い出したので、社内向けに作ったスライドを張ってお茶を濁す。書き換えたい部分もあるが面倒なのでオリジナルまま。

Icfp2009

View more presentations from tanakh.

動画。手振れがひどい。なかなか辛い回り方をしているなあ。

2009-09-08

[Scala]競技プログラミング in Scala

Scalaで競技プログラミングを行う際に気をつけることの列挙。

なぜScalaなのか？

速い
静的型付
字面がC++よりましなのでC++よりは速く書けるであろうという期待
同じ理由でJavaよりは速く書けるであろうという期待
OCamlよりも基本的なライブラリが充実しているので速く書けるであろうという期待
Haskelは配列を弄繰り回すような場合にコードが冗長になる傾向があるのでそういう場合に比較して速く書けるであろうという期待

プログラム全体の構造

Scalaプログラムの実行方法には二通りある。

scalaコマンドによる直接実行
scalac(fsc)コマンドで.classファイルを生成 → scalaコマンドで.classファイルを指定して実行

注意すべきは、どちらの方法をとるかで書くべきプログラムが変わることである。scalaコマンドで直接実行する場合、トップレベルに書かれた式が実行される。scalacコマンドでコンパイルする場合、トップレベルには定義しかかけない。つまり、クラスを作らなければならない。コードは次のようになる。

object A extends Application{
  ... hoge hoge
}

直接実行する場合、クラスを定義しただけでは実行されないので、これとは逆にクラスを定義してはいけない。

書くべきコードはコンパイルする場合のほうが多い。また、実行させるのに必要なコマンドも長くなる(さらに悪いことに、コンパイルした場合、ラムダ式に応じて匿名の.classファイルが大量に生成される傾向にある)。あえてコンパイルする理由があるとすれば実行速度だろう。しかし、私の見たところによると、コンパイルして実行速度が速くなるということはなかった。直接実行する場合も内部的にはきっちりコンパイルして実行しているようだ(たぶんそうなので、直接実行する場合にもscalacする場合と同じぐらい起動に時間がかかる)。このことを鑑みるに、競技プログラミングであえてscalacを行う理由はない。プログラムはトップレベルに書き、scalaコマンドで実行するのが良い。

入出力

典型的な競技プログラミングの課題は標準入力からテストセットを入力し、結果を標準出力に書き出す必要がある。Scalaで入力をするにはいくつかの方法がある。

java.io.以下のBufferedReaderなどを使う
scala.io.Sourceを使う
java.util.Scannerを使う

一つ目の方法は旧来のJavaで一般的な方法だが、冗長に過ぎる。scala.io.Sourceはインターフェースが使いにくい。Java1.5以上であればScannerを使うのがよろしい。

出力はSystem.outを使う方法と、scalaの標準ライブラリを使う方法がある。前者は、単にSystem.out.とタイプするのが面倒なこと(これはimportすればよいのだが)に加え、JavaのクラスであるObjectを引数をとる関数にはscalaの暗黙の型変換がうまく働かないという問題がある。

System.out.printf("%d\n", 123) // NG
System.out.printf("%d\n", int2Integer(123)) // OK

この理由から、scala組み込みのを使うべきである。

printf("%d\n", 123) // OK

なお、scalaのprint/printlnには任意個の引き数が渡せて、その場合にはタプルの出力と同じになるので、デバッグに便利である。

データ構造

配列

newでの生成は初期値が指定できない上に要素の型を指定しなくてはならず大変使いにくい。コンパニオンオブジェクトのfromFunctionが便利。

val aa = Array(1, 2, 3) // リテラル
val bb = Array.fromFunction(i=>...)(n) // 添え字で初期化できる
val cc = Array.fromFunction(_=> -1)(n) // 初期値が決まっているなら
val dd = Array.make(n, -1) // これでもいい
val ee = Array.fromFunction((i, j)=>...)(n, m) // 多次元配列も
val ff = Array.make(n, Array.make(m, -1)) // これはだめ

リスト

普通のリスト。

- scala.collection.Map
- scala.collection.SortedMap

の二つのtraitがある。前者は順序を保障しない。後者は保障する。実装しているクラスは次のとおり

- scala.collection.immutable.HashMap extends Map
- scala.collection.immutable.ListMap extends Map
- scala.collection.immutable.TreeMap extends SortedMap
- scala.collection.immutable.TreeHashMap extends Map
- scala.collection.immutable.UnbalancedTreeMap extends Map
- scala.collection.immutable.IntMap extends Map
- scala.collection.immutable.LongMap extends Map

- scala.collection.mutable.HashMap extends Map
- scala.collection.mutable.LinkedHashMap extends Map
- scala.collection.mutable.OpenHashMap extends Map

などがある。たくさんあるが、

- immutable.ListMapと、immutable.UnbalancedTreeMapは存在価値が不明
- immutable.TreeHashMapはHashMapでいい
- mutable.LinkedHashMapとOpenHashMapはmutable.HashMapでいい

おおよそ次のような基準で選ぶと良い。

- 順序付ならimmutable.TreeMap一択
- キーが整数かつ非負で順序つきならimmutable.IntMap or LongMap
  - これらはunsignedに順序が付くようなので、非負の数しか入れないならSortedMapとして使える
  - HashMapよりは遅いがTreeMapよりはだいぶ速い
- パフォーマンスが気になるならmutable.HashMap
- それ以外ならimmutable.HashMap
  - (実際のところimmutable.HashMapは十分速い)

なお、scala.collection.immutable.Mapとmutable.Mapコンパニオンオブジェクトはそれぞれimmutable.HashMapとmutable.HashMapを生成する。

- scala.collection.Set
- scala.collection.SortedSet

mapと同様に順序付きとそうでないものの二つのtraitがある。

- scala.collection.immutable.HashSet extends Set
- scala.collection.immutable.ListSet extends Set
- scala.collection.immutable.TreeSet extends SortedSet

- scala.collection.mutable.HashSet extends Set
- scala.collection.mutable.LinkedHashSet extends Set

なぜかmapよりもバリエーションが少ない。IntMap相当のものがないことを除けば、選定基準はMapと同じでいいだろう。

MultiMap

基本的にMap[A, Set[B] ]で扱う。便利のためにそのようなTraitがscala.collection.mutable.MultiMapに用意されている(なぜかmutableだけ)。

val x = new HashMap[Int, Set[Int] ] with MultiMap[Int, Int] // こうすると
x.add(1, 2)
x.add(1, 3)
x.entryExists(1, (_ = 2))
x.remove(1, 2) // こういうメソッドが使える

当然ながらimmutableにはくっつけられない。

キーも値も重複するものを許すものは用意されていない。

MultiSet

特に用意されているものはない。Map[A, Int] などで出現回数を数えるぐらいだろうか。

PriorityQueue

scala.collection.mutableにある。比較関数は変えられない。

小技

パラメータを複数個読み込む必要がある場合。

val sc = new java.util.Scanner(System.in)
val a, b, c = sc.nextInt() // a, b, c の順に整数が三つ読み込まれる

整数の配列を読み込む場合

val arr = Array.fromFunction(_=>sc.readInt())(n) // arr(0) .. arr(n-1) に順に整数が読み込まれる
val mat = Array.fromFunction((_,_)=>sc.readInt())(n, m) // arr(0)(0) .. arr(0)(m-1) .. arr(n-1)(m-1) に順に整数が読み込まれる

文字列を空白区切りで分割

val words = sc.nextLine() split " +"

ジェネレータは一回しか評価されない

for (caseno <- 1 to sc.nextInt()){
  ...
  printf("Case #%d: ...", caseno, ...)
}

パーザコンビネータが標準でついてるので、使えるようにしておくべし

気をつけること

型推論

型推論が弱いので、要所要所で型を書いてやる必要がある。書く必要がある場所の判定にはScalaの型推論アルゴリズムを熟知している必要があるので、Programming in Scalaには、コンパイラに怒られたらその都度注釈を入れよ、の様に書いてあった。しかし、いちいちそれでは時間をロスするので、注釈が必ず必要な簡単な場所は覚えておく。

- 関数の引き数
- 明示的にreturnしている関数の返り値の型
- 再帰呼び出ししている関数の返り値の型

for式の型

for式でyieldすると、最初のジェネレータと同じ型のコレクションが返る。ListならList、ArrayならArrayであるが、SetだとSetになって、要素がつぶれてしまうことがあるので注意。