花谷です。

> 遅延評価がどういうときになされるかをお尋ねしたいです。
>
ほとんどいつも遅延評価されると思います。
遅延評価ってのは単に最外簡約しているだけなのではないでしょうか。
>
> なぜ、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 || b) を計算するには a の値が必要になって、
a が真ならb は評価されず、(b || c) も評価されずに計算終了。
a が偽なら b が評価されて…と続いていきます。
特別な最適化を施さない限り、b は最大 2 回評価されてしまいます。

-- 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 []
               )


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