Haskell数组过于严格？

Question

Haskell数组过于严格？

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

我该如何修复它？

- dsign

我猜你没有正确地“系好结”。检查你的基本情况并验证你的递归参数是否在减少。 - cdk

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

您正在通过模式匹配严格检查，

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和map snd，可以使其正常工作，但会循环遍历。

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

通过对配对进行模式匹配，必须评估cellDef k，以查看顶层构造函数是否确实为(,)。为此，必须确定所采取的分支，并且这需要检查先前元素的包含值。但是，在创建数组时，这些值尚无法获得。

每个单元格都引用具有较小索引的单元格，因此计算应该可行

然而，这并不重要。您只需要确保不存在依赖循环，并且每个链都通向定义的基本情况。