---
title: データ構造の階層関係
date: 2025-04-14T02:14:13.000Z
updated: 2026-01-08T14:50:44.579Z
url: https://baku89.com/ja/%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%E3%81%AE%E9%9A%8E%E5%B1%A4%E9%96%A2%E4%BF%82
---

# データ構造の階層関係

より広範な概念から順番に?

もともと「デカルト閉圏 → DG → DAG → Tag → Tree → List」を考えていたんだけど、[chatgpt#icon](/chatgpt#icon)的にはこうreviseしたほうがいいって。

明確に包含関係にあるのは「DG → DAG（+非巡回性） → Tree（+単一親） → List（単一子）」。

Set（集合）はどう考える?

- **CCC**; Closed Cartesian Category

  - [デカルト閉圏](/Cartesian_closed_category)
  - プログラミング言語における型
  - 射そのものを対象にすることができる
  - CCC構造を持つハイパーテキストは構成可能か?
    - つまりページからページへのリンクではなく、リンクからページ、ページからリンク、リンクからリンクへのリンクをを作ることは出来るか？　そしてそれはどういう意味を持つか?

- **Directional Graph**（有向グラフ）

  - 相互参照を許容する
  - ハイパーリンクはコレ
  - [Cosense](/cosense)もDGとしての構造を有している
  - CMSのデータ設計は須らくDGとして設計されていたほうがいいんじゃないか
    - → [Principles for Digital Gardening](/Principles_for_Digital_Gardening)

- **DAG**; Directed Acyclic Graph（非巡回有向グラフ）

  - DGに対して「非巡回性」という制約を付与したもの
  - Program Dependency Tree
  - Reactive Programming
  - ノードベースUI

- **Bipartite Graph**（2部グラフ）

  - オブジェクト（括られるもの; 対象）とタクソノミー（分類子; タグ）の二元論
  - CMS、ファイルシステムでいうTag
  - ラベル、ハッシュタグ
  - オブジェクトは複数のタグに紐づけることができる

- **Tree**

  - DAGに「親が一つだけ」という制約
  - CMSにおけるカテゴリー。（[圏](/%E5%9C%8F)とは異なる意味）
  - ファイルシステム
    - ディレクトリ（括るもの）とファイル（括られるもの）
  - Redditのような電子掲示板

- **List**

  - Tree Sturcutreに「子が一つだけ」という制約
  - 圏論: 始代数
  - 型理論: inductive type（List, Nat）
  - ある元から後続する元へと対応付ける`succ: a -> a` が存在する?
  - 自然数、タイムライン、ストリーム
  - 2ch, 5chのような電子掲示板
    - `>>1` のような参照を通して、DGを構成することが出来る
      - Redditと違って、後続する未来のレスに対してもリンクを張ることができる
  - SNSのタイムラインという概念は、ハイパーテキストが元来持っていたDGとしての性質を喜捨して、Listという構造の表現力の乏しいものにした
    - リツイートという概念は、DAG性の付与? けど単一親ではあるから違う