遅延評価は「同じ」変数(or部分式)ならば高々一回評価されるのであり、
件のケースは、たまたま異なる場所で、同じ関数が同じ引数で評価されて
いるだけであって、内部的にも別の式とされています。

関数の評価結果を憶えておいて、全く同じ引数で再び評価されたとき
憶えていた値を返すというのはmemoizationと呼ばれる手法です。

結果をmemoizeするようなコードを書いてみました。
--begin
test a b c = head $ head $ cache a b c

cache :: String -> String -> String -> [[Bool]]
cache []     bs cs     = [build2 bs cs]
cache (a:as) bs []     = [take (length bs + 1) $ repeat False]
cache (a:as) bs (c:cs) = [build a bs (c:cs) (head rs)] ++ rs
                          where rs = cache as bs cs

build :: Char -> String -> String -> [Bool] -> [Bool]
build a []     (c:cs) (x:xs) = [a==c && x]
build a (b:bs) (c:cs) (x:xs) = g a b c x : is
     where is        = build a bs cs xs
           g a b c x = (a==c && x) || (b==c && head is)
build a bs     []     _      = take (length bs + 1) $ repeat False

build2 :: String -> String -> [Bool]
build2 []     []     = [True]
build2 bs     []     = take (length bs + 1) $ repeat False
build2 []     _      = [False]
build2 (b:bs) (c:cs) = (b==c && head is) : is
                        where is = build2 bs cs
--end

再帰的な部分問題
『「aの先頭m文字を除いた列」と「bの先頭n文字を除いた列」を適当にinterleaveして
「cの先頭(m+n)文字を除いた列」になるか』
の結果の|a|×|b|テーブル(二重リスト)を作って、(0,0)を見ればOKという感じ。

問題となってるケース("a...x", "a...y", "a...y"++"a...x")では、"a..."の長さに対して
線形オーダーで計算できました。

-----
寺田 卓史 TERADA, Takuji
trad / psg.cs.titech.ac.jp


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