Possiamo pensare ad elenchi immutabili come doppi agli alberi?

Question

potrei disegnare un elenco di parole come:

this -> is -> a -> test 

e poi attraverso la condivisione, potrei disegnare due liste come:

this -> is -> a -> test 
        ^
        | 
that -> was -> a -> hard 

Ora, se io invertire le frecce, ottengo un albero, con test come root. Questa è la stessa nozione della dualità nella teoria del grafico/categoria. Pertanto, posso pensare ad alberi ed elenchi come concetti duali.

È corretto/utile?

Answer 1

La condivisione e la pigrizia consentono di avere strutture cicliche arbitrarie. Ad esempio, in Haskell definizione

ones = 1 : ones 

produce un grafico costituito da un singolo vertice (corrispondente a 1) ed un anello (grafico teoria, non si programma senso). Invertendo le frecce, otterresti la stessa struttura e non è un albero (dato che ha dei loop).

Quindi, non è vero in un linguaggio pigro.