ローズツリー

ノードごとに可変かつ無制限の数の枝を持つ木データ構造

コンピューティングにおいて、ローズツリーとは、ノードごとに可変かつ無制限の数の枝を持つツリーデータ構造の値です。 ^[1]この用語は主に関数型プログラミングコミュニティで使用され、例えばバード・メルテンス形式論の文脈で使用されます。^[2]多分岐性に加えて、ローズツリーの最も重要な特徴は、双相似性と同一性が一致することです。つまり、2つの異なるローズツリーが双相似になることはありません

命名

「バラの木」という名前は、ランバート・メーレンスによって、似た名前で似た構造を持つシャクナゲを想起させるために造られました。^[3]

このような木を、ロドデンドロン（ギリシャ語のῥόδον = バラ、δένδρον = 木）の直訳であるバラの木と呼ぶことにします。これは、この低木の姿に似ているからです。ただし、北半球では逆さまに成長しません。

再帰的定義

整基礎バラの木は、以下の種類の実体の再帰的構築によって定義できます

基本エンティティは、定義済みの値の基底集合 $V$ の要素です（「先端」値^[3]）。
分岐エンティティ(または、フォークエンティティまたはフォレストエンティティ) は、次のいずれかのサブタイプです。
1. エンティティの セット。
2. エンティティの シーケンス。
3. 定義済みの名前のセット $Σ$ からエンティティへの部分的なマップ。
(a)(b)(c) はいずれも空になる可能性がある。(b) は (c) の特殊なケースと見なすことができる点に注意されたい。つまり、数列とは自然数の集合の最初の部分からの写像に過ぎない。 $\mathbb {N}$
ペアリング実体とは、 $F$ が分岐実体であり、 $xが$ 定義済みの「ラベル」値の集合 $L$ の要素となるような順序付きペア $（ F 、 x ）$ である。ペアリング実体は分岐実体を構成要素としてのみ含むことができるため、分岐実体のサブタイプに対応するサブタイプ（3a）、（3b）、または（3c）への誘導的な分割が存在する。

通常、構築には実体型の組み合わせのみが用いられます。原著論文^[3]では、1+2b（「シーケンスフォーク」ローズツリー）と1+2a（「セットフォーク」ローズツリー）のみが検討されています。その後の文献では、1+2bの変種は通常、以下の定義で導入されます。

データ ツリー a = リーフ a | ノード [ツリー a]

ローズツリーは[...]値を含む葉、または任意のサブツリーのリストを持つことができるノードのいずれかです。^[4]

関数型プログラミング（特にHaskell ）で最もよく使われる定義は、3+2b を組み合わせたものです。

データ ローズα = ノードα [ローズα]

Rose αの要素は、ラベル付きノードとサブツリーのリストで構成されます。^[1] つまり、バラの木は、分岐エンティティがバラの木のシーケンス（つまりタイプ2b）であるペアリングエンティティ（タイプ3）です。

場合によっては1+3bの組み合わせも考慮される。^[5]^[6] 次の表は、最も確立されたエンティティの組み合わせの概要を示しています。

用語	使用される実体
整基礎集合	(2a)
十分に根拠のあるネストされたリスト値	(2b)(1)
根拠のある入れ子の辞書値	(2c)(1)
十分に根拠のあるネストされたデータ値	(2b)(2c)(1)
強制的に知られる $L$ 字型の名前	（2a）（3）^{[w 1]}
最も一般的な意味でのしっかりとしたバラの木	（3）（2b）^{[w 1]}

注:

^ ab (2a)(3)と(3)(2b)の組み合わせでは、2番目に記述された実体型は中間的なものであり、最初に記述された型である「最終的な」実体の定義にのみ使用されます。さらに、型は厳密に交互に変化します。つまり、分岐実体は、そのメンバーとしてペアリング実体のみを含むことができます

一般的な定義

一般的なバラの木は、ノードと矢印に適切なラベルを付けたアクセス可能な尖端多重有向グラフの双相似性によって定義できます。これらの構造は、非整集合論におけるアクセス可能な尖端グラフ（略称APG）の概念を一般化したものです。以下で説明する多重有向グラフ構造には、頭字語としてAPQを使用します。これは「アクセス可能な尖端クイバー」の略語であり、「クイバー」は「多重有向グラフ」の確立された同義語です

再帰定義で使用される実体の型に対応して、APQの各ノードには(1)、(2a)、(2b)、(2c)、または(3)のいずれかの型が割り当てられます。APQは、再帰的に構築された実体の特性を模倣する条件に従います。

