7

Haskell でSmith-Watermanアルゴリズムを実装していますが、実行時エラーが発生します。<<loop>>

私の実装では、Haskell の遅延性質を使用しようとしているので、不変配列を使用resarrayして、配列自体も参照する遅延および再帰スタブを格納します (依存関係チェーンでは、依存resarrayするzippedListものに依存するものに依存するcellDefものに依存するcellものに依存するもの)オンresarray )。各セルはインデックスが小さいセルを参照するため、計算は実行可能であるはずです...ただし、そのようには動作しません。

概念実証として、ghci で次のことを試しました。

let arr = listArray (0,3) [0, arr ! 0, arr ! 1, arr ! 2 ]

そしてそれはうまくいきました。ただし、私の長い計算は、何らかの理由で厳密になります。

これが私のコードです（テストスクリプトを含む完全なバージョンはこちらです）：

buildSWArray:: 
    WordSequence ->
    WordSequence ->
    SWMatrix
buildSWArray ws1 ws2 = let
        rows = arrLen ws1
        cols = arrLen ws2
        im = matToLinearIndex rows cols
        mi = linToMatIndex rows cols
        totsize = rows * cols
        ixarr = [0 .. (totsize-1)]
        cell i j 
            | i < 0 || j < 0 = 0
        cell i j  = 
            resarr !  (im i j ) 
        cellDef k | k == 0 = (None,0)
        cellDef k = 
            let
                (i,j) = mi k
                upwards = cell (i-1) j
                leftwards = cell i (j-1)
                diag = cell (i-1) (j-1) 
                -- One up if match, -5 if not match
                c = if ws1 ! i == ws2 ! j then 1 else (-5)
                hi = maximum [ 0, diag + c, upwards - 3, leftwards - 3]
            in 
                -- Dirty way of guessing which one was picked up
                case hi of 
                   hi | hi == 0  -> ( None, 0)
                   hi | hi == upwards - 3 -> ( Upwards, hi)
                   hi | hi == leftwards - 3 -> ( Leftwards, hi )
                   hi | hi == diag + c -> (Diag, hi )
        zippedList = [ cellDef k | k <- ixarr ]
        resarr =  IA.listArray (0,(totsize - 1)) [ score | (way,score) <- zippedList ]
        wayarr = IA.listArray (0,(totsize - 1)) [ way | (way,score) <- zippedList ]
    in 
        SWMatrix rows cols wayarr resarr

どうすれば修正できますか？

4

1 に答える 1

14

パターンマッチングで厳しくしている、

resarr =  IA.listArray (0,(totsize - 1)) [ score | (way,score) <- zippedList ]
wayarr = IA.listArray (0,(totsize - 1)) [ way | (way,score) <- zippedList ]

これは、構築中に配列要素を強制的に読み取らせますが、機能しません。

簡単な例:

module LazyArr where

import Data.Array.IArray

test :: Int -> (Array Int Int, Array Int Int)
test n =
    let zippedList = map foo [0 .. n]
        foo :: Int -> (Int,Int)
        foo i
            | i == 0 = (0,0)
            | arrOne ! (i-1) < arrTwo ! (i-1) = (2,1)
            | even i = (i,arrTwo ! (i-1))
            | otherwise = (arrOne ! (i-1),i)
        arrOne = listArray (0,n) $ map fst zippedList -- [a | (a,b) <- zippedList]
        arrTwo = listArray (0,n) $ map snd zippedList -- [b | (a,b) <- zippedList]
    in (arrOne, arrTwo)

map fst動作しますが、 respの代わりにリスト内包表記を使用します。map snd、ループします。

したがって、怠惰なバージョンを使用するmap fst zippedListと機能map snd zippedListするはずです（リスト内包表記の怠惰なパターンと同様[way | ~(way,score) <- zippedList]に）、少なくとも依存関係にそれ以上の問題は見られません。

ペアのパターン マッチングによりcellDef k、最上位のコンストラクターが実際に(,). そのためには、取られた分岐を決定する必要があり、それには以前の要素に含まれている値を検査する必要があります。ただし、配列が作成されている間は、これらはまだ取得できません。

各セルはインデックスが小さいセルを参照するため、計算は実行可能である必要があります

ただし、それは重要ではありません。必要なのは、依存関係のサイクルがなく、すべてのチェーンが定義済みの基本ケースにつながることだけです。

于 2013-03-06T18:06:53.437 に答える