Dlaczego implementacja zamka Clojure wykorzystuje różne typy i struktury danych ze suwaka Huet?

Question

Porównuję Huet's original paper z Clojure's implementation i próbuję dowiedzieć się, dlaczego zmiany zostały wprowadzone. Jestem nowicjuszem Clojure, więc jeśli się mylę w mojej interpretacji kodu Clojure, popraw mnie.

W artykule Hueta typ ścieżki to (w Ocaml) Top | Node of tree list * path * tree list;;. W Clojure dostępne są dwa dodatkowe pola: pnodes i changed?. Jaki jest cel tych pól? Czy mam rację, sądząc, że l i r odpowiadają pierwszym i trzecim wpisom w typie Hueta, oraz że ppath jest drugim?

Zamek błyskawiczny Huet wykorzystuje połączone listy (uwaga mówię o samym typie Loc, a nie o strukturze danych, z którą działa zamek), podczas gdy w niektórych miejscach, na przykład l, implementacja Clojure wykorzystuje wektory. Skąd ta zmiana i jaka jest jej konsekwencja dla złożoności czasowej wdrożenia Clojure?

Answer 1

Po pierwsze, zrozumienie l, r i ppath jest poprawna.

pnodes i changed? pracują razem jako optymalizacja: gdy idziesz up jeśli changed? jest fałszywa wtedy pop węzeł z pnodes zamiast odbudowy go z bieżącego węzła i po lewej i po prawej list rodzeństwo.

Jeśli chodzi o użycie wektora dla l i listę dla r. Znowu chodzi o koszt odbudowy węzła. W artykule Hueta znajduje się (rev left) @ (t::right), który jest O (nleft), gdzie nleft ma rozmiar lewej. W Clojure mamy (concat l (cons node r)), który jest O (1) [1], ponieważ l jest wektorem nie musi być odwracany (wektory w Clojure mogą być efektywnie przemierzane w dowolnym kierunku, ale są dostępne tylko z prawej strony).

[1] ok jest to O (1) tylko w momencie tworzenia: nouft conses będą leniwie alokowane, ponieważ wynikowa sekwencja jest zużywana przez dalsze obliczenia.