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

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

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

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

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

  書きたいプログラムの種類(アプリケーション分野)によっては、 実行効率などのために、これらのimpureな機能がどうしても必要な場面もあるのだが、 本実験では、関数型プログラム言語の表現力を理解してもらうため、 極力、impure な機能を使わない という方針で行く。 (ただし、ファイルからの入出力、例外処理機能は使う。)

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

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

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

• 例題ファイル1 (基本)
• 例題ファイル2 (リスト)
• 例題ファイル3 (型の基本)

課題1-3.

• 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 を実装せよ。

亀山 幸義