如何在Haskell中实现BST搜索

Question

我正在尝试理解这段代码:

search_bst :: Tree -> String -> Maybe Int 
search_bst Leaf _ = Nothing
search_bst (Node k v l r) sk =
    if sk == k then Just v
    else if sk < k then search_bst l sk
    else search_bst r sk

我可以得到这个概念但是Node k v l r意味着什么？这是否意味着search_bst需要两个参数,第一个是类型的实例Node并且有三个值？

Answer 1

Haskell语言的这个特性称为模式匹配.签名Tree -> String -> Maybe Int告诉您search_bst函数的第一个参数是类型Tree.该Tree数据类型可能是定义如下:

data Tree = Leaf | Node String Int Tree Tree

A Tree是a Leaf或a Node.甲Node还包含类型的4个字段String,Int.Tree和Tree.模式匹配现在允许您访问这些字段并拆分类型值Tree.在你的函数中,第一种情况:

search_bst Leaf _ = Nothing

意思是:如果search_bst给出Leaf第一个参数,任何东西作为第二个参数,则返回Nothing.

第二种情况:

search_bst (Node k v l r) sk =
  if sk == k then Just v
  else if sk < k then search_bst l sk
  else search_bst r sk

则表示:如果type的第一个参数Tree是a Node,则变量k,v,l和r将是Node构造函数的字段值.变量sk引用函数的第二个参数.

因此,如果你跑search_bst (Node "foo" 3 Leaf Leaf) "foo",那么首先,将尝试第一种情况.因为表达式Node "foo" 3 Leaf Leaf是a Node而不是a Leaf,所以第一种情况将失败.现在将尝试第二种情况,并且它匹配.所以k设置为"foo",v设置为3,lto Leaf,r也设置为Leaf.然后评估函数体.

您可以在本书的一章中学习更多关于函数定义的语法.了解大好的Haskell!