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：使用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并且Node是 Haskell 所称的构造函数。构造函数有两种使用方式：

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> 

Empty具有Bst aany类型的常量也是如此a，而Node生成Bst a给定三个参数的函数也是如此： ana和 two Bst a。因此，要构造该类型的值，您可以使用其中一个构造函数，为其提供所需数量的参数（在 的情况下为无，在 的情况下为Empty三个Node）和正确的类型。

让我再次强调这一点：您可以使用构造函数，就像使用与构造函数相同类型的任何表达式一样。因此，例如，就像您可以在 Haskell 中部分应用一个函数（将其应用到比它需要的更少的参数），您可以部分应用一个构造函数：Node "foo" Emptyhas type Bst String -> Bst String。