HaskellでLCS(最長共通部分列問題)

LCSは以前C++で

最長共通部分列(LCS)
http://d.hatena.ne.jp/g940425/20110210/1297296036

書きましたが、ちょっと今回Haskellで書いてみようと思います。

動機は、Haskellでは代入ができないのでループを回して二次元配列を更新、という従来の手続き型DPが書けないとのことなので、純粋関数型言語のDPを練習をしようと思った次第です。

意外と簡単に書けるものですね。

ちなみに、下のコードを書くにあたり、以下のサイトを参考にしました。

「Haskell の多次元配列(tnomuraのブログ)」
http://tnomura9.exblog.jp/10407594/

「Haskell で動的計画法を書くための3つの方針(tosの日記)」
http://d.hatena.ne.jp/toslunar/20100408/1270719176

２変数関数fがDPの漸化式で、これをDP配列の値であると定義してやれば、あとはリスト内包表記で書けばインデクスが回ってDP配列を逐次的に計算してくれます。

リスト内包表記はうまく使うと便利ですね。

import Array

lcs l1 l2 =
    let dp = array ((0,0),((length l1),(length l2))) [((i,j),f i j)|i<-[0..(length l1)],j<-[0..(length l2)]]
             where
               f i j = if (i==0||j==0) then
                           0 
                       else if l1!!(i-1)==l2!!(j-1) then 
                                (dp!(i-1,j-1))+1 
                            else  (max (dp!(i-1,j)) (dp!(i,j-1)))
    in
      dp!((length l1),(length l2))

main = do str1 <- getLine
          str2 <- getLine
          putStrLn (show (lcs str1 str2))

C++に比べて短く書けていいですねー。

トレースバックはまだ実装してませんが、後日実装すると思いますので、そのときはまた書きます。

ちょっとHaskell練習中なのでこれから記事にしていこうかと思います。