関数の評価についての注意

date:	2012/11/08

0. 概要
1. 準備
- 1.1 OR (||)
- 1.2 折り畳み
2. 止まるかどうか
3. まとめ
4. 余談

0. 概要

遅延評価をすると、正格評価で止まらない計算が止まること”も”ある
同じ動作を期待する関数でも、書き方が違えば止まらない
foldr (||) repeat True の評価が有限時間でできるかどうかを理解する

1. 準備

1.1 OR (||)

OR (||) とは、真偽値を2つとって、1つの真偽値を返すものです。例えば、

True || False      -- True になる

です。OR の返り値は以下の通りです。

	True	False
True	True	True
False	True	False

1.2 折り畳み

とある真偽値の無限リスト List があるとします。

[True, True, False, True, False, True, ....] -- ....以降は、何か複雑な列

リストのORによる右から左への折り畳み(注意: foldr1 (||) と言いたい) を

(True || (True || (False || (True || (False || (True || ....

とします。

ちょうとリストの ”,” の部分を (||) で置き換えた形になっています。括弧のつき方が、右から計算する形になっているので、右からの折り畳みと言います。

2. 止まるかどうか

さて、実際に次の式を評価した時に、無事に結果を得ることができるでしょうか?

(True || (True || (False || (True || (False || (True || ....

Answer:	できます

ちょっと (||) の定義を見てみましょう。

(||) :: Bool -> Bool -> Bool
True  || _              =  True
False || x              =  x

重要なのは2行目です。

1つ目の引数が True だったら、 2つ目の引数によらずに True を返す、と言っています。

遅延評価では、このような場合に2つ目の引数を評価しません。

つまり、先ほどの式では、

(True || "複雑なリスト" ....

という先頭の部分を評価した段階で結果が返ってくるので、無限リストに対しても評価を終えることができるのです。

Note

例えば、新しい関数 (|||) を次のように定義したとします。

(|||) :: Bool -> Bool -> Bool
True  ||| True  = True
True  ||| False = True
False ||| True  = True
Flase ||| False = False

このときに、先ほどと同様、リストの(|||)による右からの折り畳みを考えると、評価は終わりません。
この定義だと、かならず 第2引数が True か False か判別しない限り、どの行の結果を見れば良いかわからないからです。
逆に言えば、このように定義することで、第2引数は必ず評価されるようになります。

3. まとめ

遅延評価すごい。

4. 余談

Ruby でも遅延評価ができるようになると聞いてやってみた。 (参考: https://speakerdeck.com/nagachika/rubyist-enumeratorlazy)

p [true, false].cycle.lazy.any?
   # => true
p [1, -1].cycle.lazy.any?{|n| n < 0}
   # => true
#p [true, false].cycle.lazy.reduce{|res, item| res || item}
   # => これは結果が返らない

スライドを見る限り割と便利なので、早く Ruby 2.0 が標準になってほしい、と(Ruby 書けるわけでもないけど)思いました。

Study Haskell