implementacja podstawowej wyszukiwarki z drzewem prefiksowym

Question

Problem polega na zaimplementowaniu drzewa prefiksów (Trie) w języku funkcjonalnym bez użycia jakiejkolwiek metody przechowywania i iteracji.

Próbuję rozwiązać ten problem. Jak powinienem podejść do tego problemu? Czy możesz podać mi dokładny algorytm lub link, który pokazuje już zaimplementowany w dowolnym języku funkcjonalnym?

Dlaczego Próbuję zrobić => tworząc prostą wyszukiwarkę z cechą

• dodając słowo drzewa
• szukając słowa w drzewie
• usuwanie słowa drzewa

Dlaczego chcę używać języka funkcjonalnego => Chcę poprawić swoje umiejętności rozwiązywania problemów nieco dalej.

UWAGA: Ponieważ jest to mój projekt hobby, najpierw wdrożę podstawowe funkcje.

EDIT:

i) Chodzi mi o "bez korzystania z pamięci masowej" => nie chcę użyć zmiennej przechowywanie (ex int a) odwołanie do zmiennej, tablicy.. Chcę obliczyć wynik rekursywnie, a następnie wyświetlić wynik na ekranie.

ii.) Napisałem kilka linijek, ale potem wymazałem, ponieważ to, co napisałem, rozgniewało mnie. Przepraszam, że nie pokazałem mojego wysiłku.

Answer 1

Spójrz na haskell's Data.IntMap.Jest to czysto funkcjonalna implementacja Patricia trie, a jej oznaczenie source jest całkiem czytelne.
bytestring-trie Pakiet rozszerza to podejście do ByteStrings

Nie towarzyszy papier Fast Mergeable Integer Maps który jest także czytelny i dzięki. Opisuje wdrażanie krok po kroku: od prób binarnych do drzew patricia big-endian.
Oto mały wyciąg z papieru.

W najprostszej, binarny trie jest kompletnym binarne drzewo głębokości równej liczbie bitów w klawisze, gdzie każdy liść jest albo pusty, co wskazuje, że odpowiedni klucz jest niezwiązany lub pełne, w przypadku, który zawiera dane, do których przypisany jest odpowiedni klucz, . Ten styl trie może być reprezentowana w Standard ML jako

datatype 'a Dict = 
    Empty 
    | Lf of 'a 
    | Br of 'a Dict * 'a Dict 

do wyszukiwania wartości w binarnym trie, po prostu przeczytać bitów klucza , idąc w lewo lub w prawo, zgodnie z zaleceniami, dopóki nie osiągnie liść.

fun lookup (k, Empty) = NONE 
    | lookup (k, Lf x) = SOME x 
    | lookup (k, Br (t0,t1)) = 
     if even k then lookup (k div 2, t0) 
       else lookup (k div 2, t1) 

Answer 2

Kluczowym punktem w implementacjach niezmiennych struktur danych jest udostępnianie danych i struktury danych i struktury. Aby zaktualizować obiekt, należy utworzyć jego nową wersję z możliwie największą liczbą współdzielonych węzłów. Konkretnie w przypadku podejść próbujących zastosować następujące podejście.

Rozważmy taką Trie (od Wikipedia):

wyobrazić, że nie dodałem słowo "Inn" jeszcze, ale masz już słowo "w". Aby dodać "inn", musisz utworzyć nową instancję całego trie z dodanym "inn". Jednak nie jesteś zmuszony do skopiowania całej rzeczy - możesz utworzyć tylko nowe wystąpienie węzła głównego (bez etykiety) i prawą banch. Nowy węzeł główny wskaże nowy prawy wiersz, ale do starych innych gałęzi, więc przy każdej aktualizacji większość struktury jest współdzielona z poprzednim stanem.

Jednak klucze mogą być dość długie, więc odtworzenie całej gałęzi za każdym razem jest nadal czasochłonne i zajmuje dużo miejsca. Aby zmniejszyć ten efekt, możesz również udostępniać strukturę wewnątrz jednego węzła. Zwykle każdy węzeł jest wektorem lub mapą wszystkich możliwych wyników (np. W węźle obrazu z etykietą "te" ma 3 wyniki - "a", "d" i "n"). Istnieje wiele implementacji map niezmiennych (Scala, , Clojure, zobacz ich repozytoria po więcej przykładów) i Clojure ma również znakomity implementation niezmiennego wektora (który jest w rzeczywistości drzewem).

Wszystkie operacje związane z tworzeniem, aktualizowaniem i wyszukiwaniem wynikowych prób mogą być realizowane rekurencyjnie bez żadnego stanu zmiennego.