1. (1)型のノードは、定義済みの基底値集合 $Vの要素である。$
2. (1) 型のノードは矢印のソースとしては表示されません。
1. (3) 型のノードは、正確に 1 つの矢印のソースとして表示されます。
2. (a)で述べた矢印のターゲットはタイプ(2)のノードである。
タイプ(2a)の同じソースノードを持つ2つの異なる矢印には、異なるターゲットがあります。
ノードは、その型が(3)である場合にのみラベル付けされる。ラベルは定義済み集合 $L$ に属する。
1. 矢印のソースノードがタイプ(2b)の場合、矢印にはインデックスが付けられます。 $\mathbb {N}$
2. 矢印のソースノードがタイプ(2c)である場合、矢印には定義済みセット $Σ$ の名前がラベル付けされます。
3. それ以外の場合、矢印にはラベルが付きません。
同じソースノードを持つ矢印のラベルは異なります。
(2b)型の同じソースノードを持つ矢印のラベルは、の初期セグメントを形成します。 $\mathbb {N}$

apqs $𝒳 = ($ $X$ $, ...)$ と $𝒴 = ($ $Y$ $, ...)$ 間の双類似性は、 $𝒳$ と $𝒴$ のルートが $R$ 関連であり、 $R$ 関連ノードのすべてのペア $($ $x$ $,$ $y$ $)$ について、次の条件が満たされるようなノード間の関係 $R$ $\subseteq$ $X$ $\times$ $Yです。$

ノード $x$ と $y$ は同じタイプです。
$x$ と $y$ が(1)型の場合、それらは同一です。
$x$ と $y$ が型（3）の場合、それらは同じラベルを持ちます。
𝒳の矢印a（その始点がx）に対して、 𝒴の矢印b（その始点がy）が存在し、
1. $a$ とb のターゲットノードは $R$ 関連であり、
2. $a$ とb のラベルは、定義されている場合は同一です。
$𝒳$ と $𝒴$ を入れ替えると対称条件が満たされます。

二つのapq $𝒳$ と $𝒴 は、それらに双相似関係$ $R$ が存在する場合、双相似であるといいます。これにより、すべてのapq のクラスに同値関係が確立されます。

ローズツリーとは、与えられたapq $𝒳$ と双相似なapqのクラス $𝒞の$ $、$ ある固定された表現である。𝒳 のルートノードが型(1)であれば $𝒞 = {𝒳$ }となり、 $𝒞は$ このルートノードで表現できる。そうでない場合、 $𝒞は$ 真クラスである。この場合、 $𝒞$ の要素のうち最低ランクの要素の集合としてスコットのトリックによって表現できる。

上記の集合論的構成の結果として、定義構成要素である集合 $V$ (基底値)、 $Σ$ (矢印名)、および $L (ノードラベル) に依存して、すべてのバラの木のクラス$ $ℛが定義されます。その結果、apqs の構造は$ $ℛ$ 上のラベル付き多重ダイグラフ構造に持ち越すことができます。つまり、 $ℛ$ の要素自体は、誘導型割り当て、ノードラベル、および矢印を持つ「ノード」と見なすことができます。矢印のクラス $𝒜は$ $、 (ℛ \times ℛ) \cup (ℛ \times ($ $\cup$ $Σ$ $) \times ℛ)$ のサブクラスです。つまり、矢印は、ソースの種類に応じて、ソース-ターゲットのカップルまたはソース-ラベル-ターゲットのトリプルのいずれかになります。 $\mathbb {N}$

$ℛ$ のあらゆる元 $rに対して$ $、$ $𝒳$ のルートノードである $r$ に対し $、$ $𝒳$ のノードと矢印の集合 $X$ $と$ $Aがそれぞれ$ $r$ から始まる矢印のパスを通じてアクセスできる $ℛ$ と $𝒜$ の元によって形成されるような、誘導された apq 𝒳 = ( $X ,$ $A$ , $r , ...$ $)$ が存在する。誘導された apq $𝒳 は、$ $r$ の構築に用いられる apq と双相似である。

パス名マップ

集合分岐ノードを含まないローズツリー（タイプ2a）は、パス名マップで表現できます。パス名は矢印ラベルの有限列です。矢印パス $a \to = [a 1, ..., a n]$ （連続する矢印の有限列）の場合、 $p$ のパス名は対応する矢印ラベルの列 $σ (a \to) = [σ (a 1), ..., σ (a n)]$ です。ここでは、各矢印にラベルが付けられていると仮定します（ $σ$ はラベル付け関数を表します）。一般に、各矢印パスは、ペアリングノード（タイプ3）をソースとするすべての矢印を削除することで、まず縮小する必要があります。

