haskell中的immutable array是如何實現隨機訪問的？

01-14

btw，為什麼函數式編程中很少見「原生」的隨機訪問？

In data structures, direct access implies the ability to access any entry in a list in constant (independent of its position in the list and of list"s size, i.e. O(1) time. Very few data structures can guarantee this, other than arrays (and related structures like dynamic arrays)

via Random access

如果要immutable又要random access的話就是一塊長度固定的不可變連續內存, 咦, 聽上去貌似已經有這個, 好像叫tuple? 但是Haskell的類型系統不太方便做這事

(!) :: (a) -&> Ix -&> a (!) :: (a,a) -&> Ix -&> a (!) :: (a,a,a) -&> Ix -&> a (!) :: (a,a,a,a) -&> Ix -&> a -- tuple不茲磁這個介面其實 ( -- 忽略上面那個, 數組可以是任意長的啊大哥(別跟我說用Template Haskell干這種挫事)

然後就有這個Data.Array.IArray

但老實說一個只能訪問的數組並沒有什麼卯月!

當時學FP的時候其中一個突破以前的認識就是: "數組"只是index對元素的映射, 提供訪問元素的介面, 至於訪問的複雜度是多少是一回事, 數組在內存裡面的布局也是另外一回事(我也是C語言學過來的人, 數組是連續的內存這種想法植根在腦里), 還有個就是Map也是一個函數, 這樣我對函數和數據結構之間的關係產生微妙變化(遞歸跟棧的關係, 後面看continuation跟zipper的關係又有這種趕腳, 這跑題了)

想開了之後就可以看各種實現了

Data.Sequence 用的Finger trees, 當年被chaoxu大神安利過

你認為最優美的數據結構是什麼，說出你的理由？ - Chao Xu 的回答

還有這個做了神奇優化的 vector: Efficient Arrays

Clojure那個受Ideal Hash Trees影響搞出來的

polymatheia - Understanding Clojure"s Persistent Vector, pt. 1

Implementing Persistent Vectors in Scala

ICFP 2015的paper, 新鮮滾熱辣, 其實前面已經有篇RRB-Trees: Efficient Immutable Vectors

RRB vector: a practical general purpose immutable sequence

隨機訪問O(1)的數組是有的，底層就是C數組，但是為了隔離副作用，要把你鎖在PrimMonad（IO或者ST s）里；不想要鎖在monad里，想要immutable的話，那就是各種樹結構了。

一般而言，需要將大量使用數組的隨機讀寫的演算法用Haskell實現時，正確的姿勢是，把數據存放到ST monad中的數組，然後用純imperative的做法進行讀寫，最後用runST把整個演算法封裝成純的界面。這樣暴露出來的函數簽名仍然是純的，而底層依然進行高效的隨機讀寫，效率不輸C數組。

另外，OCaml的數組也可以O(1)隨機訪問，而且不會強制要求卡在一個monad裡面，而是可以在純的代碼里隨便讀寫。數組的本質其實就是引用，在函數式語言中不加限制地使用引用類型會破壞引用透明性（同樣的函數調用給出同樣的結果），不過OCaml社區並不追求引用透明，也沒有用類型系統隔離副作用的習慣。

已經有答案給出Haskell常用的幾個庫，但如果追求極致性能的話，C數組依舊是最好的選擇。vector庫中的mutable vector，其實就是包裝好的c數組。它內部通過黑魔法轉化成immutable vector。以下source摘自：https://hackage.haskell.org/package/vector-0.11.0.0/docs/src/Data-Vector-Storable-Mutable.html#MVector

-- | Mutable "Storable"-based vectors data MVector s a = MVector {-# UNPACK #-} !Int {-# UNPACK #-} !(ForeignPtr a) deriving ( Typeable )

instance Storable a =&> G.Vector Vector a where {-# INLINE basicUnsafeFreeze #-} basicUnsafeFreeze (MVector n fp) = return $ Vector n fp

黑魔法怎麼用的，可以看Part I: Deamortized ST

摘其中一段名言：

As long as nobody knows that you cheated and nobody can observe that you did, and no matter how many times they try to catch you you get away with it, does it matter that you cheated? I will definitely not be trying this line of reasoning with my wife, but types are more forgiving.
Edward Kmett