koie blog : 第4回スタートHaskell (メモ)

本編: http://atnd.org/events/20992
日時: 2011/11/13 13:00〜18:15
場所: ニフティ (大森)
#start_haskell
@master_q さん（ライブ中継）http://ja.justin.tv/kiwamu
@kamakiri_ys さん（togetterまとめ）http://togetter.com/li/213769

懇親会: http://atnd.org/events/20993
日時: 2011/11/13 18:30〜21:15

午前は相模原マスターズ水泳大会で100m IMを泳いでダウンなしに帰宅→ソバをかきこむ/プロテインの野菜ジュース割りをながしこむ→電車で大森まで1時間ちょっと。ビルに到着したのは12時半。フリーマーケットをやってた。案内看板によると定期的にやってるようだ。時間があるのでマックで昼飯のつづき。館内はひっそりとした感じだが、それなりに家族客がランチタイムだった。

喰いおわって1階の集合場所にいってみるとだれもおらず焦るも、すぐに社員の型が案内にきて一安心。会場に入るとすでに半分くらい席がうまっていた。WiMAXはばっちり。

宿題の答えあわせ (虎)

いきなり「宿題やってきましたか?」って誰も手を上げないから虎:「やりがいがないです」。宿題って前々回に出されたやつだったのね。

第8章: 関数型パーサ (@ruicc)

スライド: http://www.slideshare.net/RuiccRail/programming-haskell-chapter8
parser: パーサ。濁らない。
return: 命令型のプログラミングでいうところのreturnとは意味がちがうので、これはよくない。returnは値をコンテナするものと理解するらしい。
>>= はthenとかbindと読むらしい。
>>= の定義はむつかしいよね、ってことで、1週間くらい悩んでやっと受け入れた自分としては救われた感じだ。
p >>= f の fの型(a -> Parser b)が不自然ではないかという質問をしてみた。
- Parser aの結果をみてParser bを生成するというのが一番の目的のようだ。
- >>という演算子もあるらしい。
ラムダ式の入れ子をどう解釈するかは訳注にも書いてあるが
- \x -> ... \y -> ... \z は
- \x -> (... \y -> ... \z ....)) となる。
- -> がきたらとにかく最後まで、というルール(メタルール?)になっているらしい。このへんは演算子の優先度とどういう関係になっているのか本に書いてないので読むときに困った。
- なのでスライドに出てくる例はこんな風になる:

double =
  sign   >>= (\s    ->
  digits >>= (\num  ->
  point  >>= (\p    ->
  digits >>= (\num2 ->
  return (func s num p num2)))))

many/many1の解説は本の付録 C.2にある。
tokenの定義で前後のspaceを喰っているが、ふつうはどちらかだけでよい。
Haskellのパーサには(主なのは)Parsec3とattoparsecがある。
- Parsec3はユーザに近いところでエラーメッセージを親切に出したいときに使う。設定ファイルとか。
- attoparsecはスピード重視のときにつかう。
BNFのBNF(from Wikipedia)を元にHaskellのパーサを書いてみたらバグがみつかった。
- 1対1対応になるので保守しやすい。
訳注「字句解析と構文解析に分けられる。...Haskellでは高階関数が利用できるので...合成する手法を取ることがおおい」について、バックトラックしたときに何度も字句解析することになって無駄ではないか?とうい質問をしたところ
- メモ化するパーサもある: http://twitter.com/khibino/status/135593507560759296
- そのほか本の例にあるようなパーサだと最後までバックトラックの可能性が残るので入力文字列がすてられないが、tryを明示的に書かせることで入力をすてられるようにしたものもあるとのこと。
Haskellのこういうコンビネータでつくるパーサは内部DSL(domain specific language)とういらしい。

休憩

日比野さんにいろいろ聞いてみた:
- 2引数の関数を部分適用したf aはサンクが作られるけど部分計算が済んだもの → 実装依存
- 2引数関数を適用するとき f 1xと書ける(1とxの間に空白がいらない)。Haskellのパーサを書いてて、けっこうかわった文法らしい。

第9章: 対話プログラム (@Lost_dog_)

発表者がいなかったので今朝あわてて作ったらしい。
スライド: https://docs.google.com/present/view?id=0AQAJxoOrvs6-ZGc3OXg3a2hfMjJmNnBmbm5kOA
IOの型は仕様では決められてない。本では関数として定義されているが「IO」だけをみたら字面的には関数ではない。オブジェクトと考えるといいらしい。
IOはアクションと呼ばれるが、IO aは命令書であって命令そのものではない。Haskellではきたない部分は処理系に押し付けてある。
putChar aとか、毎回同じ値を返す。それを受け取ったランタイム・システムが毎回違うことをするだけ。
IOが上から順番に実行されるのは、遅延評価があるからわかりにくいが、たぶんWorldとかの依存関係で決まるっぽい。
- foo = putChar 'a' >>= (\_ -> putChar 'b' >>= (\_ -> putChar 'c' >>= (\_ -> putChar '\n'))) みたいなのを考えたとき、
- fooを実行すると、foo Worldが評価した結果の((),world)が必要になる。
- ((),world)はputChar '\n'がつくって返すが、putChar '\n'を評価するにはその前のputChar 'c'が返すworldが必要で..
- と連鎖してputChar 'a'までさかのぼってきてやっとputChar 'a' worldが評価されるという、末尾呼び出しの連鎖で依存関係が表現されてるっぽい。(俺の理解では)

演習

虎さんから章末問題のユニットテストが提供されて、テストがとおるようにするという形式。
あらかじめ章末問題はやってきてたので(めんどくさい問題はやってなかったけど、幸いユニットテストは提供されてなかった)、虎さんオリジナル問題を解くも、Floatのパーサを書けず断念 → おやつタイム → インスリンショックでぐったり → Webふらふら
tips: +++ でつなげていくとどんどんインデントが深くなるが、where で関数にしてしまえば短かくできる。
コメントは行末までという問題でコメントに改行文字を含むかどうか虎さんに聞いてみたが、オリジナルの問題文からも読みとれないとのことだった。