パス名 $p$ が解決可能であるとは、パス名が $p$ であるルート起点矢印パス $a \to$ が存在する場合のみである。そのような $\to$ $は$ 、ラベルなしの最終矢印（ペアリングノードを起点とする）に一意に割り当てられる。空でない解決可能パスのターゲットノードは、対応するルート起点矢印パスの、ラベルなし矢印で終わらない最終矢印のターゲットノードである。空パスのターゲットはルートノードである。

集合分岐ノードを含まないバラの木 $rが与えられた場合、$ $r$ のパス名マップは、次の一般的なスキームに従って、解決可能な各パス名 $p に$ その値 $t$ $($ $p$ $)$ を割り当てるマップ $tです。$

$\mathbb {N}$ t——— → $(V \cup {⊥} \cup L) \times T$

$\cup$ $Σ$ は矢印ラベルの集合（は自然数の集合、 $Σ$ は矢印名の集合）であり、 $L$ はノードラベルの集合、 $V$ は基底値の集合であることを思い出してください。追加の記号 $⊥$ と $T$ はそれぞれ、解決可能なパス名と型タグの集合（ $T$ $= {'1', '$ $2b', '2c', '3b', '3c'$ }）のインジケータを意味します。tマップは次の式で定義されます（ $x は$ $p$ のターゲットを表します）。 $\mathbb {N}$ $\mathbb {N}$

$t (p) =$	$（ x 、'1'）$	$x$ が(1)型の場合、
	$(⊥, '2b')$ または $(⊥, '2c')$	$x$ がそれぞれ(2b)または(2c)の型である場合、
	$(ℓ, '3b')$ または $(ℓ, '3c')$	$x$ $が$ それぞれ(3b)または(3c)の型であり、 $ℓ\inL が x$ のラベルである場合。

異なるローズツリーは異なるパス名マップを持つことが示されています。「同質」なローズツリーの場合、型タグ付けは不要であり、そのパス名マップ $t$ は以下のように定義できます。

用語	スキーム
ネストされたリスト値	$\mathbb {N}$ t ——— → $V \cup {⊥$ }
ネストされた辞書の値	$Σ ⁎ \supseteq dom(t)$ t ——— → $V \cup {⊥$ }
ハスケル作のバラの木、 $L字型$ ^[7]^[8]	$\mathbb {N}$ t ——— → $L$ ^{[p 1]}
$L$ 値木^{[9] 、} $L$ でラベル付けされた木^[10]	$Σ ⁎ \supseteq dom(t)$ t ——— → $L$ ^{[p 1]}

いずれの場合も、パス名に関しては単純な公理化が存在します。

$dom(t)は$ $⁎$ または $Σ$ $⁎$ の空でない接頭辞閉部分集合です。 $⁎$ の場合、 $dom($ $t$ $)は$ 木ドメインを形成するために「左兄弟閉」である必要があります。シーケンスによるエンコードを参照してください。 $\mathbb {N}$ $\mathbb {N}$
ネストされたリストまたはネストされた辞書値の場合、 $pが$ $dom(t)$ 内で最大でないパス名であれば、 $t (p)=⊥となる$ 。^{[p 2]}

特に、最も一般的な「Haskell」的な意味でのバラの木とは、空でない前置閉かつ左兄弟閉の自然数の有限列の集合から集合 $L$ への写像に過ぎません。このような定義は、関数型プログラミングの分野以外で主に用いられます（木（オートマトン理論）を参照）。通常、この定義を用いる文書では「バラの木」という用語は全く使用されません。

注:

^ ab $dom($ $t$ $) =$ $M$ $⁎$ （のサブセットまたは $Σ$ の場合）であれば、パス名マップ $tは、入力シンボルのシーケンスを$ ムーアマシンの出力シンボルにマッピングしたものです。具体的には、入力シンボルの集合 $M$ がの初期セグメントであり、すべての状態が到達可能であるすべてのムーアマシンは、Haskellの意味でローズツリーと双相似です。非整基盤ローズツリーの例を参照してください。ネストされた辞書（またはリスト）とミーリーマシンの間にも同様の関係が見られます。ネストされた辞書を参照してください。 $\mathbb {N}$ $\mathbb {N}$
^ ネストされたリストまたはネストされた辞書がそれぞれリストまたは辞書であることを保証するには、空のパス名 $pに対して条件$ $t (p) = ⊥ が$ 明示的に成立する必要がある。これは、のようなケースが「ツリー値」とはみなされないことを示唆している。x = 5

