日記 - 2013-09
2013-09-11
関数型言語とは
関数型言語とは何か、ということをTwitterでちょっと考えました。
関数型言語がどういうものか教えてほしいと言われて、一番最初に思いついた例えは
線型変換ABC……Zvを計算したいとき、(ABC……Z)vと考えるのが関数型、A(B(C(……(Zv)……)))と考えるのが手続き型
というものでした（この時点では感覚で言っていて、あまり厳密に考えていない）。
その後で、具体的に何ができれば関数型と言ってよいのかというのを把握できていないことに気付きました。
強力な静的型推論でバグが見つかるというのは、関数型のメリットとして@tanakhさんを始め様々な人が言っていますが、
そもそも型と呼べる構造をもたないLispや、静的に型の付かないErlangも一般的には関数型と呼ばれていることを考えると不十分です。
また、Wikipediaの「関数型言語」では、関数型の必要条件として第一級関数を挙げていますが、
最近の言語であればPerl、Ruby、JavaScriptなど、大抵は関数を第一級として扱えるため、十分条件としては不適当に思えます。
もうひとつ、関数型言語に対してもっているイメージを書き出してみると
というものもありました。 これは、手続き型では処理の流れを上から下へ、時間的に順番に実行されるという前提で書き下していくのに対し、 関数型ではそういう依存性は関数適用の順番だけで表現しているな、と思ったものです。
そんなことをTwitterで言っていたら、@omasanoriさんに捕捉されて、助言をいただきました。
WP-jaが書いている通り、最低条件は関数を第一級の値として扱えること（これがないと、高階関数や関数合成に支障が出る）ではないかと思います。
で、上述した不適当さについては、
実際にそう言っている人もいます。しかし、仮にJavaScriptを関数型言語と分類したとしても、JavaScriptで関数型プログラミングを行うかどうかは別の話ですね。
とのことでした。
どうやら、第一級関数の存在に着目して関数型を定義する流派もあるようです。
また、別の見方として
という基準の指摘もありました（今Wikipediaを見返したら、λ計算についても言及してありますね……）。 明確に概念として整理できていなかったのですが、最初に挙げた例えはβ簡約に他ならず、まさにこの基準に基づいたものですね。
ということで、これからは「λ計算による計算モデルを採用している言語」と言うことにしようと思います。 @omasanoriさん、ありがとうございました。
Project Euler
215を解きました。これも典型的DP。
2013-09-07
焼肉
9/6の話ですが、ただ肉というイベントで、CROOZという企業のスポンサーで焼肉を食べてきました。 見つけたのはTwitterで、プログラマの学生なら誰でもタダで焼肉が食べられる！という触れ込みに釣られました。
肉！
ビール！
冷麺！
とてもおいしかったです。ありがたや～
イベントの詳しい成り立ちなどは知らなかったんですが、どうもベンチャーのスタートアップ周辺と繋がりが深いらしく、学生で起業している人も参加者の中に数人いました。
そういった起業の話や、研究の話など、色々と面白い話ができて楽しかったです。
あと、ICPCでもらったIBMの名札入れを着けてたら、「IBMの人ですか？」と数人に聞かれました。 ICPC WFに行った話もそれなりにウケていたっぽいし、話下手な自分としてはこういうの便利だなぁと思いました。
Euler
188と191を解いて、Decimation Iを取得しました。 DPは楽でよい。
SRM 590
o– +1 243.56pts / 132nd
Easyを解いて、Medの探索解を落として、黄色に復帰しました。
Medも解きたかったけど、解法をTwitterで見てもコードにうまく落とせなかったので無理だった感……。
2013-09-03
PHP
バイトでPHPを書きました。
同じような機能をもつクラスをたくさん作る案件だったので、mixin使えれば楽なのになーと思いつつガシガシ書いていました。
どうやら5.4.0以降ならtraitsという名前でmixinっぽいのが使えるみたいですね。
あと、error_reporting(-1)すると、syntax error等で落ちた時のログが詳細になって嬉しい感じでした。
Project Eulerは134を解いて、Daring Dozenをもらいました。 このへんの領域は2桁番号の問題と違って、4000solvedくらいでも結構簡単なのがありますね。
そういえば、昨日見つけたRubyの問題はやっぱりバグだったようです。 ささださんに拾われて、あっという間に修正されていました。
2013-09-02
進捗
Project Eulerで102, 104, 112, 113, 124を解いて100solvedを達成しました。
とりあえずみんなが解いている問題を解いていく方針。
112と113はDigit DPの典型問題で楽しかったです。
あと、メモ化再帰にmemoizeというgemを使っていたんですが、なんかRubyのバグっぽい挙動を踏んでRuntimeErrorを吐いていたので ruby-listに質問を投げました。
2013-09-01
DPコンテスト
飲み会をしていたので参加できなかった、Typical DP Contestを解いていました。
Typicalと言いつつ、個人的にはかなり難しく感じました……。
解けなかった（解説を見て解いた）ものではF - 準急とL - 猫
が重要そうなので、しっかり復習したいところです。
コードはGithubに置いているので、参考にしたい人は見てください。
簡単な解説も付けています。
Eulerは97と99を解きました。1日中DP解いてて疲れたので、超簡単な2問。