Mảng thưa thớt trong Haskell?

Question

Có cách nào tiêu chuẩn hoặc "thông thường nhất" để biểu diễn các mảng thưa thớt đa chiều trong Haskell (mà không làm mất hiệu suất quá nhiều) không?

Ví dụ: bản đồ < int, bản đồ < int, MyClass>> trong C++ chẳng hạn. Tôi đã google và tìm thấy chỉ là một số giấy tờ học thuật cũ và những người khác yêu cầu này quá.

Cảm ơn!

Answer 1

Data.Map (Int,Int) MyClass là một đề xuất tuyệt vời; hãy thử điều đó trước.

Nếu bạn gặp sự cố về không gian, hãy thử IntMap (IntMap MyClass). IntMap s (trong mô-đun Data.IntMap) là Map s với Int s làm khóa; chuyên môn hóa chúng hiệu quả hơn bản đồ chung. Nó có thể hoặc có thể không tạo ra một sự khác biệt đáng kể.

Ngoài ra còn có dự án Scalable, adaptive persistent container types có thể được sử dụng cho bạn. Những thùng chứa (bao gồm cả bản đồ) sử dụng không gian ít hơn đáng kể so với bản đồ bình thường nhưng chúng hơi phức tạp hơn một chút (mặc dù vẫn còn dễ sử dụng hợp lý).

Answer 2

Không có gì tôi có thể thấy rằng hoàn toàn miễn phí, nhưng có này:

Sparse matrix representations in a functional language

và điều này:

A study of sparse matrix representations for solving linear systems in a functional language

Answer 3

Làm thế nào về một Data.Map (Int,Int) MyClass?

Answer 4

Có HsJudy, có vẻ như được thiết kế riêng cho bộ khóa thưa thớt.

Ràng buộc Judy (thư viện C triển khai mảng động thưa thớt nhanh) cho các API trình bày Haskell phù hợp nhất có thể với các giao diện thư viện Haskell tồn tại, như Data.Map và Data.Array.MArray. Ràng buộc này cho thư viện Judy bao gồm tất cả bốn kiểu: ánh xạ từ từ thành bit (Judy1), từ từ thành giá trị (JudyL), từ chuỗi thành giá trị (JudyHS) và từ mảng-of-byte tới giá trị (JudyHS).

Nhưng tôi có thể đi với Data.Map.Map (Int, Int) MyClass cho đến khi gặp sự cố về khả năng mở rộng hoặc khả năng sử dụng.

Answer 5

tôi thấy this short gist cho thấy một Row lưu trữ nén cho Haskell và nhân Matrix-vector liên quan:

import Data.Vector.Unboxed as U 

-- | A compressed row storage (CRS) sparse matrix. 
data CRS a = CRS { 
     crsValues :: Vector a 
    , colIndices :: Vector Int 
    , rowIndices :: Vector Int 
    } deriving (Show) 

multiplyMV :: CRS Double -> Vector Double -> Vector Double 
multiplyMV CRS{..} x = generate (U.length x) outer 
    where outer i = U.sum . U.map inner $ U.enumFromN start (end-start) 
      where inner j = (crsValues ! j) * (x ! (colIndices ! j)) 
       start = rowIndices ! i 
       end  = rowIndices ! (i+1) 
       (!) a b = unsafeIndex a b