跳轉到內容

Haskell/Libraries/Arrays

Add links
來自華夏公益教科書，開放書籍，共建共享世界
Arrays (Solutions)
庫參考

介紹
Maybe
IO
Random
資料結構入門 75% developed
陣列
對映

Haskell'98 只支援一個數組建構函式型別，即 Array，它提供不可變的盒子陣列。 "不可變"意味著這些陣列，就像任何其他純函式式資料結構一樣，其內容在構造時固定。 您不能修改它們，只能查詢。 存在“修改”操作，但它們只是返回新陣列，不修改原始陣列。 這使得可以在純函式式程式碼中將陣列與列表一起使用。 "盒子"意味著陣列元素只是普通的 Haskell（惰性）值，這些值在需要時進行評估，甚至可以包含底層（未定義）值。 您可以在 http://haskell.org/tutorial/arrays.html 中學習如何使用這些陣列，我建議您在繼續本頁面的其餘部分之前閱讀它。

如今，主要的 Haskell 編譯器 GHC 和 Hugs 附帶相同的 分層庫 集，這些庫包含陣列的新實現，該實現與 Haskell'98 的實現向後相容，但功能更多。 不用說，這些庫支援 9 種陣列建構函式型別：Array、UArray、IOArray、IOUArray、STArray、STUArray、DiffArray、DiffUArray 和 StorableArray。 不難理解為什麼陣列庫會讓新來的 Haskellers 感到困惑。 但是，它們實際上非常簡單 - 每個都只提供兩種介面中的一種，而其中一種您已經知道。

快速參考

[編輯 | 編輯原始碼]
不可變
instance IArray a e 		IO 單子
instance MArray a e IO 		ST 單子
instance MArray a e ST
標準 Array
DiffArray 		IOArray STArray
非盒子 UArray
DiffUArray 		IOUArray
StorableArray 		STUArray

不可變陣列

[編輯 | 編輯原始碼]

新陣列庫提供的第一個介面由型別類 IArray（代表“不可變陣列”，在模組 Data.Array.IArray 中定義）定義，並定義了與 Haskell '98 中為 Array 定義的相同操作。 以下是一個簡單示例，演示了它的用法，該示例列印 (37,64)

