6-2. リスト型のデータの処理

リストは、関数型言語では非常に頻繁に使われる基本的データ構造である。 (Lispという関数型言語では、その名前が List Processing に由来している。) OCaml では以下のように処理ができる。

[ ]                 (* 空リスト *)
1 :: [2; 3; 4]      (* リストの先頭に要素を追加; cons操作 *)
List.hd [1; 2; 3]   (* リストの先頭要素 *)
List.tl [1; 2; 3]   (* リストの先頭要素以外 *)
[1; 2; 3] = [1; 2; 3]  (* リストの比較 *)
match [1; 2; 3] with ... (* リストのパターンマッチ *)

これらのうち、match式を処理するのは大変であるので、それ以外の処理を実装しよう。まず、expと valueの拡張である。

type exp = 
  ...
  | Empty                 (* [ ] *)
  | Cons of exp * exp     (* e :: e *)
  | Head of exp           (* List.hd e *)
  | Tail of exp           (* List.tl e *)
  ...

type value = 
  ...
  | ListVal of value list

リストに対するCons操作 ( 1 :: [1; 2; 3] における :: の操作) の処理を以下に記述する。

(* eval5 : env -> (string * value) list -> value *)

let rec eval5 e env =
  ...
  match e with
  ...
  | Cons(e1,e2) ->
     begin
      match (eval5 e1 env, eval5 e2 env) with
      | (v1,ListVal(v2)) -> ListVal(v1 :: v2
     end
  ...

やや読みにくい感じもあるが、非常に簡潔に処理できることがわかるであろう。 Cons 以外の操作も全く同様であるので省略する。

課題 6-2.

上記にならって、List.hdや List.tl などに対応する操作を実装せよ。
上記の Cons操作の処理では、エラーとすべきものをそのまま処理してしまうことがある。たとえば、OCaml では 1 :: [true; false] という操作はエラーであるが、このインタープリタでは正常に計算してしまう。この点を改善することは可能か、考察せよ。
「整数のリスト」だけではなく、「整数のリストのリスト」などリスト構造がネストしたものに対しても、上記の実装が通用するかテストをせよ。
Eq はこれまでは整数値同士か真理値同士の比較であったが、リスト同士の等しさを調べる関数となるよう拡張せよ。 (リストの要素が再びリストであるかもしれないことに注意せよ。ただし、関数同士の等しさの比較は無理なので、エラーにしてよい。)

トップ, 前へ, 次へ.

亀山幸義