İşlevsel bir dilde denklik sınıfları ve sendika/bulma

Question

Bir otomata algoritması için işlevsel bir dilde hızlı bir Union-Find veri yapısına ihtiyacım var. Veri yapısının doğruluğunu resmi olarak kanıtlamak gerektiğinden, basit bir yapıyı tercih ederim.

Yapmaya çalıştığım şey, bir S w.r.t. setindeki öğelerin denklik sınıflarını hesaplamaktır. bir ilişki R ⊆ S × S. Sonunda çıkmak istediğim, S öğesinin herhangi bir elemanını R-eşitlik sınıfının bir (kanonik) temsilcisine eşleyen bazı f: S → S işlevidir. "Kanonik", demek istediğim, hangi temsilcisinin, bir denklik sınıfının tüm öğeleri için aynı olduğu sürece, yani, f x = f y ⟺ (x,y) ∈ R'un beklemesini istiyorum.

Bunun için en iyi veri yapısı ve algoritması işlevsel bir dilde ne olurdu? Gerçekten "normal" fonksiyonel kodlara, yani hiçbir mutabilite/durum trafo monadına ihtiyacım olduğunu eklemeliyim.

DÜZENLEME: Bu temsilcisi ilk olan denklik sınıfının temsilci için S herhangi bir unsur eşleştiren bir harita oluşturur

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] 

: Bu arada, bu algoritma ile geldi S üzerinden yineleme ile ulaşılan öğe. Sanırım bu aslında doğrusal zamana sahip (harita operasyonları sabitse). Yine de, diğer çözümlerle hala ilgileniyorum çünkü pratikte bunun ne kadar verimli olduğunu bilmiyorum.

(benim ilişkisi içten bir "S → (S Seti) seçeneğinde", üzerinde dolayısıyla yineleme olarak temsil edilir. {T | (s, t) ∈ R} - Bu o yapı üzerinde ucuz bir operasyondur)

Answer 1

AFAIK (ve hızlı bir arama beni reddetmedi), karşılaştırılabilir asimptotik performansa sahip (amortize ters-Ackermann fonksiyonu) geleneksel disjoint-set datastructure bilinen tamamen işlevsel bir eşdeğeri yoktur. (geleneksel veri yapısı tamamen işlevsel değildir, çünkü yol sıkıştırması gerçekleştirmek için yıkıcı bir güncelleme gerektirir)

İşlevsel saflıkta ölü olarak ayarlanmadıysanız, yıkıcı güncelleştirmeyi kullanabilir ve geleneksel veri yapısını uygulayabilirsiniz.

Asimptotik performansı eşleştirmekle ilgilenmiyorsanız, geleneksel veri yapısının rasgele erişim dizisini persistent associative map ile değiştirebilir, ek bir O (log N) performans faktörü pahasına ve bunun doğrulanması gerekir. doğruluğu.

Doğrulama amacıyla maksimum basitlik istiyorsanız ve yukarıdakilerden herhangi birinde ölü olarak ayarlanmadıysanız, güncelleştirilebilir bir dizi ve sendika sıralaması optimizasyonunu kullanabilirsiniz. IIRC, bu, O (log N) amortize edilmiş en kötü durum performansını verir, ancak pratik yürütme hızını artırabilir (sıralamanın artık saklanması veya yönetilmesi gerekmediği için).