北海道苫小牧市出身の初老PGが書くブログ

永遠のプログラマを夢見る、苫小牧市出身のおじさんのちらしの裏

擬リスト

最近関数プログミラング入門を読んでるのだけど、擬リストって概念が新鮮だったのでメモ。

関数プログラミング入門 ―Haskellで学ぶ原理と技法―
Richard Bird 山下伸夫
427406896X

予備知識

擬リストの話をするのに必要な概念がボトムとか正格性とか。ボトムとは値の1つで、エラーとか無限ループとか、プログラムの結果を出力できない状態を表す。Perlで言えばdieとかwhile (1) {} とかだと思えばよい。これを⊥で表す。Haskellではundefinedと書く。

「関数fが正格である」とは、f ⊥ = ⊥であることを言う。これは値渡しな簡約をするLLではごく当たり前のことで、引数の式がエラーであればfを呼び出すまでもなくエラーが発生するという意味だ。「関数fが正格ではない」という状態は値渡しではなく遅延評価によって簡約する言語で初めて登場する。

ちなみに⊥はエラーとか無限ループなので、基本的にどの型にもありうる値となる。例えばHaskellのBool型はTrueとFalseと思われがちだが、実は⊥もBool型に含まれる。そういう意味では他の言語のnullやundefと同様の性質と思われるかもしれないが、評価した時に「うれしくない振る舞いをする」という点ではそれ以上のものとなる*1

擬リストとは

HaskellにおいてリストはNil(つまりは[ ])をベースに再帰的に定義される。例えば、[1, 2, 3]は1:2:3:[ ]のことだ。ところが、先ほど話したようにボトムも[Integer]の要素なため、[ ]を起点としない変なリストを作ることができる。具体的に言えば、1:2:3:undefinedのようなものだ。

ここで鍵となるのが最初に書いた非正格な関数の存在である。正格な関数しか書けない言語であれば、(:) 3 ⊥ == ⊥ となるので、1:2:3:undefinedも簡約すればundefinedと等価になってしまう。ところが、Haskellの値コンストラクタは非正格とされており*2、そのため 3:undefined と undefined は別のものとなる。実際に違いをheadで確かめてみよう。

Prelude> head (3:undefined)
3
Prelude> head undefined
*** Exception: Prelude.undefined

この1:2:3:undefinedが1:2:3:[ ]と違うのは見た目からも明らかだと思う。さらに、[1,2,3,undefined]とも全く違うことにも注意が必要。[1, 2, 3, undefined]は⊥を要素に含むもののあくまでも普通のリストだ。擬リストではない。

これらが全て本当に違うものだということは、lengthをとれば実証できるだろう。

Prelude> length (1:2:3:[])
3
Prelude> length [1,2,3,undefined]
4
Prelude> length (1:2:3:undefined)
*** Exception: Prelude.undefined


といったところで、2013年もよろしくお願い致します。

*1:nullやundefはどちらかと言えばMaybe

*2:newtypeで宣言した場合は正格