69952


# 前置き

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

[代数的データ型 - ウォークスルー Haskell](http://walk.northcol.org/haskell/adts/)

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

[Algebraic data type -
Wikipedia](https://en.wikipedia.org/wiki/Algebraic_data_type)

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

>     data Tree = Empty
>               | Leaf Int
>               | Node Tree Tree
>  
[/code]

# 質問

## Shape型

[代数的データ型 - ウォークスルー Haskell](http://walk.northcol.org/haskell/adts/) にある

[code]

    data Shape = Rect Double Double
    
[/code]

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

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

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

こんな感じですか？

[code]

    Rect
    ├── Double
    └── Double
    
[/code]

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

[code]

    Shape
    └── Rect(Double, Double)
    
[/code]

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

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

[code]

    Rect
        └── Double
            └── Double
    
[/code]

### 具体的な数値の場合

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

[code]

    Rect
        ├── 2.0
        │   └── 1.0
        ├── 5.0
        │   └── 4.0
        ....
    
[/code]

もしくは

[code]

    Rect
        └── 2.0
            └── 1.0
    や
    Rect
        └── 5.0
            └── 4.0
    
[/code]

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

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

## Tree型

一方  
[Algebraic data type -
Wikipedia](https://en.wikipedia.org/wiki/Algebraic_data_type) にある

[code]

    data Tree = Empty
              | Leaf Int
              | Node Tree Tree
    
[/code]

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

こんな感じでしょうか？

[code]

    Tree
        ├── Empty
        ├── Leaf
        │   └── Int
        └── Node
            ├── Tree
            │   └── 以下略
            └── Tree
                └── 以下略
    
[/code]


CC BY-SA 4.0
2020-08-28T14:46:06.540
69947
2020-08-28T23:55:01.043
2020-08-28T23:24:49.250
9008
9008
question
haskell
代数的データ型は木構造で表現されるとあるが、どのような構造になるのかよくわからない


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

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

[code]

    data Shape = Rect Double Double
    
[/code]

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

[code]

    Rect
    ├── 1.0
    └── 3.14
    
[/code]

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

また `Tree` 型については、

[code]

    data Tree = Empty
              | Leaf Int
              | Node Tree Tree
    
[/code]

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

[code]

    Node
    ├── Leaf
    │   └── 100
    └── Node
        ├── Leaf
        │   └── 200
        └── Leaf
            └── 300
    
[/code]

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

[code]

    Node (Leaf 100) (Node (Leaf 200) (Leaf 300))
    
[/code]

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

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

>
> [![](https://i.stack.imgur.com/qIFa0.png)](https://i.stack.imgur.com/qIFa0.png)

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

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


CC BY-SA 4.0
2020-08-28T23:55:01.043
69952
2020-08-28T23:55:01.043
19110
69947
answer