長い上に初歩的な質問で申し訳ないですが、
遅延評価がどういうときになされるかをお尋ねしたいです。

米国のプログラミングコンテストに出題された問題で
Haskellを使えば容易に解けるのではと考えたのですが、
うまく行きませんでした。

次のような問題です。
文字列 A, B から、文字列 C を作れることを以下のように定義します。
文字列 C から適当な数の文字を間引く。残った文字列は A となり、
間引いた文字列はこの順で B となるような、
間引き方が存在するとき、文字列 A, B から、
文字列 C を作れると定義します。
三つの文字列、A,B,Cが与えられた時に、
A, B から C が作れるか作れないかを判定するプログラムを書け。

たとえば、
chocolate chips cchochiolpaste が与えられたら、
cChocHIolPaSte と大文字にしたところを間引けば、確かに作れています。


さて、O(n^2)程度で抑えられそうな、この問題がなぜ難問かというと、
再帰を使った安易なアルゴリズムで組むと
aaaaaaaaaax aaaaaaaaaay aaaaaaaaaaxaaaaaaaaaay
aaaaaaaaaax aaaaaaaaaay aaaaaaaaaayaaaaaaaaaax
の文字列の組が与えられた時に、O(2^n)になってしまいます。

つまり、例えばCで
int check(char* a,char* b,char* c)
{
    if(*a=='\0')
        return !strcmp(b,c);
    if(*b=='\0')
        return !strcmp(c,a);
    if(*c=='\0')
        return !strcmp(a,b);
    if(*a==*c && check(a+1,b,c+1))
        return 1;
    if(*b==*c && check(a,b+1,c+1))
        return 1;
    return 0;
}
とすると、aaaaaaaaaax aaaaaaaaaay aaaaaaaaaayaaaaaaaaaax の時に
初めにa,cの頭を削っていくのでO(2^n)となるのです。


で、遅延評価のおかげでO(n^2)になるだろうと期待して、
以下のような、素人っぽい Haskell ソースを書きました。

same :: String -> String -> Bool
same [] [] = True
same _ [] = False
same [] _ = False
same (x:xs) (y:ys) = if x /= y then False else same xs ys

tte :: String -> String -> String -> Bool
tte [] [] [] = True
tte _ _ [] = False
tte [] y z = same y z
tte x [] z = same x z

tte (x:xs) (y:ys) (z:zs) =
  (if x == z then tte xs (y:ys) zs else False) ||
  (if y == z then tte (x:xs) ys zs else False)

st :: Int -> Char -> [Char]
st n a = if n<=0  then [] else (a:st (n-1) a)

test n = tte (st n 'a' ++ ['x']) (st n 'a' ++ ['y'])
                (st n 'a' ++ ['x'] ++ st n 'a' ++ ['y'])


なぜ、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")

と展開されて、中の二行が同じになるために遅延評価が使われて
項数が深さ n に対して O(n^2) になると思いました。

ところが、実際に動かしてみると、O(2^n)になり、 test 20 あたりが限度だったのですが、
Haskellの遅延評価を利用して、基本的な構造を変えずに、これはO(n^2)になるでしょうか。

小田


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