È possibile fare una ricerca su un grafico costruito con la strategia del nodo?

Question

La strategia legatura-the-nodo può essere utilizzato per costruire i grafici come, utilizzando un semplice grafico a doppio taglio come esempio:

data Node = Node Node Node 

-- a - b 
-- | | 
-- c - d 
square = a where 
    a = Node b c 
    b = Node a d 
    c = Node a d 
    d = Node b c 

Questa strategia è piuttosto elegante, ma non sono riuscito a trovare un modo per usarlo effettivamente senza etichette Int. Ad esempio, come posso scrivere una funzione che conta la quantità di nodi sul valore square?

countNodes :: Node -> Int 
countNodes = ... ??? ... 

main = print $ countNodes square 
-- output: 4 

Answer 1

Hai davvero bisogno di un qualche tipo di etichettatura, perché da Haskell all'interno non c'è modo di distinguere i nodi come scritti. Infatti, quando un compilatore Haskell vede

square = a where 
    a = Node b c 
    b = Node a d 
    c = Node a d 
    d = Node b c 

è interamente legale per rilevare che a e d, nonché b e c, sono definiti da uguali espressioni, e di attuare ciascuna coppia come uno oggetto sottostante. (Si chiama eliminazione di sottoespressione comune.)

In effetti, sarebbe addirittura legale per esso identificare tutti e quattro, anche se dubito che i compilatori lo facciano davvero perché richiederebbe che abbiano esattamente la stessa "denotazione" semantica , essendo tutti i modi essenzialmente diversi di scrivere l'albero infinito t = Node t t = Node (Node ... ...) (Node ... ...) - dal punto di vista della semantica denotazionale è il valore solo del tipo di dati che non contiene fondi.

Answer 2

In generale si deve essere in grado di confrontare un nodo per uguaglianza con nodi precedentemente osservati per determinare sei infatti rivisitare una porzione del grafico invece di avere decended in un sottografo di struttura simile. Questo indipendentemente dal modo in cui sintatticamente esprimi i tuoi nodi o in quale lingua.

Ad esempio, utilizzando le rappresentazioni fornite non è possibile distinguere un grafico della

a - b 
| | 
c - d 

da

a - b 
|/
c 

o

a - b - c 
|  | 
d - e - f 

o anche

a - b     a - 
| | or heck even | | 
- - -     -- 

Ogni osservazione locale è un nodo con due bordi a entità indistinguibili.

Se si aggiunge un identificatore, ad esempio un int, ai bordi o ai nodi, oppure si imbroglia e si ruba un identificatore (come un indirizzo, ma in Haskell questo non è deterministico a causa del GC) allora si potrebbe essere in grado di utilizzare queste informazioni per inferire l'uguaglianza o la disuguaglianza.

Answer 3

È possibile osservare la condivisione in IO, utilizzando ad es. data-reify:

{-# LANGUAGE TypeFamilies #-} 
import Data.Reify 

data Node = Node Node Node 
data NodeId s = NodeId s s 

instance MuRef Node where 
    type DeRef Node = NodeId 
    mapDeRef f (Node n1 n2) = NodeId <$> f n1 <*> f n2 

L'attuazione di countNodes è ormai banale (ma nota che è in IO!)

countNodes :: Node -> IO Int 
countNodes n = do 
    Graph nodes root <- reifyGraph n 
    return $ length nodes 

Il vostro esempio:

square :: Node 
square = a where 
    a = Node b c 
    b = Node a d 
    c = Node a d 
    d = Node b c 

*Main> print =<< countNodes square 
4