akimachoのはてなブログ

ICTとデザインのためのブログ

『プログラミングの基礎』読書日誌-20日目-

はじめに

今日は,第20章 再帰的なデータ構造です.

バリアント型

バリアント(variant)型とは,いくつかの要素のうちひとつしかないデータ型を指します.バリアント型は構成子(constructior)から構成されます.構成子の名前は,大文字で始まらなければなりません.以下の例では,RedとWhiteが構成子です.

(* 赤組か白組かを表す型 *)
type バリアント型名 = 構成子1 | 構成子2 | ・・・ | 構成子N

バリアント型の構成子に引数を持たせる場合は次のように書きます.

構成子 of

また,バリアント型のパターンマッチは次のようになります.

match 変数 with
    構成子1 ->1
  | 構成子2 ->2

バリアント型では,再帰的な定義が可能です.その例として,データ構造としての木(tree,木構造)をみていきます.木は,空の木(empty tree)・葉(leaf)・節(node)から構成され,OCamlでは以下のようなコードで書くことができます(2分木です).

type tree_t = Empty (* 空の木 *)
  | Leaf of int (* 葉 *)
  | Node of tree_t * int * tree_t (* 節 *)

再帰的なデータ構造に対するデザインレシピ

データ定義

再帰的なデータ構造が必要になるときは,自己参照しないケース・自己参照が含まれているケースを確認し,それをコメントとして明示しておく.この時に,データの例を作成しておく.

テンプレート

対応するmatch文を,再帰的なデータ構造の定義と1対1対応するように作成する.

おわりに

Emacsのtuareg-modeというので,OCamlのコードを書くようになりました.便利です.

入門OCaml ~プログラミング基礎と実践理解~

入門OCaml ~プログラミング基礎と実践理解~

プログラミングの基礎 (Computer Science Library)

プログラミングの基礎 (Computer Science Library)