haskell - 尝试实现二叉树搜索

Question

我正在尝试在 haskell 中实现二叉树搜索算法。

data BinTree k d = 
   Branch (BinTree k d) (BinTree k d) k d 
  | Leaf k d 
  | Empty
  deriving (Eq, Show)

是我用来捕获二叉树的数据结构。问题是如果找不到值，我不知道该返回什么。这是我到目前为止的搜索功能:

lkp :: (Monad m, Ord k) => BinTree k d -> k -> m d
lkp (Leaf a b) x
  | a == x = return(b)
lkp (Branch lSub rSub a b) x
  | a < x = lkp rSub x
  | a > x = lkp lSub x
  | a == x = return(b)

我可以在测试中看到测试需要 [] 的返回值，但我不明白我们如何返回这个空值。这是其中一项测试的示例:

testCase "3 in Leaf 5 500 ([]))[1 mark]"
    (lkp (Leaf 5 500) 3 @?= [] ) 

Answer 1

因此我们错过了返回“零”或“空”值的方法。

幸运的是，Haskell 基础库(Prelude)提供了 MonadPlus类(class)。 MonadPlus 是 Monad 的一个特殊版本，它使用 mzero 和 mplus 增强了常规 Monad 接口(interface)，本质上提供了一个类似幺半群的结构。理论here on the Haskell Wiki .

使用MonadPlus，lkp的代码可以这样写:

import Control.Monad

data BinTree k d = 
       Branch (BinTree k d) (BinTree k d) k d 
    |  Leaf k d 
    |  Empty
  deriving (Eq, Show)

lkp :: (MonadPlus m, Ord k) => BinTree k d -> k -> m d
lkp (Branch lSub rSub a b) x
  | a < x      =  lkp rSub x
  | a > x      =  lkp lSub x
  | otherwise  =  return b
lkp (Leaf a b) x  =  if (a == x)  then  (return b)  else  mzero
lkp Empty      _  =  mzero

注意::我使用 otherwise 关键字而不是相等性测试来消​​除虚假的“非详尽模式”警告。

在ghci下测试:

 λ> 
 λ> :load q65169028.hs
[1 of 1] Compiling Main             ( q65169028.hs, interpreted )
Ok, one module loaded.
 λ> 
 λ> tr1 = Branch (Leaf 1 2) (Branch (Leaf 5 6) (Branch (Leaf 9 10) (Leaf 17 18) 13 14) 7 8) 3 4
 λ> 
 λ> (lkp tr1 7) :: [Int]
[8]
 λ> 
 λ> (lkp tr1 8) :: [Int]
[]
 λ> 
 λ> (lkp tr1 17) :: [Int]
[18]
 λ> 

我们想强制解释器选择列表作为我们的 MonadPlus 实例，因此 ::[Int] 类型签名在每行的末尾。

如果这听起来太麻烦，总是可以进一步专门化 lkp 函数，如下所示:

llkp :: Ord k => BinTree k d -> k -> [d]
llkp tr x = lkp tr x