2

前置き

下記の例のように代数的データ型は木構造で表現されるという説明がありますが、どのような構造になるのかいまいち理解できません。

代数的データ型 - ウォークスルー Haskell

代数的データ型(algebraic data type)とは,図のように木構造で表現される値からなるデータ型のことです. 配列のような一部の例外を別とすれば,Haskell で取り扱うあらゆるデータ型は代数的データ型です.
もう少しきちんと説明すると,代数的データ型は項(term)の形で表されるデータの集合を定義するデータ型です.

Algebraic data type - Wikipedia

For a slightly more complex example, binary trees may be implemented in Haskell as follows:

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

質問

Shape型

代数的データ型 - ウォークスルー Haskell にある

data Shape = Rect Double Double

この Shape はどのような木構造になるのでしょうか?

下記答えになりそうなもので考えたものを列挙します。

たぶん違うんじゃないかと思いながら書いたイメージ

こんな感じですか?

Rect
├── Double
└── Double

それともこんな感じ?(下記自分でもなにを書いているのかよくわかってないですが強引に書いてます)

Shape
└── Rect(Double, Double)

おそらく一番正解に近そうと思いながら書いたイメージ

おそらく一番正解に近そうなものは下記と推測

Rect
    └── Double
        └── Double

具体的な数値の場合

Doubleは複数の値を取り得るので、実際に値を与えた感じは下記のような感じでしょうか(数字は適当)。

Rect
    ├── 2.0
    │   └── 1.0
    ├── 5.0
    │   └── 4.0
    ....

もしくは

Rect
    └── 2.0
        └── 1.0
や
Rect
    └── 5.0
        └── 4.0

みたいに具体的な変数ごとに独立して考えるんでしょうか?

おそらく独立のほうが正しいと推測しています、というか Doubleが取り得る値 * Doubleが取り得る値パターンあるツリーの中から具体的な値を1つずつ選ぶイメージのような気がしてます。

Tree型

一方
Algebraic data type - Wikipedia にある

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

Tree はどのような木構造になるのでしょうか?(これでバイナリーツリーのようですがよくわかりません)

こんな感じでしょうか?

Tree
    ├── Empty
    ├── Leaf
    │   └── Int
    └── Node
        ├── Tree
        │   └── 以下略
        └── Tree
            └── 以下略

1 件の回答 1

3

ここでいう「木構造」とは、その型の項の抽象構文木を考えると分かりやすいでしょう。

下で与えられる Shape 型に対し、

data Shape = Rect Double Double

Shape 型の項としてはたとえば Rect 1.0 3.14 というのが考えられます。この項に対応する木構造は下のものです。

Rect
├── 1.0
└── 3.14

これは辺の長さが 1.0 と 3.14 である長方形を表している訳です。Rect コンストラクタはふたつの引数を受け取るので、木構造としては子がふたつあるノードになっています。

また Tree 型については、

data Tree = Empty
          | Leaf Int
          | Node Tree Tree

その項の木構造の例は以下です。

Node
├── Leaf
│   └── 100
└── Node
    ├── Leaf
    │   └── 200
    └── Leaf
        └── 300

これで葉が 3 つある木のひとつを表している訳ですね。項としては

Node (Leaf 100) (Node (Leaf 200) (Leaf 300))

です。Node コンストラクタと Leaf コンストラクタで引数の数が違うことに注意してください。

また、参考にされている「ウォークスルー Haskell」にも例が載っているので引用します。

http://walk.northcol.org/haskell/adts/

このように、代数的データ型は特定のルールに従った木構造たちを生み出す生成器のようなもので、その型の項はそのルールに従うあるひとつの木構造と対応しているのです。

3
  • ありがとうございます。おおよそ理解できました。TreeEmpty の場合はどうでしょうか? 木構造の端にEmptyを置くのも変なんで、Empty単体でしか存在しないんでしょうか。 Commented 2020年8月29日 0:20
  • ナイスキャッチで、その場合は Empty という 木構造 になります。ノードがひとつだけの木構造で、エッジがひとつもありませんがそれでも木構造です。
    – nekketsuuu
    Commented 2020年8月29日 0:23
  • ちょっと実際に書いてみて、またわからないところが出てしまいましたので別件で‎質問しました。念の為記載しておきます。 Commented 2020年8月29日 0:48

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。