1-3. OCamlでの関数プログラミング

• プログラム言語を知る最善の方法は、そのプログラム言語の処理系を 書くことである。
  新しいプログラム言語を教えるとき、通常ならば、まず、その使い方に習熟し、 しかるべき後にその処理系の構成などを習うであろう。この実験では、 そうではなく、ほんの 1-2週間の使い方の練習の後、すぐさま、言語処理系の 作成をはじめる。つまり、プログラム言語の使い方を理解することと、 処理系を作成することがほとんど同時進行でおこなわれる。

  たとえば、fun x -> e という式は関数を表すが、いったいこれの意味は何 かまだよくわかっていないうちに、その形式を処理するプログラムを書き始め るのである。

  このようにする理由は、時間を節約するためではなく、むしろ、 「処理系を作成することが、そのプログラム言語を本当に理解するための近道 である。」という理由による。

• 関数型プログラム言語は、非常に表現力豊かである。
  実は、OCaml は「関数型プログラム言語らしくない」機能をいくつか持ってい る。たとえば、参照型 (ref型)を使えば、C言語の x = x + 1 と同じような 式を書くことができるし、文字列などに対する操作は破壊的代入(文字列の一部を別の文字 列に置換するとき、既存の文字列を破壊する)である。 これらの機能は impure (純粋でない)機能といわれている。

  効率などの理由により、これらの機能がどうしても必要な場面もあるのだが、 本実験では、関数型プログラム言語の表現力を理解してもらうため、 徹頭徹尾、これらの impure な機能を使わない という方針 で行く。(ただし、ファイルからの入出力などと、 例外処理機能は使う。)

  その方針であっても、本実験でわかるように、プログラム言語の機能を理解す るためには十分な処理系が書けてしまうし、多くのアルゴリズムも書けてしま う、ということを体験してほしい。

以上の方針のもとに、本実験で必要な機能を厳選したものが、以下のリストで ある。

• 変数、if then else, fun, let, let rec, match
• データ型: int、string, list、組(タプル)の型、関数の型、type定義
• ファイルの読み込み、print, 例外 (exception)

• 例題ファイル1 (基本)
• 例題ファイル2 (リスト)
• 例題ファイル3 (少しだけ型)

課題1.

• 2つの整数を与えられると、その最大公約数(Greatest Common Divisor) を求める関数 gcd を、 let rec, if then elseと、整数上の比較、引き算 などを使って記述せよ。

  ヒント: x,y ともに正の整数であるとき、以下が成立する。(Euclidの互除法)

  gcd(x,y) = x            if x=y
  gcd(x,y) = gcd(x-y, y)  if x>y
  gcd(x,y) = gcd(x, y-x)  それ以外
  

  
  もちろん、もっと効率よいアルゴリズムを使ってもよい。 ただし、上記の問題文では、与えられた整数は正とは限らないことに 注意せよ。
• Fibonacci数を計算する関数fibを定義せよ。ただし、

  fib(1) = 1
  fib(2) = 1
  fib(n+2) = fib(n) + fib(n+1)  if n>0
  

  である。

  (以下はオプショナル課題) 上記の定義を単純に実装すると非常に効率が悪い。 そこで、効率を改善したプログラムを実装せよ。 (ヒント: OCaml では、2つの数mとn の組は (m,n) という式で表現できる。)

• 正の整数nが与えられると、n番目の素数を計算する関数primeを定義せよ。たと えば、

  prime(1) = 2
  prime(3) = 5
  prime(5) = 11
  

  である。
• 文字列 s1 と文字列 s2 が与えられたとき、s1 に s2 が含まれているな らその位置を(複数含まれているなら、その一番左側の位置を)返し、 含まれていないなら -1 を返す関数 substring を定義せよ。 たとえば、

  substring "abcabc" "abc" = 0
  substring "abcabc" "bca" = 1
  substring "abcabc" "bcd" = -1
  

  である。
• 整数リストに対する Quick Sort Algorithm を実装せよ。

亀山 幸義