Can we think of immutable lists as a dual to trees?

Question

I might draw a list of words like:

this -> is -> a -> test

and then through sharing, I might draw two lists as:

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

Now, if I reverse the arrows, I get a tree, with test as the root. This is the same notion as duality in graph/category theory. Therefore, I can think of trees and lists as dual concepts.

Is this correct/useful?

Answer 1

Sharing and laziness allow you to have arbitrary cyclic structures. For example, in Haskell the definition

ones = 1 : ones

produces a graph consisting of a single vertex (corresponding to 1) and a loop (in graph-theoretic, not programming sense). By reversing the arrows, you'd get the same structure, and it's not a tree (as it's got loops).

So, it's not true in a lazy language.