Szybkie wyszukiwanie elementów dla języka funkcyjnego (Haskell)

Question

Powiedzmy, że przechodzimy przez wykres i chcemy szybko stwierdzić, czy dany węzeł był widziany wcześniej czy nie. Mamy kilka ustalonych warunków wstępnych.

1. węzły oznaczone liczbami wartości 1..n
2. wykres jest realizowane z węzłami o listę przylegania
3. Każda wartość całkowitą od 1..n występuje na wykresie, który ma wielkość N

Jakieś pomysły na zrobienie tego w czysto funkcjonalny sposób? (Nie dozwolone tabele lub tablice skrótu).

Chcę struktury danych z dwiema funkcjami nad nią pracującymi; add (dodaje napotkaną liczbę całkowitą) i lookup (sprawdza czy liczba całkowita została dodana). Oba powinny korzystnie przyjąć czas (n) zamortyzowany na N powtórzeń.

Czy to możliwe?

Answer 1

Można użyć numeru Data.Set. Dodajesz element, tworząc nowy zestaw ze starego z insert i przekazujesz nowy zestaw dookoła. Sprawdzasz, czy element jest elementem zestawu z member. Obie operacje to O (log n).

Być może warto rozważyć użycie monady stanu do gwintowania przejścia zestawu.

Answer 2

Efektywne wyszukiwanie elementów w językach funkcyjnych jest dość trudne. Data.Set (jak pokazano powyżej) zaimplementowano przy użyciu drzewa binarnego, które można zbudować w czysto funkcjonalny sposób, zapewniając operacje wyszukiwania w O (log n). HashTables (które nie są czysto funkcjonalne) miałyby O (1).

Answer 3

Wierzę, że Data.BitSet może być O (n).

Answer 4

Spójrz na judy hashtables, jeśli nie masz nic przeciwko zawijaniu kodu w Monadzie IO.