例

下の図は、バラの木の2つの例と、対応するHaskellコードを示しています。どちらの場合も、Haskellコンテナパッケージ[12]で提供されているData.Treeモジュール[ ¹¹^]が使用されています。このモジュールは、次の定義によってバラの木をペアリングエンティティとして導入します

データTree a = Node { rootLabel :: a , -- ^ ラベル値subForest :: [ Tree a ] -- ^ 0個以上の子ツリー}

どちらの例も、バラの木の際立った特徴である「部分構造の共有」 ^[13]の概念を示すために考案されています。どちらの場合も、ラベル付け関数は単射（つまり、ラベル'a'、'b'、'c'またはが'd'部分木／ノードを一意に識別する）であり、これは一般に満たされる必要はありません。矢印に沿う自然数（0、1、2、または3）は、subForest特定の「スーパーツリー」のシーケンスにおいて、ツリーが現れるゼロベースの位置を示します。が繰り返しになる可能性があるためsubForest、ノード間に複数の矢印が存在する可能性があります。それぞれの例において、問題のバラの木はでラベル付けされ'a'、コード内の変数の値に等しくなりますa。どちらの図でも、ツリーはソースのない矢印によって指されています。

根元のしっかりしたバラの木

Data.Treeをインポートします。main:: IO ( ) main = do let d = Node { rootLabel = 'd' , subForest = [] } let c = Node { rootLabel = 'c' , subForest = [ d ] } let b = Node { rootLabel = 'b' , subForest = [ d , c ] } let a = Node { rootLabel = 'a' , subForest = [ b , c , c , c ] } print a

根元のしっかりしていないバラの木

import Data.Tree main :: IO () main = do let root x = case x of 'a' -> ( x ,[ x , 'b' ]) 'b' -> ( x ,[ x , 'c' ]) 'c' -> ( x ,[ x , 'a' ]) let a = unfoldTree root 'a' putStrLn ( take 900 ( show a ) ++ "... (以下同様)" )

a最初の例は、増分構築によって得られた整基礎ローズツリーを示しています。最初にdが構築され、次にcが構築されb、最後にが構築されますa。ローズツリーは、左側に示すパス名マップで表すことができます。

a2番目の例は、幅優先コンストラクタによって構築された非整基礎ローズツリーですunfoldTree。ローズツリーはムーアマシンです（上記の注記を参照）。そのパス名マップ $t : {0,1} ⁎ \to {'a','b','c'$ } は、 $t (p)が$ $n$ $mod 3$ に従ってそれぞれ $'a'$ または $'b'$ または $'c'$ に等しいと定義されます（ $nは$ $p$ における $1$ の出現回数）。

ツリーデータ構造との関係

一般的な定義は、ツリーデータ構造への接続を提供します。

ローズツリーは双相似性を法とするツリー構造です。

ツリーデータ構造をその値にマッピングする

「木構造」とは、各ノードに一意の矢印パスでアクセスできるAPQ（一般的な定義では多重有向グラフと呼ばれる）のことです。すべてのバラの木は、このような木構造と双相似です（すべてのAPQはその展開と双相似であるため）。また、このような木構造はすべて、まさに1つのバラの木と双相似であり、したがって、そのバラの木は木構造の値と見なすことができます。

右の図は、このような構造から値へのマッピングの例を示しています。図の上部には、23個のノードを含む、ノードラベル付きの順序付きツリー $Tが表示されています。下部には、$ $T$ の値であるローズツリー $Rが表示されています。（$ $T$ と $R$ の両方において、兄弟矢印は暗黙的に左から右へ順序付けられています。）青い矢印で部分的に示されているように、サブツリーからサブ値へのマッピングが誘導されています。

多対一のマッピングであることに注目してください。つまり、異なるツリーデータ構造が同じ値を持つ可能性があります。結果として、バラの木は一般に、その部分値間の「部分値」関係の観点からはツリーではありません。#用語論争を参照してください。

ツリーデータ型

上記の値のマッピングは、「ツリーデータ構造」と「ツリーデータ型」という用語の違いを明確にするために使用できます

ツリーデータ型は、ツリーデータ構造の値の集合です。^{[dt 1]}

