Tablice Haskell są zbyt rygorystyczne?

Question

Jestem wykonawczych Smith-Waterman algorytmu w Haskell, ale dostaję błąd wykonania: <<loop>>

W mojej realizacji, Próbuję użyć leniwy charakter Haskell, więc używam niezmienny tablicę resarray do przechowywania leniwe i rekursywne kody pośredniczące, które również odnoszą się do samej tablicy (w łańcuchu zależności resarray zależy od zippedList, która zależy od cellDef, która zależy od cell, która zależy od resarray). Każda komórka odnosi się do komórki z mniejszymi indeksami, więc obliczenia powinny być wykonalne ... ale nie zachowuje się w ten sposób.

Jako dowód koncepcji Próbowałem następujących w ghci:

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

i to działało. Jednak moje dłuższe obliczenia są z jakiegoś powodu nieznane.

Oto mój kod (pełna wersja, wraz ze scenariuszem testowym jest 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 

Jak mogę to naprawić?

Answer 1

Ty będąc ścisła przez wzorzec dopasowywania,

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

że zmusza elementów tablicy należy odczytywać podczas budowy, który nie działa.

Prosty przykład:

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) 

prace, ale z listowych zamiast map fst wzgl. map snd, pętle.

Więc korzystając z wersji Lazier map fst zippedList i map snd zippedList powinny pracować (jak powinno leniwy wzór w listowych [way | ~(way,score) <- zippedList]), przynajmniej ja nie widzę dalszych problemów w zależności.

Po dopasowaniu do pary, cellDef k należy ocenić na tyle daleko, aby przekonać się, że konstruktorem najwyższego poziomu jest rzeczywiście (,). W tym celu brana musi być określona, ​​a to wymaga sprawdzenia zawartych wartości wcześniejszych elementów. Ale gdy tworzona jest tablica, nie można ich jeszcze uzyskać.

To jednak nie jest ważne. Wszystko czego potrzebujesz to to, że nie ma cykli zależności, a każdy łańcuch prowadzi do zdefiniowanego podstawowego przypadku.