W Clojure, kiedy drzewa heterogenicznych typów węzłów powinny być reprezentowane za pomocą rekordów lub wektorów?

Question

Który jest lepszy idiomatyczne praktyka clojure do reprezentowania drzewo składa się z różnych typów węzłów:

A. budowlanych drzew z kilku różnych typów rekordów, które definiuje się za pomocą deftype lub defrecord:

(defrecord node_a [left right]) 
(defrecord node_b [left right]) 
(defrecord leaf []) 

(def my-tree (node_a. (node_b. (leaf.) (leaf.)) (leaf.))) 

B. budowlanych drzewa z wektorami, ze słowami kluczowymi wyznaczania tych typów:

(def my-tree [:node-a [:node-b :leaf :leaf] :leaf]) 

Większość kodu clojure że widzę wydaje się sprzyjać wykorzystanie struktur danych ogólnego zastosowania (wektory, mapy, itp), R niż dane lub rekordy. Czkawka, aby wziąć jeden przykład, przedstawia html bardzo ładnie za pomocą wektora + słowa kluczowego.

Kiedy powinniśmy preferować jeden styl w stosunku do drugiego?

Answer 1

Możesz umieścić dowolną liczbę elementów w wektorze, jak chcesz. Rekord ma ustawioną liczbę pól. Jeśli chcesz ograniczyć węzły do ​​N tylko pod-węzłów, rekordy mogą być dobre, np. co przy binarnym drzewie, w którym węzeł musi mieć tylko lewe i prawe. Ale dla czegoś takiego jak HTML lub XML, prawdopodobnie chcesz obsługiwać dowolne liczby pod-węzłów.

Używanie wektorów i słów kluczowych oznacza, że ​​"rozszerzanie" zestawu obsługiwanych typów węzłów jest tak proste, jak wstawianie nowego słowa kluczowego do wektora. [:frob "foo"] jest OK w czkawka, nawet jeśli jego autor nigdy nie słyszał o frobbingu. Używając rekordów, potencjalnie musisz zdefiniować nowy rekord dla każdego typu węzła. Ale wtedy uzyskujesz korzyści z łapania literówek i weryfikowania podwęzłów. [:strnog "some bold text?"] nie zostanie przechwycony przez Hiccup, ale (Strnog. "foo") będzie błędem podczas kompilacji.

Wektory będące jednym z podstawowych typów danych Clojure, można użyć wbudowanych funkcji Clojure do manipulowania nimi. Chcesz przedłużyć swoje drzewo? Po prostu conj na to, lub update-in lub cokolwiek innego. W ten sposób możesz budować drzewo przyrostowo. W przypadku rekordów prawdopodobnie utknąłeś w wywołaniach konstruktorów, albo musisz napisać mnóstwo funkcji otoki dla konstruktorów.

Wygląda na to, że częściowo sprowadza się do argumentu dynamicznego vs. statycznego. Osobiście podążałbym drogą dynamiczną (wektor + słowo kluczowe), chyba że istniała szczególna potrzeba korzystania z rekordów. Prawdopodobnie łatwiej jest kodować w ten sposób i jest on bardziej elastyczny dla użytkownika, kosztem bycia łatwiejszym dla użytkownika, który w końcu robi bałagan. Jednak użytkownicy Clojure są zwykle przyzwyczajeni do radzenia sobie z niebezpieczną bronią w regularnych odstępach czasu. Clojure jest w dużej mierze dynamicznym językiem, a pozostawanie dynamicznym często jest słuszne.

Answer 2

To jest dobre pytanie. Myślę, że oba są odpowiednie dla różnych rodzajów problemów. Zagnieżdżone wektory są dobrym rozwiązaniem, jeśli każdy węzeł może zawierać zmienny zestaw informacji - w szczególności systemy szablonowe będą działać dobrze. Rekordy są dobrym rozwiązaniem dla małej liczby stałych typów węzłów, w których zagnieżdżanie jest znacznie bardziej ograniczone.

Wykonujemy wiele pracy z heterogenicznymi drzewami rekordów. Każdy węzeł reprezentuje jedną z kilku dobrze znanych typów, z których każda ma inny zestaw znanych kluczy stałych. Rekordy powodu są lepsze w tym przypadku, że można wybrać dane z węzła za pomocą klucza, którym jest O (1) (naprawdę wywołanie metody Java, które jest bardzo szybkie), a nie O (n) (gdzie trzeba szukać poprzez zawartość węzła), a także ogólnie łatwiejszy dostęp.

Nagrania w wersji 1.2 są niezupełnie "skończone", ale samemu łatwo je zbudować.Mamy defrecord2, który dodaje funkcje konstruktora (new-foo), sprawdzanie poprawności pól, wsparcie drukowania, obsługę Pprint, obsługę przechodzenia/edycji drzewa przez suwaki, itp.

Przykładem tego, w którym używamy tego, jest reprezentacja AST lub wykonanie plany, w których węzły mogą być takie jak Join, Sort itd.

Wektory będą lepsze do tworzenia takich rzeczy jak łańcuchy, w których dowolna liczba rzeczy może być umieszczona w każdym węźle. Jeśli możesz wstawić 1 <p> s wewnątrz <div>, to nie możesz utworzyć rekordu zawierającego pole: p - to po prostu nie ma sensu. To przypadek, w którym wektory są znacznie bardziej elastyczne i idiomatyczne.