lcs.hs

--ST Monad instead!
lcs :: (Eq a) => [a] -> [a] -> [a]
lcs s' t' = reverse $ build n m
  where
    a = runST $ do  
          b <- newArray ((0,0),(n,m)) 0
          mapM_ (f b) $ range ((0,0),(n,m))
          unsafeFreeze b
    n = length s'
    m = length t'
    s = listArray (0,n-1) s'
    t = listArray (0,m-1) t'
    f ::STArray s (Int,Int) Int -> (Int,Int) -> ST s ()
    f b (i,j) 
      | min i j == 0  = writeArray b (i,j) 0
      | otherwise     = 
          if s!(i-1) == t!(j-1) then do
            x <- readArray b (i-1,j-1)
            writeArray b (i,j) (x + 1)
          else do
            x <- readArray b (i-1,j)
            y <- readArray b (i,j-1)
            writeArray b (i,j) (max x y)
    build i j 
      | min i j == 0          = []
      | s!(i-1) == t!(j-1)    = (s!(i-1)):build (i-1) (j-1)
      | a!(i,j-1) > a!(i-1,j) = build i (j-1)
      | otherwise             = build (i-1) j

哈囉~ 我讀你的這份程式碼裡面, 有用到 mutable STArray.
不過其實你對每一個 element 都只有寫入一次,
所以這一個情況下, 是可以用 immutable Array 的
(不過因為 element 之間有 dependency, 所以必須用 lazy boxed 的, 不能用 strict unboxed 的)

因為我對實際寫 Haskell 程式也不是很熟,
所以就藉這機會拿這題目自己練習一下.
這邊是我練習的程式碼 https://gist.github.com/6b0d01fd200124d12dba

我寫的 immutable Array 版本沒有比你的 mutable STArray 短,
不過應該比較像在寫 Functional Language, 沒有像在寫 C 的感覺 ^^
實際跑起來 immutable Array 花的時間大約是 STArray 版本的 1/4 ~ 1/5.
( 用 ghc -rtsopts --make Main 沒有開特殊的最佳化選項 )

不過如果不要把輸入放到 Eq a => [a] 這麼一般化的話,
ST 版可以改用 STUArray, 少一層 reference 可以再快一些.
不知道可以加快多少~

我沒有測到長度 10000, 只有測到 5000.
我用筆電跑的, 10000 會跑不太動 ^^|