これらの用語には2段階の差異があることに注意してください。これは、単一のツリーデータ型と単一のツリーデータ構造を比較すると明らかになります。単一のツリーデータ型には（無限に）多くの値が含まれており、それぞれの値は（無限に）多くのツリーデータ構造によって表現されます。

例えば、ラベルの集合 $L = {'a','b','c','d'$ } が与えられたとき、Haskell の意味で (3b) のバラの木の集合（ラベルは $L$ から取得）は単一の木データ型です。上記のバラの木の例はすべてこのデータ型に属します。

注:

^ ただし、ツリーデータ構造の値の集合すべてがツリーデータ型であるわけではありません

用語論争

上記の文章と図からわかるように、「バラの木」という用語は議論の的となっています。2つの関連する問題があります

「ノード」の意味が不明瞭です。
「ツリー」と「サブ構造の共有」の間の矛盾。

興味深いことに、「ノード」という用語は原著論文^[3]には登場せず、20ページの非公式な段落に「ノード群」が1回だけ登場するのみである。後続の文献ではこの語が頻繁に使用されている。これは、引用した定義に関するコメントからも既に見て取れる。

バラの木は[...]葉[...]または節[...]のいずれかです。^[4]
Rose αの要素はラベル付きノード[...]から構成されます。^[1]

特に、Haskellにおける最も一般的な意味でのバラの木の定義は、（議論の文脈において）「ノード」と「ツリー」が同義語であることを示唆しています。これは、すべてのバラの木がそのルートノードと一致することを意味するのでしょうか？もしそうであれば、そのような性質はバラの木に特有のものなのでしょうか、それとも他の木にも当てはまるのでしょうか？こうした疑問は未解決のままです。

(B)の問題は、上記の例の図を見ると明らかです。どちらの図も、各ノードが正確に1回描かれているという意味で忠実です。基になるグラフが木ではないことはすぐにわかります。「木（グラフ理論）」からの引用を用いると、

コンピュータサイエンスでツリーと呼ばれるさまざまな種類のデータ構造には、グラフ理論のツリーである基礎グラフがあります [...]

一般的にバラの木は、コンピュータ科学で知られている通常の意味での木ではないと結論付けることができます。

ベイジアン・ローズツリー

コンピュータサイエンスにおいて、「ローズツリー」という用語が採用されている事例が少なくとも1つあります。その事例では、「部分構造の共有」は排除されています。ベイジアン・ローズツリーの概念は、以下のローズツリーの定義に基づいています

$T$ がバラの木であるとは、あるデータポイント $xに対して$ $T = {x$ }であるか、または $T$ $= {$ $T$ $1$ $, ... ,$ $T$ $n$ $T$ }であり、 $T$ $i$ が互いに素なデータポイントの集合上のバラの木である場合を指す。^[14]

参考文献

