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 fstresp。map snd，它循环。

因此，使用惰性版本map fst zippedList并且map snd zippedList应该可以工作（列表推导中的惰性模式也应该如此[way | ~(way,score) <- zippedList]），至少我在依赖项中没有看到进一步的问题。

通过对对的模式匹配，cellDef k必须评估足够远以看到顶级构造函数确实是 a (,)。为此，必须确定所采用的分支，这需要检查早期元素的包含值。但是在创建数组时，这些还不能获得。

每个单元格引用索引较少的单元格，因此计算应该是可行的

然而，这并不重要。您所需要的只是没有依赖循环，并且每条链都会导致定义的基本案例。

于 2013-03-06T18:06:53.437 回答