list - 不変リストをツリーの二重と考えることができますか？

Question

私は次のような単語のリストを描くかもしれません：

this -> is -> a -> test

次に、共有を通じて、次のように2つのリストを作成する場合があります。

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

ここで、矢印を逆にすると、テストをルートとするツリーが得られます。これは、グラフ/圏論の双対性と同じ概念です。したがって、ツリーとリストは二重の概念と考えることができます。

これは正しい/便利ですか？

Answer 1

共有と怠惰により、任意の循環構造を持つことができます。たとえば、Haskellでは定義

ones = 1 : ones

単一の頂点（1に対応）とループ（グラフ理論で、プログラミングの意味ではない）で構成されるグラフを生成します。矢印を逆にすると、同じ構造になり、ツリーではなくなります（ループがあるため）。

ですから、怠惰な言語ではそうではありません。