小田です。どうもありがとうございました。
理解してからお返事しようと思っていたのですが、
特に最後のプログラムが難しく、
もう少し学ばなくてはと思っております。

> (a || b) || (b || c)
> 真ん中の || を計算するのには左側 (a || b) の真偽値が必要になって、
> (a || b) を計算するには a の値が必要になって、
> a が真ならb は評価されず、(b || c) も評価されずに計算終了。
> a が偽なら b が評価されて…と続いていきます。
> 特別な最適化を施さない限り、b は最大 2 回評価されてしまいます。

なるほど、preludeを見ると、
(||)  :: Bool -> Bool -> Bool
False || x   = x
True  || x   = True
とあるので、 a が評価されてから b が評価されるのですね。

b が最大 2 回評価されるかを調べるために下のようなコードを走らせて見ました。

hoge :: Int -> Int
hoge x = (2 * x + 1)
test :: Int -> Int -> Int
test x y = hoge x * hoge y
square :: Int -> Int
square x = x * x
test2 :: Int -> Int
test2 x = square (hoge x)

--test2 5 => (45 reductions, 54 cells)
--test 5 5 => (35 reductions, 44 cells)
となり、たしかに同じ引数で関数が呼ばれたならば、
前の計算結果を流用するといったことはないことが分かりました。

http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/external.html
の Lecture 2 と違う気がしていたのですが、
簡約が起きるのは同じ変数に束縛された時ということですね。
遅延評価に最外簡約以上のことを期待していたようです。


--
ML: haskell-jp / quickml.com
使い方: http://QuickML.com/