OCamlの入門文書を読んでいて「再帰データ型」というものを見かけました。
type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree ;;
treeはLeafもしくはNodeですが、Leafの場合は値（'a）を持ち、Nodeの場合は'a型のtreeをふたつ持つ、という意味です。「'a」というのはMLで多相型を表現するためのもので、'aのかわりにintでもfloatでもstringでも入れることができるものです。型宣言の中に「もしくは」が使えるのに感心してしまいました（C言語でもunionとかで似たようなことができるかもしれません）。
これをLISPで書いたらどういう風になるんだろうかと考えてみましたが、LISP経験がなさすぎて訳が分からなくなりました。まず多相型に関しては静的型付け言語だからこそ必要になる仕組みなので、LISPのような動的型付け言語には必要ありません。リストにどんな型の値でも入れることができるため、tree型を作ったとしても「ひとつのtreeにはひとつの型しか入れることができない」という制約はなさそうです。
(list 1 "hoge" 3.14)
さて再帰データ型です。LISPではどうやるんでしょう？ LISPにデータ型を作るという考え方があったかどうかも定かじゃなくなってしまいました。オブジェクト指向言語ではクラス内に変数とメソッドを書きますが、LISPではメソッドしか存在しないような印象があります。LISPでは型を書くこととアルゴリズムを書くこととが同じような気がしてしまうのです。
