Czy możemy myśleć o niezmiennych listach jako podwójnych do drzew?

Question

mogę narysować listę słów takich jak:

this -> is -> a -> test 

a następnie poprzez dzielenie, mogę narysować dwie listy jako:

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

Teraz, jeśli odwrócić strzałek, mam drzewo, z testem jako root. Jest to to samo pojęcie, co dualność w teorii grafów/kategorii. Dlatego mogę myśleć o drzewach i listach jako podwójnych pojęciach.

Czy to jest poprawne/użyteczne?

Answer 1

Dzielenie się i lenistwo umożliwiają posiadanie dowolnych cyklicznych struktur. Na przykład, w Haskell definicja

ones = 1 : ones 

wytwarza wykres składający się z jednego wierzchołka (odpowiadającą 1), uchwyt (na wykresie, teoretycznie, nie programowania znaczeniu). Odwracając strzałki, otrzymasz tę samą strukturę i nie jest to drzewo (ponieważ ma pętle).

To nie jest prawda w leniwym języku.