Tôi đang cố triển khai thuật toán Dijkstra trong Haskell. Tôi đã thực hiện một đống nhị phân bằng cách sử dụng một cây. Trong thuật toán các phím lân cận của đỉnh hiện tại nên được cập nhật trong heap. Làm thế nào tôi có thể mô phỏng con trỏ để giá trị trong heap trong Haskell? Làm thế nào tôi có thể truy cập nhanh đến các phần tử trong heap, trong khi đống thay đổi sau mỗi thao tác?Làm cách nào để mô phỏng con trỏ trong Haskell?
Xem các gói Data.IORef và Data.STRef cho phép bạn truy cập vào các tham chiếu có thể thay đổi. Sử dụng IORefs nếu bạn cũng cần phải thực hiện IO, và STRefs nếu bạn không.
Tuy nhiên, sự nghi ngờ của tôi là có thể bạn đang làm sai. Hoàn toàn có thể thực hiện thuật toán của Dijkstra mà không có trạng thái có thể thay đổi (mặc dù bạn cần cẩn thận một chút, vì bạn có thể dễ dàng gây ra thời gian chạy tiệm cận nếu bạn liên tục đánh giá lại các chức năng có thể được lưu trữ).
Có thể bạn đang tìm kiếm Data.Vector.Mutable từ gói vector, mà bạn có thể muốn kết hợp với đơn vị ST hoặc IO.
Bạn có thể sử dụng Data.FingerTree.PSQueue hỗ trợ thao tác adjust để cập nhật heap. Trong trường hợp này, bạn không cần trỏ đến các giá trị trong heap vì bạn cập nhật chúng thông qua các khóa của chúng.
FWIW, có hàng đợi ưu tiên tuyệt vời về hackage và ghép nối heaps dễ thực hiện hơn so với đống nhị phân nhưng vẫn đóng gói khá một cú đấm. Đối với đột biến: Không. Có lẽ là một cách xung quanh nó, và mặc dù bộ nhớ có thể thay đổi tồn tại, sử dụng nó cực kỳ xấu xí để nhắc nhở bạn rằng bạn không nên làm điều đó;) – delnan
Bạn có thể sẽ nhận được câu trả lời tốt hơn nếu bạn hỏi làm thế nào để làm nhanh Dijkstra trong Haskell (mà dường như là vấn đề thực tế của bạn) thay vì một giải pháp có thể. – Pubby
@ElectricHedgehog, có rất nhiều hàng đợi ưu tiên tối ưu tiệm cận có thể được thực hiện chức năng, đáng chú ý nhất là hàng đợi nhị thức. Kiểm tra các gói như [pqueue] (http://hackage.haskell.org/package/pqueue). –