Cách tiếp cận thành ngữ nhất đối với các bộ sưu tập đa chỉ mục trong Haskell là gì?

Question

Trong C++ và các ngôn ngữ khác, thư viện bổ sung triển khai vùng chứa nhiều chỉ mục, ví dụ: Boost.Multiindex. Đó là, một bộ sưu tập lưu trữ một loại giá trị nhưng duy trì nhiều chỉ mục khác nhau trên các giá trị đó. Các chỉ số này cung cấp các phương thức truy cập và hành vi sắp xếp khác nhau, ví dụ: map, multimap, set, multiset, array, vv Thời gian chạy phức tạp của container đa chỉ mục thường là tổng của các phức tạp của các chỉ số riêng lẻ.

Có tương đương với Haskell hoặc những người sáng tác riêng của họ không? Cụ thể, cách thành ngữ nhất để thực hiện một bộ sưu tập kiểu T với cả hai loại chỉ số là gì (T là một thể hiện của Ord) cũng như một loại bản đồ chỉ mục (giả sử rằng một giá trị khóa của loại K có thể được cung cấp cho mỗi T, hoặc rõ ràng hoặc thông qua một hàm T -> K)?

Answer 1

Trong trường hợp tầm thường, mọi thành phần đều có khóa duy nhất luôn có sẵn, bạn chỉ có thể sử dụng Map và trích xuất khóa để tìm kiếm phần tử. Trong trường hợp nhỏ hơn một chút, mỗi giá trị chỉ đơn thuần là có một khóa khả dụng, một giải pháp đơn giản, nó sẽ là một cái gì đó như Map K (Set T). Tìm kiếm một phần tử trực tiếp sau đó sẽ liên quan đến việc giải nén khóa đầu tiên, lập chỉ mục Map để tìm tập hợp các phần tử chia sẻ khóa đó, sau đó tìm kiếm phần tử bạn muốn.

Đối với hầu hết các phần, nếu một cái gì đó có thể được thực hiện đơn giản trong thời trang trên (chuyển đổi đơn giản và làm tổ), nó có thể làm cho tinh thần để làm điều đó theo cách đó. Tuy nhiên, không cái nào trong số này tổng quát tốt, ví dụ: nhiều khóa hoặc khóa độc lập có thể không có sẵn, vì những lý do hiển nhiên.

Ngoài ra, tôi không biết bất kỳ triển khai chuẩn nào được sử dụng rộng rãi. Một số ví dụ tồn tại, ví dụ: IxSet from happstack dường như gần như phù hợp với hóa đơn. Tôi nghi ngờ các giải pháp một kích thước phù hợp nhất ở đây có trách nhiệm có tỷ lệ lợi ích/độ phức tạp thấp, vì vậy mọi người có xu hướng chỉ cần cuộn riêng cho phù hợp với nhu cầu cụ thể.

Bằng trực giác, điều này có vẻ như là một vấn đề có thể hoạt động tốt hơn không chỉ là triển khai đơn lẻ, mà là tập hợp các nguyên thủy có thể được cấu thành linh hoạt hơn Data.Map cho phép tạo cấu trúc đặc biệt. Nhưng điều đó không thực sự hữu ích cho các nhu cầu ngắn hạn.

Answer 2

Tôi tin rằng cách đơn giản nhất để thực hiện việc này đơn giản chỉ bằng Data.Map. Mặc dù nó được thiết kế để sử dụng các chỉ mục duy nhất, khi bạn chèn cùng một phần tử nhiều lần, hầu hết các trình biên dịch (chắc chắn GHC) sẽ làm cho các giá trị đặt vào cùng một vị trí. Việc triển khai multimap riêng biệt sẽ không hiệu quả, vì bạn muốn tìm các phần tử dựa trên chỉ mục của chúng, vì vậy bạn không thể liên kết một cách ngây thơ từng phần tử với nhiều chỉ mục - giả sử [([key], value)] - vì điều này sẽ rất không hiệu quả.

Tuy nhiên, tôi chưa xem xét triển khai Boost của Multimaps để xem, dứt khoát, nếu có cách tối ưu để làm như vậy.

Answer 3

Đối với câu hỏi cụ thể này, bạn có thể sử dụng Bimap. Nói chung, mặc dù, tôi không nhận thức được bất kỳ lớp phổ biến cho multimaps hoặc các thùng chứa được lập chỉ mục nhân.

Answer 4

Tôi có gặp sự cố trực tiếp không? Cả T và K đều có lệnh. Có phím chức năng :: T -> K nhưng không phải là để bảo quản đơn hàng. Nó là mong muốn để quản lý một bộ sưu tập của Ts, lập chỉ mục (để truy cập nhanh) cả hai theo thứ tự T và thứ tự K. Nói chung, người ta có thể muốn một tập hợp các phần tử T được lập chỉ mục bởi một loạt các đơn đặt hàng key1 :: T -> K1, .. keyn :: T -> Kn, và nó xảy ra ở đây key1 = id. Đó có phải là hình ảnh không?

Tôi nghĩ rằng tôi đồng ý với đề xuất của gereeter rằng cơ sở cho giải pháp chỉ là để đồng bộ hóa một loạt (Map K1 T, .. Map Kn T). Chèn một cặp khóa-giá trị trong bản đồ sẽ không trùng lặp cả khóa lẫn giá trị, chỉ phân bổ phần thừa bổ sung cần thiết để tạo một mục mới ở đúng vị trí trong chỉ mục. Chèn cùng một giá trị, được khóa hợp lý, trong nhiều chỉ mục không được chia nhỏ (ngay cả khi một trong các khóa là giá trị). Nó là giá trị gói cấu trúc trong một API đảm bảo rằng bất kỳ sửa đổi tiếp theo cho các giá trị được tính một lần và chia sẻ, chứ không phải là recomputed cho mỗi mục trong một chỉ mục.

Điểm mấu chốt: có thể duy trì nhiều bản đồ, đảm bảo rằng các giá trị được chia sẻ, mặc dù các đơn đặt hàng khóa là riêng biệt.

Answer 5

Tôi chỉ tải lên IxSet để hackage sáng nay,

http://hackage.haskell.org/package/ixset

ixset cung cấp bộ mà có nhiều chỉ số.

ixset đã được sử dụng trong một thời gian dài như happstack-ixset. Phiên bản này loại bỏ các phụ thuộc vào bất cứ điều gì happstack cụ thể, và là phiên bản chính thức mới của IxSet.

Một lựa chọn khác sẽ là kdtree:

darcs được http://darcs.monoid.at/kdtree

kdtree nhằm cải thiện trên IxSet bằng cách cung cấp loại an toàn hơn và thời gian tốt hơn và sử dụng không gian. Phiên bản hiện tại dường như làm tốt trên cả ba khía cạnh đó - nhưng nó vẫn chưa sẵn sàng cho thời gian đầu. Những người đóng góp bổ sung sẽ rất được hoan nghênh.