Gli array Haskell sono troppo rigidi?

Question

sto implementando Smith-Waterman algoritmo in Haskell, ma sto ottenendo un errore di runtime: <<loop>>

Nella mia applicazione, sto cercando di usare la natura pigra di Haskell, quindi utilizzare un array immutabili resarray per memorizzare stub pigri e ricorsivi che fanno riferimento anche alla matrice stessa (in una catena di dipendenze resarray dipende da zippedList che dipende da cellDef che dipende da cell che dipende da resarray). Ogni cella si riferisce a una cella con indici minori, quindi il calcolo dovrebbe essere fattibile ... anche se non si comporta in questo modo.

Come una prova di concetto, ho provato quanto segue in ghci:

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

e ha funzionato. Tuttavia il mio calcolo più lungo finisce per essere rigido per qualche motivo sconosciuto.

Ecco il mio codice (la versione completa, insieme a uno script di test, è 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 

Come posso risolvere il problema?

Answer 1

Ti stai comportando rigorosa da pattern-matching,

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

che costringe gli elementi della matrice da leggere, mentre la costruzione, che non funziona.

semplice esempio:

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) 

opere, ma con l'elenco comprehension invece di map fst resp. map snd, loop.

Quindi, utilizzando la versione più pigri map fst zippedList e map snd zippedList dovrebbe funzionare (come dovrebbe un modello pigro nei list comprehension [way | ~(way,score) <- zippedList]), almeno io non vedo ulteriori problemi nelle dipendenze.

In base alla corrispondenza del modello sulla coppia, è necessario valutare il valore cellDef k in modo sufficiente per verificare che il costruttore di livello superiore sia effettivamente un (,). Per questo, il ramo preso deve essere determinato, e ciò richiede l'ispezione dei valori contenuti degli elementi precedenti. Ma mentre viene creato l'array, questi non possono ancora essere ottenuti.

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

Questo, tuttavia, non è importante. Tutto ciò che serve è che non vi siano cicli di dipendenza e che ogni catena porti a un caso base definito.