Are Haskell arrays too strict?

Question

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

In my implementation, I am trying to use the lazy character of Haskell, so I use an immutable resarray array to store lazy and recursive stubs that also apply to the array itself (in the dependency chain, resarray depends on zippedList , which depends on cellDef , which depends on cell , which depends on from resarray ). Each cell refers to a cell with lower indices, so the calculation must be viable ... although it does not behave this 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 calculations end up being rigorous for an unknown reason.

Here is my code (full version, along with a test script, 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 ij | i < 0 || j < 0 = 0 cell ij = resarr ! (im ij ) 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 this?

Answer 1

You strictly adhere to patterns,

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

which forces the elements of the array to be read during construction, which does not work.

A 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 given the list instead of map fst respectively. map snd , it is a loop.

Thus, using the map fst zippedList version of map fst zippedList and map snd zippedList should work (like the lazy template in the list comprehensions [way | ~(way,score) <- zippedList] ), at least I don’t see any additional problems in the dependencies .

By the figurative coincidence in the cellDef k pair, cellDef k necessary to evaluate far enough to see that the top-level constructor is indeed (,) . To do this, it is necessary to determine the occupied branch, and this requires checking the contained values ​​of earlier elements. But while the array is created, they still cannot be retrieved.

Each cell refers to a cell with lower indices, so the calculation must be viable

This, however, is not important. All you need is the absence of dependency cycles, and each chain leads to a specific base case.