ハスケル配列があまりにも厳しいですか？

Question

私はHaskellでSmith-Watermanアルゴリズムを実装していますが、私はランタイムエラーになっている：私の実装では<<loop>>

は、私はHaskellのの怠惰な性質を利用しようとしているので、私は保存するために不変配列resarrayを使用します怠惰な再帰的スタブは、配列自体も参照している（依存関係のチェーンでresarrayは、resarrayに依存するcellに依存するcellDefに依存するzippedListに依存する）。各セルはインデックスの少ないセルを参照するので、計算は実行可能でなければなりません...しかし、それはそのように動作しません。コンセプトの証明として

、私はGHCiの中で次のことを試してみました：

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

、それが働きました。しかし、私の長い計算は、何らかの未知の理由で厳しくなってしまいます。ここで

は（、一緒にテストスクリプトとの完全なバージョン、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 

私はそれを解決することができますか？

Answer 1

あなたは動作しません。これは、構築しながら読むべき配列要素を強制的にその

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

、パターンマッチングにより、厳密であることです。

簡単な例：

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) 

作品が、代わりにmap fst RESPのリスト内包しています。 map snd、それはループします。 （リストの内包[way | ~(way,score) <- zippedList]で怠惰なパターンがなければならないとして）、少なくとも私は、依存関係の更なる問題が表示されていない

だからlazierバージョン map fst zippedListを使用して map snd zippedListは動作するはずです。

ペアのパターンマッチングにより、cellDef kは、トップレベルのコンストラクタが実際に(,)であるかどうかを十分に評価する必要があります。そのためには、分岐を決定しなければならず、それは以前の要素の含まれた値を検査する必要があります。しかし、配列が作成されている間、これらはまだ取得できません。

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

しかし、それは重要ではありません。必要なのは、依存サイクルがなく、すべてのチェーンが定義された基本ケースにつながることだけです。