0

代数的データ型は木構造で表現されるとあるが、どのような構造になるのかよくわからない回答を受けて実際にコードを書いてみてよくわからないところが出たので別の質問として投稿します。

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

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

y = Node(Node(Empty), Node(Empty)) -- NG

箇所のエラーは

<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))

となりました。

z = Node(Empty, Empty) -- NG

箇所のエラーは

<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)

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

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

x = Node(Empty) -- OK

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

w = Empty -- OK

Haskellを書いているツールはあんまり関係ないと思いますが念の為記載します。‎Haskell on the Mac App Store で Haskellを書いています。

3
  • Node (Leaf 200) (Leaf 300) とパラレルなのは Node Empty Empty です(複数引数を食べさせるときにタプルを使う必要はない)…ので、その辺整理するとわかりやすいのではないでしょうか。
    – Yosh
    Commented 2020年8月29日 1:17
  • 1
    あー もしかして、関数呼び出し的な()とタプルを見間違えているのかも。そもそも関数呼び出し的な()はコンストラクタに書いたら駄目なんでしょうか。他の言語でいう Hoge.new() みたいな。 Commented 2020年8月29日 1:25
  • Haskell で () は関数呼び出しではないのです。Node (Leaf 200) (Leaf 300) にあるかっこは、結合の優先順位をつけるためです(ないと、 NodeLeaf200 を別々に引数にとる)。 Node (Empty) (Empty) は OK です。f () みたいなのがあったら、それは f を呼び出しているのではなく、f に引数として空タプル () を渡しているのです。map succ [1,2,3]map (succ, [1,2,3]) は異なります。
    – Yosh
    Commented 2020年8月29日 6:32

2 件の回答 2

2
-- これは型エラー
z = Node(Empty, Empty)

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

余談

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

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

0

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

z = Node(Empty, Empty) -- NG

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

(Empty, Empty)

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

Node Empty Empty

さて

x = Node(Empty) -- OK

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

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

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

y = Node(Node(Empty), Node(Empty)) -- NG

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

Foo.hs

data Tree = Empty
          | Leaf Int
          | Node Tree Tree deriving Show
         
y = Node (Node Empty Empty) (Node Empty Empty)

main = print $ y

実行:

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

出力結果:

Node (Node Empty Empty) (Node Empty Empty)

下記のようにすると部分適用(?)したNodeを2つ持てるのかと思ったがエラーになってしまった...

data Tree = Empty
          | Leaf Int
          | Node Tree Tree deriving Show
         
y = Node (Node Empty) (Node Empty)

main = print $ y

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

4
  • 取り急ぎ。 > つまり部分適用されている(というかデータ構造に部分適用あるのだろうか。この名称であっているのだろうか?)。 Node(Empty)はNode Emptyと同じ意味と考えられる。 ご認識のとおりです。 > というかデータ構造に部分適用あるのだろうか。この名称であっているのだろうか? はい、データ構造、というより正確にはデータコンストラクター(「値コンストラクター」と呼ばれることの方が多いです)が二つ以上の引数をとる場合、部分適用ができます。 > (そもそも()の中に,がある時点でタプルと解釈されると考えてしまってよさそうなので、タブルを受け取らないコンストラクタ付近に(,)を書いてるとおかしいと気づけそう これもご認識のとおりです。 Commented 2020年8月29日 3:08
  • すみません、コメントだとやっぱり回答しづらいので、別途気になる点として質問を新しく作っていただけないでしょうか? その後に整理すればこの回答は素晴らしいものになると思います。 Commented 2020年8月29日 3:09
  • @YujiYamamoto さん。ありがとうございます。なるほど、試して書いてる途中に次から次に気になることがでてきているので、切り出しにくいですね... "データ型に部分適用はあるのか?" みたいにかなり小さくして質問を別途新しく作っていったほうがよさそうでしょうか? Commented 2020年8月29日 3:19
  • あるいは、宣伝になってしまって恐縮ですが、Haskell-jpのSlack Workspace haskell.jp/signin-slack.html の #questionsチャンネルで質問いただけると、スレッドで回答できるのでこういう場合はやりやすいです。よければ切り替えていただけると! Commented 2020年8月29日 3:23

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

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