Czytałem rozdział w LYAH, który tak naprawdę nie miał dla mnie sensu. Rozumiem, że zamki błyskawiczne mogą dowolnie przechodzić przez strukturę przypominającą drzewo, ale potrzebuję trochę wyjaśnień na ten temat. Czy zamki można uogólnić na dowolną strukturę danych?
ds.data-structures
functional-programming
tree
n_ary_crazy
źródło
źródło
Odpowiedzi:
Zamek błyskawiczny to ogólnie struktura danych z dziurą. Do przesuwania / manipulowania strukturami danych używane są zamki błyskawiczne, a otwór odpowiada bieżącemu ogniskowaniu przejścia. Zazwyczaj bierze się również pod uwagę element struktury danych, tak że ma się suwak (lista) i suwak listy lub (drzewo) i drzewo. Zamek błyskawiczny pozwala programiście efektywnie poruszać się po strukturze danych, zastępując nawet element w centrum uwagi. Para zamka błyskawicznego i element w ognisku spełniają warunek, że umieszczenie elementu w ognisku w otworze zapewnia oryginalną strukturę danych.
Zamki błyskawiczne można uogólniać na dowolne typy danych indukcyjnych. Pojęcie to można zdefiniować w sposób indeksowany według typu (patrz typy danych indeksowane według typu ). Są one również związane z ideą pochodnej struktury danych i zostały zbadane z perspektywy teorii teoretycznej .
źródło
Zamek błyskawiczny to na ogół para rzeczy: to struktura z dziurą, skupienie , reprezentujące miejsce w strukturze, w którym się znajdujesz, wraz ze ścieżką , rejestrujące, jak doszedłeś do tego skupienia. (Ta ścieżka jest śladem LYAH bułki tartej.)
Ścieżka jest sposobem, w jaki faktycznie stosujesz zmiany w strukturze: „idź w dół, idź w lewo, zwiększ wartość”. Poprzez wielokrotne stosowanie „idź w górę” (
go_upw pracy Hueta ) w tym momencie, możesz prześledzić swoje kroki i otrzymać nową, zmutowaną kopię oryginalnej struktury.Rzeczywiście można je uogólnić na inne struktury:
źródło