Haskell arrays are too strict?

Question

I'm implementing Smith-Waterman algorithm in Haskell, but I'm getting a runtime error: <<loop>>

In my implementation, I'm trying to use the lazy nature of Haskell, so I use an immutable array resarray to store lazy and recursive stubs which also refer to the array itself (in a dependency chain resarray depends on zippedList which depends on cellDef which depends on cell which depends on resarray ). Each cell refers to a cell with lesser indexes, so the computation should be viable... albeit it doesn't behave that way.

As a proof of concept, I tried the following in ghci:

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

and it worked. However my longer computation ends up being strict for some unknown reason.

Here is my code (the complete version, together with a test script, is here ):

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

How can I fix it?

Answer 1

You're being strict by pattern-matching,

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

that forces the array elements to be read while constructing, which does not work.

Simple example:

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)

works, but with the list comprehensions instead of map fst resp. map snd, it loops.

So using the lazier version map fst zippedList and map snd zippedList should work (as should a lazy pattern in the list comprehensions [way | ~(way,score) <- zippedList]), at least I don't see further problems in the dependencies.

By pattern-matching on the pair, cellDef k must be evaluated far enough to see that the top-level constructor is indeed a (,). For that, the branch taken must be determined, and that requires inspecting the contained values of earlier elements. But while the array is created, these cannot yet be obtained.

Each cell refers to a cell with lesser indexes, so the computation should be viable

That, however, isn't important. All you need is that there are no dependency cycles, and every chain leads to a defined base case.