Hatena::Grouphaskell

Haskellで遊ぶよ

 | 

2009-06-01

diff

09:49

Haskell で diff を書こうと頑張ったんだけど、出入力とかのあたりに来たら急にヤル気が落ちていったので、とりあえずここらで書いておこうと思う。

アルゴリズムについては以下を読んで学んだ。リンク先の説明でもまだ分かりにくいのだけれど、自前では説明したくても面倒くさすぎる。

一つ目のリンクにはコード例が載っていて、(そのままでは動かないのだけど) 参考になった。

まず、以下が単純に O(NP) アルゴリズムによる探索をする部分。

onp :: (Eq a) => [a] -> [a] -> Int 
onp listA listB
    | delta < 0 = startONP listB listA
    | otherwise = head [p | p <- [0..], n == fp delta p ]
    where
        delta = n - (length listA)
        n = length listB
        fp = fpGen listA listB

-- generates fp 
-- fp returns y coordinate of the furthest point reachable on diagonal k, with detour p
fpGen :: (Eq a) => [a] -> [a] -> (Int -> Int -> Int)
fpGen listA listB = fp
    where 
        fp k p 
            | p == -1       = 0
            | k < - p       = 0
            | k > delta + p = 0
            | k == delta    = snake k $ max ((fp (k-1) p)     + 1) (fp (k+1) p)
            | k < delta     = snake k $ max ((fp (k-1) p)     + 1) (fp (k+1) (p-1))
            | k > delta     = snake k $ max ((fp (k-1) (p-1)) + 1) (fp (k+1) p)
        delta = (length listB) - (length listA)
        snake = snakeGen listA listB

-- generates snake
-- snake returns, for given k and y0, y coord of the point along the diagonal 
--      as far as the elems in A and B at the point are identical
snakeGen :: (Eq a) => [a] -> [a] -> (Int -> Int -> Int)
snakeGen listA listB = snake
    where
        snake k y0 = (+y0).length.takeWhile (==True) $ zipWith (==) (drop (y0-k) listA) (drop y0 listB)

main = print $ onp [1,2,3,4,5,6,7,8] [1,3,2,4,5,7,8,8,9,6]

与えられたリストによって、fp 関数 (例では配列だけど、Haskell では遅延評価があるので関数のほうが都合がいい)、と snake 関数を生成している。

上から4行目。

head [p | p <- [0..], n == fp delta p ]

普通なら fp(k,p) において、p を 0 から増やしつつ、k を [-p, delta + p] の範囲で変化させるロジックを書かなくてはならないのだけど、今回は「後ろから」評価することにしたため、

fp k p

とするだけでいい。探索の終了条件は、fp delta p が n と等しくなるとき。なので、head とリスト内包表記で書いた。

ここでちょっと問題があって、p が 0 から増やされる度に同じ引数で fp が計算されることがある。これはとりあえず課題として置いておく。

State モナドとかメモ化とか読んでみたけど、まだ全然理解できない。


次に、探索したルートを巡れるようにする。

そこで、k と y の値のタプルを繋げるリストを、Chain 型として定義した。

-- Chain type --
type Chain = [(Int,Int)]

stepRight,stepDown,slide :: Chain -> Chain
stepRight ((k,y):ns) = (k + 1 , y + 1):(k,y):ns
stepDown  ((k,y):ns) = (k - 1, y):(k,y):ns
slide     ((k,y):ns) = (k, y + 1):(k,y):ns

progress :: Chain -> Int
progress [] = 0
progress ((_,y):_) = y

diagonal :: Chain -> Int
diagonal [] = 0
diagonal ((k,_):_) = k

toXY :: Chain -> [(Int,Int)]
toXY [] = []
toXY ((k,y):ns) = (y-k,y):(toXY ns)
-- end --

onp :: (Eq a) => [a] -> [a] -> [(Int,Int)]
onp listA listB
    | delta < 0 = zipSwap $ onp listB listA
    | otherwise = reverse.toXY.head.dropWhile ((/=n).progress) $ map (fp delta) [0..]
    where
        delta = n - (length listA)
        n = length listB
        fp = fpGen listA listB

-- generates fp 
-- fp returns y coordinate of the furthest point reachable on diagonal k, with detour p
fpGen :: (Eq a) => [a] -> [a] -> (Int -> Int -> Chain)
fpGen listA listB = fp
    where 
        fp k p 
            | p < 0         = []
            | k < - p       = []
            | k > delta + p = []
            | k == delta    = snake k $ further (fp (k-1) p) (fp (k+1) p)
            | k < delta     = snake k $ further (fp (k-1) p) (fp (k+1) (p-1))
            | k > delta     = snake k $ further (fp (k-1) (p-1)) (fp (k+1) p)
        delta = (length listB) - (length listA)
        snake = snakeGen listA listB

-- analogy of "max (a+1) b" for Node
further :: Chain -> Chain -> Chain
further left upper
    | left == [] && upper == []          = [(0,0)]
    | left == []                         = stepDown upper
    | upper == []                        = stepRight left
    | progress left + 1 < progress upper = stepDown upper
    | otherwise                          = stepRight left

-- generates snake
-- snake returns, for given k and y0, y coord of the point along the diagonal 
--      as far as the elems in A and B at the point are identical
snakeGen :: (Eq a) => [a] -> [a] -> (Int -> Chain -> Chain)
snakeGen listA listB = snake
    where
        snake k chain = foldl (\chn _ -> slide chn) chain [1..len]
            where
                len = let y0 = progress chain
                      in  length.takeWhile (==True) $ zipWith (==) (drop (y0-k) listA) (drop y0 listB)

fp、snake、max という関数を、Chain 型を使って定義する。例えば fp は、(与えられた k と p に対して)「到達できる最遠点の y 座標」を返していたのだが、「到達できる最遠点までのルート」を返すようにした。

これで、onp 関数は、終点に到達するまでのルートの座標を返すようになった。


その座標から unified format に直す部分を考えていて、面倒になってきたので一旦ここで止めとく。

またヤル気が出たら始めるということで。

トラックバック - http://haskell.g.hatena.ne.jp/edvakf/20090601
 |