```花谷です。

> 遅延評価がどういうときになされるかをお尋ねしたいです。
>
ほとんどいつも遅延評価されると思います。

>
> なぜ、O(n)になると期待したかというと、
>   test "aaaaax" "aaaaay" "aaaaayaaaaax"
> =
>   test "aaaax" "aaaaay" "aaaayaaaaax" ||
>   test "aaaaax" "aaaay" "aaaayaaaaax"
> =
>   (test "aaax" "aaaaay" "aaayaaaaax"  ||
>    test "aaaax" "aaaay" "aaayaaaaax") ||
>   (test "aaaax" "aaaay" "aaayaaaaax"  ||
>    test "aaaaax" "aaay" "aaayaaaaax")
>

(a || b) || (b || c)

(a || b) を計算するには a の値が必要になって、
a が真ならb は評価されず、(b || c) も評価されずに計算終了。
a が偽なら b が評価されて…と続いていきます。

-- O(2^n/2) (?) の例

bar [] [] []         = True
bar (a:as) (b:bs) (c:cs)
| a == c && b == c = bar as (b:bs) cs || baz (a:as) bs cs
bar (a:as) bs (c:cs)
| a == c           = bar as bs cs
bar as (b:bs) (c:cs)
| b == c           = bar as bs cs
bar _ _ _            = False

baz [] [] []         = True
baz (a:as) (b:bs) (c:cs)
| a == c && b == c = baz (a:as) bs cs
baz (a:as) bs (c:cs)
| a == c           = bar as bs cs
baz as (b:bs) (c:cs)
| b == c           = bar as bs cs
baz _ _ _            = False

-- O(n^2) の例

u p (x:xx:xs)
| p x == p xx = u p (x:xs)
| otherwise = x:u p (xx:xs)
u p xs = xs

g as bs cs = g' cs [(0, (as, bs))]
where
g' [] ((_, ([], [])):_) = True
g' [] _ = False
g' _ [] = False
g' (c:cs) xs = g' cs \$ u fst \$ xs >>= h
where
h (i, (as, bs))
= (if not (null as) && head as == c
then [(i+1, (tail as, bs))]
else []
) ++
(if not (null bs) && head bs == c
then [(i  , (as, tail bs))]
else []
)

--