Các mảng Haskell quá nghiêm ngặt?

Question

Tôi đang thực hiện Smith-Waterman thuật toán trong Haskell, nhưng tôi nhận được một lỗi runtime: <<loop>>

Trong thực hiện của tôi, tôi đang cố gắng để sử dụng bản chất lười biếng của Haskell, vì vậy tôi sử dụng một mảng bất biến resarray để lưu trữ các nhánh lười và đệ quy cũng tham chiếu đến mảng đó (trong chuỗi phụ thuộc resarray phụ thuộc vào zippedList phụ thuộc vào cellDef phụ thuộc vào cell phụ thuộc vào resarray). Mỗi ô đề cập đến một ô có chỉ số thấp hơn, do đó tính toán phải khả thi ... mặc dù nó không hoạt động theo cách đó.

Như một bằng chứng của khái niệm, tôi đã thử sau đây trong ghci:

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

và nó làm việc. Tuy nhiên, tính toán dài hơn của tôi sẽ trở nên nghiêm ngặt vì một số lý do không xác định.

Đây là mã (phiên bản hoàn chỉnh, cùng với một kịch bản thử nghiệm, là here) của tôi:

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 

Làm thế nào tôi có thể sửa chữa nó?

Answer 1

Bạn đang là nghiêm ngặt bởi mô hình khớp,

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

buộc các phần tử mảng được đọc trong khi xây dựng, mà không hoạt động.

đơn giản ví dụ:

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) 

công trình, nhưng với sự comprehensions danh sách thay vì map fst resp. map snd, nó lặp lại.

Vì vậy, sử dụng phiên bản lazier map fst zippedList và map snd zippedList nên làm việc (như cần một mô hình lười biếng trong comprehensions danh sách [way | ~(way,score) <- zippedList]), ít nhất là tôi không thấy vấn đề hơn nữa trong sự phụ thuộc.

Bằng cách khớp mẫu trên cặp, cellDef k phải được đánh giá đủ xa để thấy rằng hàm tạo cấp cao nhất thực sự là (,). Đối với điều đó, nhánh phải được xác định và yêu cầu kiểm tra các giá trị chứa của các phần tử trước đó. Nhưng trong khi mảng được tạo, thì chúng chưa thể có được.

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

Điều đó, tuy nhiên, không quan trọng. Tất cả những gì bạn cần là không có chu trình phụ thuộc, và mỗi chuỗi dẫn đến một trường hợp cơ bản đã định nghĩa.