import Data.Array
buildPair :: (Int, Int)
buildPair = let arr  = listArray (1,10) (repeat 37) :: Array Int Int
                arr' = arr // [(1, 64)]
            in (arr ! 1, arr' ! 1)

main = print buildPair

最大的區別在於它現在是一個型別類，並且有 4 種陣列型別建構函式，每種都實現了此介面：Array、UArray、DiffArray 和 DiffUArray。 我們稍後將描述它們之間的差異以及何時優先使用這些其他型別而不是傳統的 Array。 還要注意，要將 Array 型別建構函式與其他新陣列型別一起使用，您需要匯入 Data.Array.IArray 模組而不是 Data.Array。

可變IO陣列

[編輯 | 編輯原始碼]

第二個介面由型別類 MArray（代表“可變陣列”，在模組 Data.Array.MArray 中定義）定義，幷包含在適當位置更新陣列元素的操作。 可變陣列與 IORefs 非常相似，只是它們包含多個值。 可變陣列的型別建構函式是 IOArray 和 IOUArray（在 Data.Array.IO 中），建立、更新和查詢這些陣列的操作都屬於 IO 單子

import Data.Array.IO
main = do arr <- newArray (1,10) 37 :: IO (IOArray Int Int)
          a <- readArray arr 1
          writeArray arr 1 64
          b <- readArray arr 1 
          print (a,b)

此程式建立了一個包含 10 個元素的陣列，所有值最初都設定為 37。 然後它讀取陣列的第一個元素。 之後，該程式修改陣列的第一個元素，然後再次讀取它。 第二行中的型別宣告是必要的，因為我們的小程式沒有提供足夠的上下文來允許編譯器確定 arr 的具體型別。

ST單子中的可變陣列

[編輯 | 編輯原始碼]

與 IORef 具有更通用的兄弟 STRef 一樣，IOArray 也具有更通用的版本 STArray（類似地，IOUArray 由 STUArray 模仿；兩者都在 Data.Array.ST 中定義）。 這些陣列型別允許人們在 ST 單子中使用可變陣列

import Control.Monad.ST
import Data.Array.ST

buildPair = do arr <- newArray (1,10) 37 :: ST s (STArray s Int Int)
               a <- readArray arr 1
               writeArray arr 1 64
               b <- readArray arr 1
               return (a,b)

main = print $ runST buildPair

信不信由你，現在您已經知道了使用任何陣列型別所需的所有知識。 除非您對速度問題感興趣，否則只需在適當的地方使用 Array、IOArray 和 STArray。 以下主題幾乎完全是關於選擇合適的陣列型別以使程式執行得更快。

凍結和解凍

[編輯 | 編輯原始碼]

Haskell 允許使用 freeze 和 thaw 函式在不可變陣列和可變陣列之間進行轉換

freeze :: (Ix i, MArray a e m, IArray b e) => a i e -> m (b i e)
thaw   :: (Ix i, IArray a e, MArray b e m) => a i e -> m (b i e)

例如，以下將 Array 轉換為 STArray，修改它，然後轉換回來

import Data.Array
import Control.Monad.ST
import Data.Array.ST

buildPair :: (Int, Int)
buildPair = let arr  = listArray (1,10) (repeat 37) :: Array Int Int
                arr' = modifyAsST arr
            in (arr ! 1, arr' ! 1)

modifyAsST :: Array Int Int -> Array Int Int
modifyAsST arr = runST $ do starr <- thaw arr
                            compute starr
                            newarr <- freeze starr
                            return newarr

compute :: STArray s Int Int -> ST s ()
compute arr = do writeArray arr 1 64

main = print buildPair

凍結和解凍都會複製整個陣列。 如果你想在凍結或解凍之前和之後使用相同的記憶體位置，但可以允許一些訪問限制，請參閱 不安全操作和遍歷陣列元素 部分。

DiffArray

[編輯 | 編輯原始碼]

正如我們已經說過的那樣，不可變陣列 (IArray) 上的更新操作只是建立陣列的新副本，這非常低效，但它是一個可以在純函式中使用的純操作。 另一方面，可變陣列 (MArray) 上的更新很有效，但只能在單子程式碼中完成。 DiffArray（在 Data.Array.Diff 中定義）結合了兩個世界的優點 - 它支援 IArray 介面，因此可以在純函式式方式中使用，但它在內部使用 MArrays 的高效更新。

這個技巧是如何運作的？ DiffArray 具有純外部介面，但在內部它表示為對 IOArray 的引用。

當 '//' 運算子應用於差異陣列時，其內容會以適當位置的方式物理更新。 舊陣列會悄無聲息地改變其表示形式，而不會改變可見的行為：它將儲存一個指向新當前陣列的連結以及要應用的差異以獲得舊內容。

因此，如果差異陣列以單執行緒方式使用，即在 '//' 應用之後不再使用舊版本，那麼 a ! i 需要 O(1) 時間，a // d 需要 O(n) 時間。 訪問舊版本的元素會逐漸變慢。

更新一個不是當前版本的陣列會進行物理複製。 生成的陣列與舊的系列沒有連結。 因此，您可以透過執行“標識更新”old // [] 來獲得一個版本，該版本保證是當前版本，因此具有快速元素訪問速度。

該庫提供了兩種“微分”陣列建構函式 - DiffArray，在內部由 IOArray 構成，以及 DiffUArray，基於 IOUArray。 如果您確實需要，您可以從任何生活在 'IO' 單子中的 'MArray' 型別構建新的“微分”陣列型別。 有關更多詳細資訊，請參閱 模組文件。

DiffArray 的用法與 Array 的用法沒有區別，唯一的區別是記憶體消耗和速度

import Data.Array.Diff

main = do
       let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int
           a = arr ! 1
           arr2 = arr // [(1,37)]
           b = arr2 ! 1
       print (a,b)

您可以使用 'seq' 來強制在更新陣列之前評估陣列元素

import Data.Array.Diff

main = do
       let arr = listArray (1,1000) [1..1000] :: DiffArray Int Int
           a = arr ! 1
           b = arr ! 2
           arr2 = a `seq` b `seq` (arr // [(1,37),(2,64)])
           c = arr2 ! 1
       print (a,b,c)

非盒子陣列

[編輯 | 編輯原始碼]

在大多數惰性評估實現中，值在執行時表示為指向其值或用於計算其值的程式碼的指標。 這種額外的間接級別，以及執行時可能需要的任何額外標籤，被稱為盒子。 預設的“盒子”陣列包含許多這樣的盒子，每個盒子都可以單獨計算其值。 這允許許多巧妙的技巧，例如遞迴地根據彼此來定義陣列的元素，或者僅計算永遠需要的陣列的特定元素。 但是，對於大型陣列，它會在開銷方面花費很多，如果始終需要整個陣列，則可能是浪費。

無箱陣列（在 Data.Array.Unboxed 中定義）更像是 C 語言中的陣列 - 它們只包含純值，沒有額外的間接層，因此例如一個包含 1024 個 Int32 型別值的陣列只會使用 4 kb 的記憶體。此外，對這類陣列的索引速度可以顯著提高。

當然，無箱陣列也有自己的缺點。首先，無箱陣列只能由具有固定大小的純值組成 - Int、Word、Char、Bool、Ptr、Double 等（在 UArray 類定義 中列出）。你甚至可以自己為其他簡單型別（包括列舉型別）實現無箱陣列。但是 Integer、String 和任何其他使用可變大小定義的型別都不能成為無箱陣列的元素。其次，如果沒有額外的間接層，無箱陣列中的所有元素都必須在陣列被求值時求值，因此你將失去惰性求值的優勢。索引陣列以讀取單個元素將構建整個陣列。如果你最終需要整個陣列，這並不算什麼損失，但這確實阻止了用彼此遞迴定義陣列元素，並且如果只使用特定值，它可能會過於昂貴。儘管如此，無箱陣列是一個非常有用的最佳化工具，我建議儘可能地使用它們。

庫中的所有主要陣列型別都有無箱對應物

 Array - UArray          (module Data.Array.Unboxed)
 IOArray - IOUArray      (module Data.Array.IO)
 STArray - STUArray      (module Data.Array.ST)
 DiffArray - DiffUArray  (module Data.Array.Diff)

因此，基本上用無箱陣列替換程式中的箱陣列非常簡單 - 只需在型別簽名中新增 'U'，就完成了！當然，如果你將 Array 更改為 UArray，還需要在匯入列表中新增 "Data.Array.Unboxed"。

StorableArray

[edit | edit source]

可儲存陣列 (Data.Array.Storable) 是一個 IO 可變陣列，它將內容儲存在 C 堆中的連續記憶體塊中。元素根據 'Storable' 類儲存。你可以獲取指向陣列內容的指標，以便從 C 等語言中操作元素。

它類似於 'IOUArray'（特別是，它實現了相同的 MArray 介面），但速度更慢。優點是它透過外部函式介面與 C 相容。可儲存陣列的記憶體地址是固定的，因此你可以將它們傳遞給 C 例程。

指向陣列內容的指標由 'withStorableArray' 獲取。這個想法類似於 'ForeignPtr'（這裡內部使用）。該指標只應該在 'withStorableArray' 函式作為引數傳遞的函式返回的 'IO' 操作執行期間使用。

{-# OPTIONS_GHC -fglasgow-exts #-}
import Data.Array.Storable
import Foreign.Ptr
import Foreign.C.Types

main = do arr <- newArray (1,10) 37 :: IO (StorableArray Int Int)
          a <- readArray arr 1
          withStorableArray arr 
              (\ptr -> memset ptr 0 40)
          b <- readArray arr 1
          print (a,b)

foreign import ccall unsafe "string.h" 
    memset  :: Ptr a -> CInt -> CSize -> IO ()

如果你想之後使用這個指標，請確保在最後一次使用指標之後呼叫 'touchStorableArray'，這樣陣列就不會過早釋放。


其他說明：GHC 6.6 應該使訪問 'StorableArray' 的速度與訪問任何其他無箱陣列一樣快。'StorableArray' 和 'UArray' 之間的唯一區別是，UArray 位於 GHC 堆的可重定位部分，而 'StorableArray' 位於不可重定位部分，因此保持固定地址，這允許將該地址傳遞給 C 例程並在 C 資料結構中儲存它。

GHC 6.6 還添加了 'unsafeForeignPtrToStorableArray' 操作，該操作允許使用任何 Ptr 作為 'StorableArray' 的地址，特別是在處理 C 例程返回的陣列時。使用此操作的示例

import Data.Array.Storable
import Foreign.Marshal.Alloc
import Foreign.Marshal.Array
import Foreign.ForeignPtr

main = do ptr <- mallocArray 10
          fptr <- newForeignPtr_ ptr
          arr <- unsafeForeignPtrToStorableArray (1,10) fptr :: IO (StorableArray Int Int)
          writeArray arr 1 64
          a <- readArray arr 1
          print a
          free ptr

此示例為 10 個 Int 分配記憶體（模擬由某個 C 函式返回的陣列），然後將返回的 'Ptr Int' 轉換為 'ForeignPtr Int'，並將 'ForeignPtr Int' 轉換為 'StorableArray Int Int'。然後它寫入並讀取陣列的第一個元素。最後，透過 'free' 釋放陣列使用的記憶體，它再次模擬 C 例程的釋放。我們還可以透過將 "newForeignPtr_ ptr" 替換為 "newForeignPtr finalizerFree ptr" 來啟用自動釋放已分配的塊。在這種情況下，記憶體將在最後一次使用陣列後自動釋放，就像任何其他 Haskell 物件一樣。

Haskell 陣列預處理器 (STPP)

[edit | edit source]

在 Haskell 中使用可變陣列（IO 和 ST 陣列）並不是很方便。但有一個工具可以新增語法糖，使使用這種陣列非常接近於在命令式語言中的使用。它由 Hal Daume III 編寫，你可以將其作為 http://hal3.name/STPP/stpp.tar.gz 獲取。

使用此工具，你可以在任意複雜的表示式中索引陣列元素，只需使用 "arr[|i|]" 表示法，此預處理器將自動將這種語法形式轉換為對 'readArray' 和 'writeArray' 的適當呼叫。也支援多維陣列，索引形式為 "arr[|i|][|j|]”。請參閱 http://hal3.name/STPP/ 中的進一步說明。


ArrayRef 庫

[edit | edit source]

The ArrayRef 庫 重新實現了陣列庫，並具有以下擴充套件

  • 動態（可調整大小）陣列
  • 多型無箱陣列

它還添加了 語法糖，簡化了陣列使用。雖然不像 STPP 那樣優雅，但另一方面，它完全在 Haskell 語言內部實現，沒有任何預處理器。


不安全操作和遍歷陣列元素

[edit | edit source]

如上所述，存在將可變陣列和不可變陣列轉換為相同型別的操作，即 'freeze'（可變 → 不可變）和 'thaw'（不可變 → 可變）。這些操作會複製整個陣列。如果你確定可變陣列不會被修改，或者不可變陣列在轉換後不會被使用，那麼你可以使用 unsafeFreeze/unsafeThaw 代替 - 這些操作會就地轉換陣列，如果輸入和結果陣列具有相同的記憶體表示（即相同的型別和裝箱）。請注意，"unsafe*" 操作會修改記憶體 - 它們會在陣列頭中設定/清除標誌，以指示陣列的可變性。因此，這些操作不能與多執行緒訪問陣列一起使用（使用執行緒或某種形式的協程）。

還存在將無箱陣列轉換為其他元素型別的操作，即 castIOUArray 和 castSTUArray。這些操作依賴於記憶體中實際的型別表示，因此沒有關於其結果的任何保證。特別是，這些操作可以用於將任何可無箱化的值轉換為位元組序列，反之亦然，例如，它在 AltBinary 庫中用於序列化浮點數。請注意，這些操作不會根據元素大小的更改重新計算陣列邊界。你應該使用 'sizeOf' 操作自己執行此操作！

雖然陣列可以具有任何型別的索引，但在內部，任何在邊界檢查之後的索引都會被轉換為普通的 Int 值（位置），然後使用低階操作之一，即 unsafeAt、unsafeRead、unsafeWrite。你可以在自己需要跳過邊界檢查並使程式更快的情況下，自己使用這些操作。這些操作在需要遍歷整個陣列時特別有用

-- | Returns a list of all the elements of an array, in the same order
-- as their indices.
elems arr = [ unsafeAt arr i | i <- [0 .. rangeSize (bounds arr)-1] ]

在這樣的迴圈中使用 "unsafe*" 操作實際上是安全的，因為 'i' 只遍歷現有陣列元素的位置。

GHC 特定主題

[edit | edit source]

並行陣列（模組 GHC.PArr）

[edit | edit source]

正如我們已經提到的，陣列庫支援兩種陣列變體 - 惰性箱陣列和嚴格無箱陣列。並行陣列實現了一些介於兩者之間的東西 - 它是一個嚴格的箱不可變陣列。這保留了使用任何資料型別作為陣列元素的靈活性，同時使建立和訪問這類陣列的速度更快。陣列建立實現為一個命令式迴圈，它填充所有陣列元素，而訪問陣列元素不需要檢查“箱”。應該很明顯，在陣列元素的計算相當複雜，並且不會使用大部分陣列元素的情況下，並行陣列效率不高。實際使用的另一個缺點是，並行陣列不支援 IArray 介面，這意味著你無法編寫同時適用於 Array 和並行陣列建構函式的通用演算法。

像許多 GHC 擴充套件一樣，這在論文中進行了描述：Haskell 中快速陣列的一種方法，作者是 Manuel M. T. Chakravarty 和 Gabriele Keller。

你也可以檢視 GHC.PArr 模組的原始碼，其中包含許多註釋。

並行陣列的特殊語法由 "ghc -fparr" 或 "ghci -fparr" 啟用，這在 GHC 6.4.1 的使用者手冊中沒有記錄。


歡迎來到機器

[edit | edit source]

Array#、MutableArray#、ByteArray#、MutableByteArray#、固定和可移動位元組陣列

GHC 堆包含兩種型別的物件 - 一些只是位元組序列，另一些包含指向其他物件的指標（稱為“箱”）。這種隔離允許在執行垃圾回收時找到引用鏈，並在壓縮堆使用的記憶體時更新這些指標，並將物件移動到新位置。內部 (raw) GHC 的型別 Array# 表示一個物件指標序列（箱）。在 ST 單元中有一個低階操作，它在堆中分配指定大小的陣列，它的型別類似於 (Int -> ST s Array#) 。Array# 型別在 Array 型別中使用，Array 型別表示箱不可變陣列。

對於可變箱陣列（IOArray/STArray），存在一種不同的型別，即 MutableArray#。可變陣列的單獨型別是由於兩階段垃圾回收機制。Array# 和 MutableArray# 的內部表示相同，除了頭部中的一些標誌，這使得可以就地轉換 MutableArray# 為 Array#，反之亦然（這就是 unsafeFreeze 和 unsafeThaw 操作所做的）。

未裝箱陣列由 ByteArray# 型別表示。它只是一個堆上的普通記憶體區域，就像 C 語言的陣列一樣。有兩個基本操作可以建立指定大小的 ByteArray# - 一個在普通堆上分配記憶體，因此這個位元組陣列每次發生垃圾回收時都會被移動。這會阻止將 ByteArray# 轉換為可以在 C 程式中使用的普通記憶體指標（儘管仍然可以將當前 ByteArray# 指標傳遞給“不安全外部”程式，如果它不嘗試將該指標儲存在任何地方）。第二個基本操作在“固定”堆區域分配指定大小的 ByteArray#，該區域包含固定位置的物件。這種位元組陣列永遠不會被 GC 移動，因此它的地址可以用作普通 Ptr 並與 C 世界共享。建立 ByteArray# 的第一種方式用於所有 UArray 型別的實現內部，第二種方式用於 StorableArray（儘管 StorableArray 也可以指向由 C malloc 分配的資料）。

還有 MutableByteArray# 型別，它與 ByteArray# 幾乎沒有區別，但 GHC 的基本操作僅支援 MutableByteArray# 的單子讀/寫操作，僅支援 ByteArray# 的純讀取操作，以及用於更改這些陣列頭部的相應欄位的 unsafeFreeze/unsafeThaw 操作。這種差異除了額外的安全檢查外沒有太大意義。

所以，固定的 MutableByteArray# 或 StorableArray 內部使用的 C malloc 的記憶體，I OUArray 和 STUArray 內部使用的未固定的 MutableByteArray#，以及 UArray 內部使用的未固定的 ByteArray#。

裝箱和未裝箱陣列的 API 幾乎相同

 marr <- alloc n            - allocates mutable array with given size
 arr  <- unsafeFreeze marr  - converts mutable array to immutable one
 marr <- unsafeThaw arr     - converts immutable array to mutable one
 x    <- unsafeRead marr i  - monadic reading of value with given index from mutable array
 unsafeWrite marr i x       - monadic writing of value with given index from mutable array
 let x = unsafeAt arr i     - pure reading of value with given index from immutable array
 (all indexes are counted from 0)

基於這些基本操作，陣列庫實現了對任何型別和任何下界的索引，邊界檢查以及所有其他高階操作。建立/更新不可變陣列的操作只是在 ST 單子中將它們建立為可變陣列，對該陣列進行所有必需的更新，然後在從 runST 返回陣列之前使用 unsafeFreeze。IO 陣列上的操作是透過使用 stToIO 操作對 ST 陣列上的操作實現的。

可變陣列和 GC

[edit | edit source]

GHC 實現了一個兩階段的 GC，它非常快 - 小 GC 在每分配 256 kb 後發生，並且在搜尋“活動”資料時只掃描該區域（以及最近的堆疊幀）。這個解決方案利用了普通 Haskell 資料是不可變的事實，因此在上次小 GC 之前建立的任何資料結構都不能指向該 GC 之後建立的資料結構（由於不可變性，資料只能包含“向後”引用）。

但是，當我們在語言中新增可變裝箱引用 (IORef/STRef) 和陣列 (IOArray/STArray) 時，這種簡單性就會被打破。在每次 GC（包括小 GC）上，可變資料結構中的每個元素都應該被掃描，因為它們可能自上次 GC 以來被更新，現在指向上次 GC 以來分配的資料。

對於包含大量可變裝箱陣列/引用資料的程式，GC 時間可能會很容易地超過有用的計算時間。具有諷刺意味的是，其中一個這樣的程式是 GHC 本身。解決此類程式的方案是在命令列選項中新增類似 "+RTS -A10m" 的選項，該選項將小 GC 塊的大小從 256 kb 增加到 10 mb，即使小 GC 的頻率降低 40 倍。您可以使用 "+RTS -sstderr" 選項看到此更改的效果 - "%GC 時間" 應該顯著下降。

有一種方法可以將此選項包含到您的可執行檔案中，這樣它將在每次執行時自動使用 - 您只需將包含以下行的 C 原始檔新增到您的專案中

char *ghc_rts_opts = "-A10m";

當然，您可以根據需要增加或減少此值。

增加 "-A" 值並非沒有代價 - 除了顯而易見的記憶體使用量增加外，執行時間（有效程式碼的執行時間）也會增加。預設的 "-A" 值經過調整，使其接近現代 CPU 快取的大小，這意味著大多數記憶體引用都落在快取內。當在進行 GC 之前分配了 10 mb 的記憶體時，這種資料區域性性就不再成立了。因此，增加 "-A" 可能會增加或減少程式速度，具體取決於程式的性質。嘗試在執行程式時使用“典型”引數嘗試 64 kb 到 16 mb 之間的各種設定，並嘗試為您的具體程式和 CPU 組合選擇最佳設定。

還有一種方法可以避免增加 GC 時間 - 使用未裝箱或不可變陣列。還要注意，不可變陣列是作為可變陣列構建的，然後被“凍結”，因此在構建期間 GC 也會掃描它們的內容。

希望 GHC 6.6 修復了這個問題 - 它會記住自上次 GC 以來哪些引用/陣列被更新，並只掃描它們。只有在使用非常大的陣列時才會遇到舊問題。

更多資訊


檢索自 "https://wikibook.tw/w/index.php?title=Haskell/Libraries/Arrays&oldid=3676129"
華夏公益教科書