^ abc Bird, Richard (1998). Haskellを用いた関数型プログラミング入門. ヘメル・ヘムステッド, ハートフォードシャー, イギリス: Prentice Hall Europe. p. 195. ISBN 0-13-484346-0。
^ マルコム、グラント (1990). 「データ構造とプログラム変換」.コンピュータプログラミングの科学. 14 (2): 255–279 . doi : 10.1016/0167-6423(90) 90023-7
^ abcd Meertens, Lambert (1988年1月). 「バラの木の理論への第一歩」(PDF) . {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
^ ab リチャード・バード、ジェレミー・ギボンズ（2020年）『Haskellによるアルゴリズム設計』ケンブリッジ大学出版局、ISBN 9781108491617。
^ Skillicorn, David B. (1996). 「ツリースケルトンの並列実装」(PDF) . Journal of Parallel and Distributed Computing . 39 (2): 115– 125. doi :10.1006/jpdc.1996.0160
^ シーマン、マーク。「教会で暗号化されたバラの木」。
^ モラウィエツ、フランク (2008). 自然言語形式主義への2段階アプローチ. ウォルター・デ・グリュイター. ISBN 9783110197259。
^ コスキー、アンソニー (1995). 再帰データ構造によるデータベースの変換 (学位論文).
^ Niwiński, Damian (1997). 「有限状態システムの無限挙動の固定小数点による特徴づけ」(PDF) .理論計算機科学. 189 ( 1–2 ): 1–69 . doi :10.1016/S0304-3975(97)00039-X.
^ Dagnino, Francesco (2020). 「Coaxioms: flexible coinductive definitions by inference systems. Logical Methods in Computer Science . 15 4745. arXiv : 1808.02943 . doi :10.23638/LMCS-15(1:26)2019. S2CID 51955443.
^ 「Data.Tree」
^ 「コンテナ：様々なコンクリートコンテナの種類」
^ ギボンズ、ジェレミー (1991). 木アルゴリズムのための代数(PDF) (Ph.D.). オックスフォード大学.
^ Blundell, Charles; Whye Teh, Yee; Heller, Katherine A. (2010). ベイジアンローズツリー(PDF) . 第26回人工知能における不確実性に関する会議.

[PairingCombined-7] (2a)(3)と(3)(2b)の組み合わせでは、2番目に記述された実体型は中間的なものであり、最初に記述された型である「最終的な」実体の定義にのみ使用されます。さらに、型は厳密に交互に変化します。つまり、分岐実体は、そのメンバーとしてペアリング実体のみを含むことができます

[Moore-11] $dom($ $t$ $) =$ $M$ $⁎$ （のサブセットまたは $Σ$ の場合）であれば、パス名マップ $tは、入力シンボルのシーケンスを$ ムーアマシンの出力シンボルにマッピングしたものです。具体的には、入力シンボルの集合 $M$ がの初期セグメントであり、すべての状態が到達可能であるすべてのムーアマシンは、Haskellの意味でローズツリーと双相似です。非整基盤ローズツリーの例を参照してください。ネストされた辞書（またはリスト）とミーリーマシンの間にも同様の関係が見られます。ネストされた辞書を参照してください。 $\mathbb {N}$ $\mathbb {N}$

[NonContainerRoot-14] ネストされたリストまたはネストされた辞書がそれぞれリストまたは辞書であることを保証するには、空のパス名 $pに対して条件$ $t (p) = ⊥ が$ 明示的に成立する必要がある。これは、のようなケースが「ツリー値」とはみなされないことを示唆している。x = 5

[RawDelimitation-20] ただし、ツリーデータ構造の値の集合すべてがツリーデータ型であるわけではありません

[Bird1988-1] Bird, Richard (1998). Haskellを用いた関数型プログラミング入門. ヘメル・ヘムステッド, ハートフォードシャー, イギリス: Prentice Hall Europe. p. 195. ISBN 0-13-484346-0。

[2] マルコム、グラント (1990). 「データ構造とプログラム変換」.コンピュータプログラミングの科学. 14 (2): 255–279 . doi : 10.1016/0167-6423(90) 90023-7

[Meertens1988-3] Meertens, Lambert (1988年1月). 「バラの木の理論への第一歩」(PDF) . {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です

[Bird2020-4] リチャード・バード、ジェレミー・ギボンズ（2020年）『Haskellによるアルゴリズム設計』ケンブリッジ大学出版局、ISBN 9781108491617。

[Skillicorn1996-5] Skillicorn, David B. (1996). 「ツリースケルトンの並列実装」(PDF) . Journal of Parallel and Distributed Computing . 39 (2): 115– 125. doi :10.1006/jpdc.1996.0160

[Seemann2020-6] シーマン、マーク。「教会で暗号化されたバラの木」。

[Morawietz2008-9] モラウィエツ、フランク (2008). 自然言語形式主義への2段階アプローチ. ウォルター・デ・グリュイター. ISBN 9783110197259。

[Kosky1995-10] コスキー、アンソニー (1995). 再帰データ構造によるデータベースの変換 (学位論文).

[Niwinski1997-12] Niwiński, Damian (1997). 「有限状態システムの無限挙動の固定小数点による特徴づけ」(PDF) .理論計算機科学. 189 ( 1–2 ): 1–69 . doi :10.1016/S0304-3975(97)00039-X.

[Dagnino2020-13] Dagnino, Francesco (2020). 「Coaxioms: flexible coinductive definitions by inference systems. Logical Methods in Computer Science . 15 4745. arXiv : 1808.02943 . doi :10.23638/LMCS-15(1:26)2019. S2CID 51955443.

[HaskellDataTree-17] 「Data.Tree」

[HaskellContainers-18] 「コンテナ：様々なコンクリートコンテナの種類」

[Gibbons1991-19] ギボンズ、ジェレミー (1991). 木アルゴリズムのための代数(PDF) (Ph.D.). オックスフォード大学.

[Blundell2010-22] Blundell, Charles; Whye Teh, Yee; Heller, Katherine A. (2010). ベイジアンローズツリー(PDF) . 第26回人工知能における不確実性に関する会議.