將runSTArray映射到STArrays列表中？

我有一個遞歸創建矩陣的扁平化列表的功能，它必須是可變的，因爲它們的元素在創建時經常更新。到目前爲止，我想出了一個具有簽名遞歸解決方案：將runSTArray映射到STArrays列表中？

doAll :: .. -> [ST s (STArray s (Int, Int) Int)]

的原因，我不返回[UArray (Int,Int) Int]直接是因爲doAll被遞歸調用，修改該列表中的矩陣的元素，並追加新的矩陣。我不想凍結和解凍矩陣不必要的。

到目前爲止這麼好。我可以在ghci

runSTArray (matrices !! 0) 
runSTArray (matrices !! 1)

檢查（的Array (Int, Int) Int型）n個矩陣確實爲我的算法正確的結果。但是，我沒有找到一種方法，在由doAll返回列表映射runSTUArray：如果我嘗試在列表遞歸評估或試圖評估包裹在一個單一的元素

map (runSTArray) matrices 

Couldn't match expected type `forall s. ST s (STArray s i0 e0)' 
      with actual type `ST s0 (STArray s0 (Int, Int) Int)'

同樣的問題發生函數

有人可以請解釋發生了什麼（我並不真正瞭解forall關鍵字的含義）以及如何評估列表中的數組？

來源

2011-11-28 bbtrb

http://www.mail-archive.com/[email protected]/msg47957.html –

這是類型伎倆，使ST安全的一個不幸後果。首先，你需要知道ST的工作原理。從ST monad到純代碼的唯一方法是使用runST函數或其他基於它的函數，如runSTArray。這些都是形式forall s.。這意味着，爲了從STArray構造一個數組，編譯器必須能夠確定它可以替換runST內s類型變量所喜歡的任何類型。

現在考慮功能map :: (a -> b) -> [a] -> [b]。這表明列表中的每個元素必須具有完全相同的類型（a），因此也是相同的s。但是這個額外的約束違反了runSTArray的類型，它聲明編譯器必須能夠自由地將其他值替換爲s。

您可以解決此通過定義一個新的功能，首先凍結ST單子裏面的陣列，然後運行所產生的ST行動：

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a] 
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze)

注意forall需要RankNTypes擴展。

來源

2011-11-28 16:19:08

謝謝你的解釋，這很有道理。但是，我必須在'runSTArrays'中刪除'runST'，然後單獨調用它。 'ghc'不能推導出上下文，也不能接受明確的類型註釋。 – bbtrb

對不起，我已經爲此代碼添加了適當的類型註釋。 GHC不會推斷出更高級別的註釋（全部），因此需要手動提供。 –

序列是否有一個佔位符，用於程序將「具有更新數組內容的某些功能」的位置？ – misterbee

你剛剛反彈了類型系統的侷限性。

runSTArray具有較高的排名類型。你必須傳遞一個ST行爲，其狀態類型變量是唯一的。然而，在Haskell中，通常不可能在列表中包含這樣的值。

整個事情是一個聰明的方案，以確保您在ST行動中產生的價值無法逃離那裏。這意味着，它看起來像你的設計在某種程度上被打破了。

一個建議：你不能在其他ST動作過程的值，比如

sequence [ ... your ST s (STArray s x) ...] >>= processing 
    where 
    processing :: [STArray s x] -> ST s (your results)

來源

2011-11-28 16:15:32 Ingo

我會感興趣的是，我的設計可能會被破壞（不是我懷疑它，我是對於haskell來說非常新穎）。你是否有一些關於如何管理不斷增長的可變矩陣列表以供評估的建議？ – bbtrb

@bbtrb - 也許這不是設計本身，而是希望與一系列'ST s ...'的東西一起工作。基本上，這樣的矩陣是可變數據，這意味着你不能（或者至少不應該）在ST或IO動作之外使用它們。確切地說，這是由John L告訴你的runST *系列功能強制實施的。 'freeze'只是告訴Haskell系統的一種方式，今後你想將矩陣（或其他）作爲只讀值處理，然後讓它在ST動作中構建的值的轉義（副本）。 – Ingo

將runSTArray映射到STArrays列表中？

回答

相關問題