

[代数的データ型は木構造で表現されるとあるが、どのような構造になるのかよくわからない](https://ja.stackoverflow.com/questions/69947/%e4%bb%a3%e6%95%b0%e7%9a%84%e3%83%87%e3%83%bc%e3%82%bf%e5%9e%8b%e3%81%af%e6%9c%a8%e6%a7%8b%e9%80%a0%e3%81%a7%e8%a1%a8%e7%8f%be%e3%81%95%e3%82%8c%e3%82%8b%e3%81%a8%e3%81%82%e3%82%8b%e3%81%8c-%e3%81%a9%e3%81%ae%e3%82%88%e3%81%86%e3%81%aa%e6%a7%8b%e9%80%a0%e3%81%ab%e3%81%aa%e3%82%8b%e3%81%ae%e3%81%8b%e3%82%88%e3%81%8f%e3%82%8f%e3%81%8b%e3%82%89%e3%81%aa%e3%81%84)
の[回答](https://ja.stackoverflow.com/a/69952/9008)を受けて実際にコードを書いてみてよくわからないところが出たので別の質問として投稿します。

[code]

    data Tree = Empty
              | Leaf Int
              | Node Tree Tree
              
    v = Node (Leaf 100) (Node (Leaf 200) (Leaf 300)) -- OK
    w = Empty -- OK
    x = Node(Empty) -- OK
    y = Node(Node(Empty), Node(Empty)) -- NG
    z = Node(Empty, Empty) -- NG
    
[/code]

上記コードを書いてみたところ

[code]

    y = Node(Node(Empty), Node(Empty)) -- NG
    
[/code]

箇所のエラーは

[code]

    <playground>:8:9: error:
        • Couldn't match expected type ‘Tree’
                      with actual type ‘(Tree -> Tree, Tree -> Tree)’
        • In the first argument of ‘Node’, namely
            ‘(Node (Empty), Node (Empty))’
          In the expression: Node (Node (Empty), Node (Empty))
          In an equation for ‘y’: y = Node (Node (Empty), Node (Empty))
    
[/code]

となりました。

[code]

    z = Node(Empty, Empty) -- NG
    
[/code]

箇所のエラーは

[code]

    <playground>:9:9: error:
        • Couldn't match expected type ‘Tree’
                      with actual type ‘(Tree, Tree)’
        • In the first argument of ‘Node’, namely ‘(Empty, Empty)’
          In the expression: Node (Empty, Empty)
          In an equation for ‘z’: z = Node (Empty, Empty)
    
[/code]

となりました。そもそも、[回答](https://ja.stackoverflow.com/a/69952/9008)のコメントにも書いたとおり、木構造の端にEmptyを置くのも変なので、このエラーは役に立つと思うのですが、`Node
(Leaf 200) (Leaf 300)`が許されて、`Node (Empty,
Empty)`がコンパイルエラーの理屈がわかりません。コンストラクタの理解が甘いのでしょうか？

エラーとは話がそれてしまいますが

[code]

    x = Node(Empty) -- OK
    
[/code]

の書き方もおそらく`Tree`作者の意図した使い方ではないと思っています。下記のようにいきなり `Empty` であれば納得感が高いです。

[code]

    w = Empty -- OK
    
[/code]

Haskellを書いているツールはあんまり関係ないと思いますが念の為記載します。[‎Haskell on the Mac App
Store](https://apps.apple.com/jp/app/haskell/id841285201?l=en&mt=12) で
Haskellを書いています。


CC BY-SA 4.0
2020-08-29T00:46:31.317
69953
2020-08-29T06:39:57.613
2020-08-29T06:39:57.613
3060
9008
question
haskell
Couldn't match expected type ‘Tree’ with actual type ‘(Tree, Tree)’ になる理由がわからない


コメントを受けて自己回答してみます。

[code]

    z = Node(Empty, Empty) -- NG
    
[/code]

がNGなのはコメントの通り

[code]

    (Empty, Empty)
    
[/code]

の部分がタプルとみなされてNG。正しくはコメントの通り、

[code]

    Node Empty Empty
    
[/code]

さて

[code]

    x = Node(Empty) -- OK
    
[/code]

がOKな理由は下記のコードで試せる。

[code]

    data Tree = Empty
              | Leaf Int
              | Node Tree Tree deriving Show
              
    hoge = Node Empty Empty -- Node Empty Empty
    bar = Node(Empty) -- 該当箇所
    barbar = bar Empty -- Node Empty Empty
    
    main = print $ barbar
    
[/code]

つまり部分適用されている（というかデータ構造に部分適用あるのだろうか。この名称であっているのだろうか？）。 `Node(Empty)`は`Node
Empty`と同じ意味と考えられる。

[code]

    y = Node(Node(Empty), Node(Empty)) -- NG
    
[/code]

の箇所を無理に正しく書こうとすると下記の感じだろうか？（そもそも`()`の中に`,`がある時点でタプルと解釈されると考えてしまってよさそうなので、タブルを受け取らないコンストラクタ付近に`(,)`を書いてるとおかしいと気づけそう）

**Foo.hs**

[code]

    data Tree = Empty
              | Leaf Int
              | Node Tree Tree deriving Show
             
    y = Node (Node Empty Empty) (Node Empty Empty)
    
    main = print $ y
    
[/code]

実行:

[code]

    % docker run -it --rm --name bar-haskell -v "$PWD":/tmp -w /tmp haskell:8 runghc Foo.hs
    
[/code]

出力結果:

[code]

    Node (Node Empty Empty) (Node Empty Empty)
    
[/code]

下記のようにすると部分適用（？）したNodeを２つ持てるのかと思ったがエラーになってしまった...

[code]

    data Tree = Empty
              | Leaf Int
              | Node Tree Tree deriving Show
             
    y = Node (Node Empty) (Node Empty)
    
    main = print $ y
    
[/code]

いまいち`（）`つけるタイミングと箇所がわからない。


CC BY-SA 4.0
2020-08-29T02:23:01.860
69957
2020-08-29T02:56:24.390
2020-08-29T02:56:24.390
9008
9008
69953
answer

[code]

    -- これは型エラー
    z = Node(Empty, Empty)
    
[/code]

この書き方をすると、`Node` コンストラクタに唯ひとつの引数としてタプル `(Empty, Empty)`
を渡しています。分かりやすいようにスペースを入れると、`z = Node (Empty, Empty)` となってしまっています。このため `Tree`
型の項が渡されるべきところに `(Tree, Tree)` 型（要素数 2 のタプルで、両方の要素の型が `Tree`
である型）の項が渡されているのでエラーになっています。

### 余談

今回使われている `Tree` 型では、`Node` コンストラクタと `Leaf`
コンストラクタで葉が値を持つノードのある木を表現しようとしている関係で、ノードの無い木が表現できません。この調整をとるため特別に `Empty`
コンストラクタを導入している訳です。しかしそうしてしまった結果、木としては意味のとれない項にも `Tree`
型がついてしまうようになってしまっています。`Node Empty Empty` のような項にも型がついてしまうのです。

このような不整合を防ぐためにはいくつか方法があります。たとえば表現が多少冗長になってしまいますが、ノードがある木とノードがない木を区別する方法など。


CC BY-SA 4.0
2020-08-29T03:27:27.753
69959
2020-08-29T03:27:27.753
19110
69953
answer