In Scheme, la primitiva eq? verifica se i suoi argomenti sono lo stesso oggetto. Ad esempio, nel seguente elencoÈ mai possibile rilevare la condivisione in Haskell?
(define lst
(let (x (list 'a 'b))
(cons x x)))
Il risultato di
(eq? (car x) (cdr x))
è vero, ed inoltre è vero senza dover scrutare (car x) e (cdr x). Ciò consente di scrivere test di uguaglianza efficienti per strutture di dati che condividono molto.
È la stessa cosa mai possibile in Haskell? Ad esempio, si consideri la seguente implementazione dell'albero binario
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
che ha condivisione a tutti i livelli. Se creo un albero con let tree = mkTree 30 e voglio vedere se left tree e right tree sono uguali, in modo ingenuo devo attraversare oltre un miliardo di nodi per scoprire che sono lo stesso albero, che dovrebbe essere ovvio a causa della condivisione dei dati.
Non mi aspetto che ci sia un modo semplice per scoprire la condivisione dei dati in Haskell, ma mi sono chiesto quali sono gli approcci tipici per affrontare problemi come questo, quando sarebbe opportuno rilevare la condivisione per scopi di efficienza (o es. per rilevare strutture dati cicliche).
Esistono unsafe primitive in grado di rilevare la condivisione? Esiste un modo ben noto per costruire strutture dati con puntatori espliciti, in modo da poter confrontare l'uguaglianza tra puntatori?
vedere anche http://stackoverflow.com/questions/1717553/pointer-equality-in-haskell – Yuras
Quando si esegue questa operazione, considerare sempre la possibilità che la struttura dati contenga NaN o altri valori non confrontabili loro stessi. La tua ottimizzazione potrebbe essere frenetica. – rightfold