Các lớp tương đương và liên kết/tìm bằng ngôn ngữ chức năng

Question

Đối với thuật toán tự động, tôi yêu cầu cấu trúc dữ liệu Union-Find nhanh chóng bằng ngôn ngữ chức năng. Vì tôi cần chính thức chứng minh tính chính xác của cấu trúc dữ liệu, tôi thích cấu trúc đơn giản hơn.

Điều tôi đang cố gắng làm là tính toán các lớp tương đương của các phần tử trong một tập hợp S w.r.t. một mối quan hệ R ⊆ S × S. Những gì tôi muốn nhận ra cuối cùng là một số chức năng f: S → S mà bản đồ bất kỳ yếu tố của S đến một (canonical) đại diện của lớp học R-tương đương của nó. Theo "kinh điển", tôi có nghĩa là tôi không quan tâm người đại diện nào miễn là nó giống nhau cho tất cả các yếu tố của một lớp tương đương, tức là tôi muốn giữ f x = f y ⟺ (x,y) ∈ R.

Cấu trúc và thuật toán dữ liệu tốt nhất cho điều này bằng ngôn ngữ chức năng là gì? Tôi nên thêm rằng tôi thực sự cần mã chức năng "bình thường", tức là không có biến thể trạng thái biến đổi/trạng thái.

EDIT: Trong lúc này, tôi đã đưa ra thuật toán này:

m := empty map 
for each s ∈ S do 
    if m s = None then 
    for each t in {t | (s,t) ∈ R} 
     m := m[t ↦ s] 

này tạo ra một bản đồ mà các bản đồ bất kỳ yếu tố S để người đại diện của lớp tương đương của nó, nơi mà người đại diện là người đầu tiên phần tử đạt được bằng phép lặp qua S. Tôi nghĩ rằng điều này thực sự có thời gian tuyến tính (nếu hoạt động bản đồ là hằng số). Tuy nhiên, tôi vẫn còn quan tâm đến các giải pháp khác, vì tôi không biết làm thế nào hiệu quả này là trong thực tế.

(quan hệ của tôi được biểu thị nội bộ dưới dạng tùy chọn "S → (S Set)", do đó lặp lại trên {t | (s, t) ∈ R} - đây là hoạt động rẻ trên cấu trúc đó.)

Answer 1

AFAIK (và tìm kiếm nhanh không giải thích cho tôi), không có tương đương hoàn toàn chức năng thuần túy của thông số disjoint-set datastructure có hiệu suất tiệm cận tương đương (tính năng nghịch đảo-Ackermann). (cơ sở hạ tầng thông thường không hoàn toàn chức năng vì nó yêu cầu cập nhật phá hủy để thực hiện nén đường dẫn)

Nếu bạn không chết trên độ tinh khiết chức năng, bạn chỉ có thể sử dụng cập nhật phá hủy và triển khai cơ sở hạ tầng thông thường.

Nếu bạn không quan tâm đến hiệu suất tiệm cận, bạn có thể thay thế mảng truy cập ngẫu nhiên của cơ sở hạ tầng thông thường bằng persistent associative map, với chi phí của hệ số hiệu suất O (log N) bổ sung và cần xác minh đúng đắn.

Nếu bạn muốn đơn giản hóa tối đa cho mục đích xác minh và không được đặt ở cả hai bên trên, bạn có thể sử dụng mảng cập nhật và để giảm tối ưu hóa theo từng hạng. IIRC này mang lại hiệu suất trường hợp xấu nhất O (log N), nhưng thực sự có thể cải thiện tốc độ thực thi thực tế (vì thứ hạng không còn cần được lưu trữ hoặc quản lý nữa).