W schemacie prymitywny eq?
sprawdza, czy jego argumenty są tym samym obiektem. Na przykład w poniższym wykazieCzy kiedykolwiek można wykryć udostępnianie w Haskell?
(define lst
(let (x (list 'a 'b))
(cons x x)))
Wynik
(eq? (car x) (cdr x))
jest prawdą, a ponadto prawdą jest bez mającego zajrzeć do (car x)
i (cdr x)
. Pozwala to pisać wydajne testy równości dla struktur danych, które mają dużo wspólnego.
Czy to samo jest możliwe w Haskell? Na przykład, rozważmy następujący binarny realizację drzewo
data Tree a = Tip | Bin a (Tree a) (Tree a)
left (Bin _ l _) = l
right (Bin _ _ r) = r
mkTree n :: Int -> Tree Int
mkTree 0 = Tip
mkTree n = let t = mkTree (n-1) in Bin n t t
który dzielenie na każdym poziomie. Jeśli utworzę drzewo z let tree = mkTree 30
i chcę sprawdzić, czy left tree
i right tree
są równe, naiwnie muszę przemieścić ponad miliard węzłów, aby odkryć, że są to te same drzewa, co powinno być oczywiste z powodu udostępniania danych.
Nie spodziewam się, że istnieje prosty sposób na odkrycie udostępniania danych w Haskell, ale zastanawiałem się, jakie są typowe podejścia do rozwiązywania takich problemów, kiedy dobrze byłoby wykryć udostępnianie dla celów efektywności (lub np. do wykrywania cyklicznych struktur danych).
Czy są tam prymitywy, które mogą wykryć udostępnianie? Czy istnieje dobrze znany sposób budowania struktur danych z wyraźnymi wskaźnikami, abyś mógł porównać wskaźnik równości?
Zobacz także http://stackoverflow.com/questions/1717553/pointer-equality-in-haskell – Yuras
Kiedy to zrobisz, zawsze rozważ możliwość, że twoja struktura danych zawiera NaN lub inne wartości, które nie są równe sami. Twoja optymalizacja może być przełomowa. – rightfold