1と40のリビジョン間の差分 (その間の編集: 39回)
2011-04-25 01:57:20時点のリビジョン1
サイズ: 2891
編集者: furaga
コメント:
2011-06-05 21:00:35時点のリビジョン40
サイズ: 905
編集者: TakuyaKuwahara
コメント:
削除された箇所はこのように表示されます。 追加された箇所はこのように表示されます。
行 1: 行 1:
## page was renamed from 関数・論理型プログラミング実験/memo
行 6: 行 7:
----
行 10: 行 10:
== 第2回 ==  * [[関数・論理型プログラミング実験/課題メモ/第2回|第2回]]
 * [[関数・論理型プログラミング実験/課題メモ/第3回|第3回]]
 * [[関数・論理型プログラミング実験/課題メモ/第4回|第4回]]
 * [[関数・論理型プログラミング実験/課題メモ/第5回|第5回]]
 * [[関数・論理型プログラミング実験/課題メモ/第6回|第6回]]
行 12: 行 16:
=== 課題4 ===

* 実装の仕方はいろいろあると思いますが、筆者は下のように'a queueをリンクリストを使って定義しました。

 * type 'a myQueue = Null | Q of 'a * ('a myQueue ref);;
 * type 'a queue = {head: 'a myQueue ref; tail: 'a myQueue ref};;

=== 課題5 ===

* Yコンビネータを使ったものなら[[http://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%E3%82%B3%E3%83%B3%E3%83%93%E3%83%8D%E3%83%BC%E3%82%BF#.E5.86.8D.E5.B8.B0.E5.9E.8B.E3.81.AB.E3.82.88.E3.82.8B.E7.AC.A6.E5.8F.B7.E5.8C.96.E3.81.AE.E4.BE.8B|Wikipedia]]に載っています

=== 課題8 ===

* カリーハワード対応というものがあって、これによると命題と型、証明とプログラムとの間に対応関係があるそうです。

* つまり「あらゆる型にはそれと1対1に対応する命題が存在する」「ある型に対応する命題が証明できるなら、その型を持つ式が書ける」ということらしいです。

* 今回の場合、型と命題の対応は
 * 「'a -> 'b」と「AならばB」が対応
 * 「('a, 'b) and_t」と「AかつB」が対応
 * 「('a, 'b) or_t」と「AまたはB」が対応
 * 「'a not_t」と「Aでない」が対応
となっています。

* 例えば2の「('a, ('b, 'c) and_t) or_t ->(('a, 'b) or_t, ('a, 'c) or_t) and_t」という型は「(Aまたは(BかつC))ならば((AまたはB)かつ(BかつC))」という命題に対応しています。この命題は証明可能なので2の型は定義可能ということになります。

* いろいろ書きましたが、多分ググってもらった方が確実だし分かりやすいと思います。

* 1・2・3・6は参照、let recなしでできました。

* 4は対応する命題「AまたはAでない」は(多分)証明可能なので定義できるはずですが、筆者はまだできてません。できた人は加筆してー。

* 5は多分無理。

* 7は参照やlet rec、あるいは継続を使えば作れるようです。筆者はoption型と参照を使って定義しました。

=== 課題9 ===

* SMLという言語で書かれたものなら[[http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html|ここ]]に載っています。

* これをがんばってOcamlのコードに直せばちゃんと動くと思います。

* module,struct,sig,functorなどは第3回の授業で習うと思います。

* susp,force,delayはOcamlでいうLazy.t,Lazy.force,lazyで、遅延評価のために用意されている型・関数です。
== 加筆について ==
加筆したところに@``USER@を付けてくれると、誰が書いたか分かりやすくていいと思うんだけど、どうだろう? -- [[carbon_twelve]]
行 60: 行 21:
 

ML演習の課題メモ

ML演習で出された課題に関するメモ的な何か。みんな加筆してー。

加筆について

加筆したところに@USER@を付けてくれると、誰が書いたか分かりやすくていいと思うんだけど、どうだろう? -- carbon_twelve


Categoryノート

関数・論理型プログラミング実験/課題メモ (最終更新日時 2011-06-06 01:55:12 更新者 furaga)