Clojure fermuar uygulaması neden Huet fermuarından farklı tip ve veri yapıları kullanıyor?

Question

Huet's original paper'u Clojure's implementation ile karşılaştırıyorum ve değişikliklerin neden yapıldığını anlamaya çalışıyorum. Ben bir Clojure acemiim, bu yüzden Clojure kodunun yorumlanmasında yanılıyorsam lütfen beni düzeltin. Huet en yazıda

, bir yolun tip Top | Node of tree list * path * tree list;; (ocaml gösterilmiştir). Clojure'da iki ek alan vardır, pnodes ve changed?. Bu alanların amacı nedir? l ve r'un Huet türündeki ilk ve üçüncü girişlere karşılık geldiğine ve ppath'un ikinci olduğuna inanıyorum?

Huet'in fermuarı, bağlı listelerin tamamını kullanır (örneğin Loc'in kendisi, fermuarın çalıştığı veri yapısı hakkında konuşmamaya dikkat edin), bazı yerlerde, örneğin l, Clojure uygulaması vektörleri kullanır. Neden değişim ve Clojure uygulamasının zaman karmaşıklığı için anlamı nedir?

Answer 1

İlk olarak, l, r ve ppath anlayışınız doğrudur.

pnodes ve bir optimizasyon olarak birlikte changed? eser: Eğer changed? yanlıştır up eğer gittiğinizde o zaman geçerli düğüm ve sol ve sağ kardeşler listelerinden yeniden inşa ziyade pnodes gelen düğümü pop.

l için bir vektörün kullanımı ve r için bir liste. Yine, bir düğümün yeniden inşa edilmesi maliyeti ile ilgilidir. Huet'in kağıdında, 0 (sol) boyutunun olduğu, O (nleft) olan (rev left) @ (t::right) var. Clojure biz O'dur (concat l (cons node r)) sahip (1) [1] l bir vektör tersine gerek yoktur olmak (Clojure vektörler etkin bir şekilde, herhangi bir yönde geçtiği ancak sağ appendable girmektedir) için.

[1] ok sadece oluşturma sırasında O (1) açıklanmıştır: Elde edilen dizi, diğer hesaplamalar tarafından tüketilen olarak nleft conses lazily tahsis edilecektir.