haskell - 二分木型の使用

Question

二分木を表すこの型宣言があります。

data Bst a = Empty | Node (Bst a) a (Bst a)

私は Haskell を初めて使用するので、使い方がわかりません。そのインスタンスのいくつかを初期化する方法を教えていただけますか?

Answer 1

単一の Int ノード:

    2

 Node Empty (2::Int) Empty

ツリー:

    2
   / \
  1   3

Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty) :: Bst Int


    2
   / \
  1   3
       \
        5

Node (Node Empty 1 Empty) 2 (Node Empty 3 (Node Empty 5 Empty)) :: Bst Int

Answer 2

あなたのデータ宣言は、Bstを構築する方法が2つあると述べています。EmptyコンストラクターまたはNodeコンストラクターを使用します。

-- An empty Bst
bst1 = Empty

-- A Bst containing a single value.
bst2 = Node Empty 42 Empty

-- A Bst containing 3 values, 2 at the root, 1 in the left child and 3 in the right child.
bst3 = Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty)

Answer 3

より慣用的な引数の順序を使用するために、宣言を少し書き直しますNode。

data Bst a = Empty | Node a (Bst a) (Bst a)

Emptyそして、Haskell がコンストラクターNodeと呼ぶものです。コンストラクターは、次の 2 つの方法で使用できます。

1. その型の値を構築する関数として。
2. 特殊なパターン マッチング構文のパターンとして、その型の値を分析および逆アセンブルします。

型をインタープリターにロードするghciと、ghci の:tコマンドを使用してコンストラクターの型を表示できます。

Ok, modules loaded: Main.
*Main> :t Empty
Empty :: Bst a
*Main> :t Node
Node :: a -> Bst a -> Bst a -> Bst a
*Main> 

はanyの型をEmpty持つ定数であり、は与えられた 3 つの引数 anと twoを生成する関数です。したがって、型の値を構築するには、コンストラクターの 1 つを使用し、必要な数の引数 ( の場合はなし、 の場合は3 つ) と正しい型を与えます。Bst aaNodeBst aaBst aEmptyNode

もう一度強調させてください:コンストラクターは、コンストラクターと同じ型の任意の式を使用できるのと同じ方法で使用できます。したがって、たとえば、Haskell で関数を部分的に適用できる (必要な引数よりも少ない引数に適用する) のと同じように、コンストラクターNode "foo" Emptyhas typeを部分的に適用できますBst String -> Bst String。