7つの言語7つの世界 - Prolog Day 2

Seven Languages in Seven Weeksを読んでいる。

この本の英語原著である。英語を解読しながらなのでちょっと時間がかかっているものの、とても面白い。 邦題はサピア=ウォーフをイメージして付けたんだろうなぁ。 確かに言語によって頭の使い方が変わるのがはっきりわかる。 いろんな考え方を学び取るのにとてもよい本である。

今Prologの2日目の課題を終えたところ。 Prologのような宣言型の言語は触ったことが無かったので、 とても新鮮。目から鱗が落ちっぱなし。 もう少し詳しく理解してからにして、まずはProlog編二日目の問題について回答をあげてみる。 この本に載っていた例題から、数学帰納法っぽい考え方で書けばいいのかと見て取りつつ、実際に書いてみた。 実際のソースコードファイルはgithubにアップロードした。

  • リストを逆に並べ替える

      (1)要素数0のリストの場合、逆順にしたリストともともとのリストは同値である。  
       従って、逆順に並べ替えたものを作成することは可能である。  
      (2)要素数kのリストが逆順に並べ替えられたと仮定した場合、  
        要素数k+1のリストが逆順に並べ替えられることを証明する。(k>=0とする)  
        要素数k+1のリストをXとし最初の1要素aと後ろの要素数kのリストBに分ける。  
        当初の仮定により、Bは逆順にすることができる。  
        Bの末尾にaを結合したものは、もともとのリストを逆順にしたものと一致する。  
        (aは元の要素の先頭要素であり、逆順にしたリストでは最後尾になるためである) 
        要素数k+1のリストを逆順に並べ替えることができる。  
    

(1), (2)より、任意のリストを逆順に並べ替えることができる。Q.E.D.

落とし込んだソースコード

myReverse([], []). %(1)
myReverse(Answer, [Head|Tail])
 :- myReverse(List, Tail), append(List, [Head], Answer). %(2)

・最小要素を探せ

	(1)1要素のリストの場合、唯一含まれる要素が最小であることは自明である。
	(2)要素数k+1のリストから最小値を発見できるものと仮定した場合、
	  要素数k+1のリストから最小値を発見できることを証明する。(k>=1とする)
	  要素数k+1のリストをXとし、最初の1要素a及び残りのk個の要素で構成されるリストLに分割する。
	  当初の仮定により、Bに含まれる要素のうちの最小要素を導くことができ、これを仮にxとする。
	  もしここでa <= xであれば、xはBの要素の中で最小値であるため、Bの要素は全てa以上である。
	  従ってXに含まれる値の最小値はaである。
	  a > xであれば、xはa及びその他全てのXに含まれる要素より小さいため、
	  Xの最小値はxとなる。
	  以上により、k要素中で最小値を発見できる場合、要素数k+1のリストから最小値を発見することができる。

(1),(2)より、任意のリストから最小値を発見することができる。Q.E.D.

落とし込んだソースコード

myMin(X, [X|[]]).
myMin(Ans, [Head|Tail]) :- myMin(Ans2, Tail), Ans is min(Head, Ans2).

・リストのソート 今回実装したのは、高速なソートアルゴリズムのうちで一番簡単そうな挿入ソート。 分割統治が必要なものは、ちょっと混乱したのでもうちょっと考えることにする。 挿入アルゴリズムを実装し、それを用いて挿入ソートを実装する。

-挿入アルゴリズム

	(1)要素数0のリストにXを挿入する場合、末尾に挿入して要素数1のリストを作成すればよい。
	(2)要素数kのリストに正しく値を挿入できると仮定した場合、
	  要素数k+1のリストに挿入できることを証明する。
	  要素数k+1のリストにxを挿入する場合、
	  最初の1要素よりもxが小さい場合は先頭に加えればよい。
	  最初の1要素よりも大きい場合は後ろのk要素のどこかに挿入することになるが、
	  これは当初の仮定により正しく挿入することができる。
	  要素数k+1のリストの正しい位置に値を挿入することが可能である。

(1),(2)より、任意のリストに任意の要素を正しく挿入することができる。Q.E.D.

落とし込んだソースコード

myInsert(Answer, AddObject, []) :- append([AddObject], [], Answer).
myInsert(Answer, AddObject, [Head|Tail])
 :- (AddObject < Head), append([AddObject], [Head|Tail], Answer).
myInsert([Head|Answer], AddObject, [Head|Tail])
 :- ¥+(AddObject < Head), myInsert(Answer, AddObject, Tail).

挿入ソート (1)要素数1のリストが整列済みのリストであることは自明である。 (2)要素数kのリストをソートすることができる場合、   要素数k+1のリストをソートすることができることを証明する。   要素数k+1のリストを先頭要素aとその他のk個の要素からなるリストLに分割する。   当初の仮定より、Lはソートすることが可能である。   ソート済みのリストL’の中にaを挿入したものは、要素数k+1のリストをソートしたものである。

(1),(2)より、任意のリストのソートが可能である。Q.E.D.

落とし込んだソースコード

myInsertionSort(Answer, [Head|[]]) :- myInsert(Answer, Head, []).
myInsertionSort(Answer, [Head|Tail]) :- myInsertionSort(SubAnswer, Tail), myInsert(Answer, Head, SubAnswer).

おまけ ・フィボナッチ数列

fib(1, 0).
fib(1, 1).
fib(Answer, Counter) :-
  Counter > 1,
  SubC1 is Counter - 1, fib(SubA1, SubC1),
  SubC2 is Counter - 2, fib(SubA2, SubC2),
  Answer is SubA1 + SubA2.

・階乗

fact(1, 0).
fact(Answer, Counter) :-
  Counter > 0,
  SubCounter is Counter - 1,
  fact(SubAnswer, SubCounter),
  Answer is SubAnswer * Counter.

まだちょっとしか触っていないけど、Prologは面白い。 記載するのはアルゴリズムではなく、解きたい問題の状況設定。 どんな問題なのか教えてさえあげれば、Prolog君が良きに計らって解いてくれる。 すっきり書けると、なんだか計算機と仲良くなれたような気がして楽しい。 これからScala, Erlang, Clojure等々個性的な言語が並んでいるので楽しみ。

Written on December 3, 2011