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

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

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

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

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

  書きたいプログラムの種類(アプリケーション分野)によっては、 実行効率などのために、これらのimpureな機能がどうしても必要な場面もあるのだが、 本実験では、関数型プログラム言語の表現力を理解してもらうため、 処理系の中核部分では、impure な機能を使わないという方針で行く。 impureな機能を使うのは、 処理系と実世界のインタフェース部分(ファイルへの読み書き、 端末へのプリント)や、エラーが起きたときの例外処理などに限定する。

  この方針であっても、 プログラム言語の機能を理解するためには十分な処理系が書ける、 ということを本実験で体験してほしい。

以上の方針のもとに、本実験で必要な機能を厳選したものが、 以下の言語プリミティブである。

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

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

課題1-3.

• 2つの整数(ただし、2つとも0である場合は考えなくてよい) を与えられると、その最大公約数(Greatest Common Divisor) を求める関数 gcd を、let rec, if then elseと、整数上の比較、引き算 などを使って記述せよ。

  ヒント: x,y がともに正の整数であるとき、xとyの最大公約数をGCD(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)  if x < y 
  

  
  なお、与えられた整数は両方とも正とは限らず、負や0のこともあり、 その時でも GCDが定義される限り(両方とも0でない限り)、 正しく動作するようにせよ。

  テスト・データ: OCamlでは「2引数関数」は、通常 gcd m n という形で記述 するので、ここでもそういう形に対するテストとする。)

  gcd 30 50  --> 10
  gcd 30 51  --> 3
  gcd 30 52  --> 2
  gcd 30 0   --> 30
  gcd  0 30  -->  30
  gcd (-3) 6 --> 3 (* 負の数には、かっこをつけること *)
  gcd (-3) (-6) --> 3 (* 「最大」公約数なので -3 でなく 3 になる *)
  gcd 0 0 --> ? (* GCD(0,0)は未定義なので何を返してもよい。停止しなくてもよい *)
  

• 正の数nに対して、n番目のFibonacci数を計算する関数fibを定義せよ。 つまり、

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

  となる FIB を計算する関数fib を定義してほしい。

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

  テスト・データ:

  fib 3 --> 2
  fib 4 --> 3
  fib 5 --> 5
  fib 7 --> 13
  fib 10 --> 55
  fib 20 --> 6765
  fib 30 --> 832040
  fib (-1) --> ? (* FIB(-1)は未定義なので何を返してもよい。停止しなくてもよい *)
  

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

  テスト・データ:

  prime 1 --> 2
  prime 2 --> 3
  prime 3 --> 5
  prime 4 --> 7
  prime 5 --> 11
  prime (-1) --> (* 未定義なので何を返してもよい。停止しなくてもよい *)
  

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

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

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

亀山 幸義