Haskell模式匹配与守卫

Question

假设我想在Haskell中建模一棵树形结构。

data Tree = Null | Node Tree Integer Tree deriving Show

我希望测试每个条目是否小于10，我想使用模式匹配并编写

isSmall :: Tree -> Bool
isSmall _ 
  | Null = True
  | (Node a b c) = if b >= 10
                   then False
                   else isSmall a && isSmall c

然而，它会报错说 a、b 和 c 超出了范围。我本以为在 guard 中将它们放入作用域基本上就可以了。这不是 Haskell 中模式匹配的正确用法吗？我查看了一些可供参考的示例，但没有发现使用由几个其他数据结构组成的数据结构进行 guard 中的模式匹配的例子。

错误信息：

test.hs:24:6: Not in scope: data constructor ‘Node’

test.hs:24:11: Not in scope: ‘a’

test.hs:24:13: Not in scope: ‘b’

test.hs:24:15: Not in scope: ‘c’

test.hs:24:27: Not in scope: ‘b’

test.hs:26:38: Not in scope: ‘a’

test.hs:26:57: Not in scope: ‘c’

- Addem

---

你能发布一下具体的错误信息吗？ - dopamane

@DavOS 修改了错误。 - Addem

你为什么试图将模式放在卫兵中？ - sepp2k

“这不是在Haskell中进行模式匹配的正确方式吗？” 不是。卫语句是布尔表达式，而不是模式。 - melpomene

if A then False else B 更好地写作 not A && B。 - melpomene

Answer 1

这不是在Haskell中进行模式匹配的正确方式吗？ 不是。Guard是布尔表达式，而不是模式。 你可以像这样进行模式匹配：

isSmall :: Tree -> Bool
isSmall Null = True
isSmall (Node a b c) = b < 10 && isSmall a && isSmall c

...或者像这样：

isSmall :: Tree -> Bool
isSmall x = case x of
  Null -> True
  Node a b c -> b < 10 && isSmall a && isSmall c

...或者像这样：

{-# LANGUAGE LambdaCase #-}

isSmall :: Tree -> Bool
isSmall = \case
  Null -> True
  Node a b c -> b < 10 && isSmall a && isSmall c

（使用LambdaCase语言扩展）。这可能是最接近您最初尝试的方法。

话虽如此，可以通过使用<-在守卫中嵌入模式。这被称为“模式守卫”。

isSmall :: Tree -> Bool
isSmall x 
  | Null <- x = True
  | Node a b c <- x = b < 10 && isSmall a && isSmall c

然而，在这里，这种语法并没有太多的帮助。你仍然需要给参数一个名称（在本例中为x），并且你必须明确地在每个地方写出<- x。更清晰的方法是直接使用模式匹配（使用case或多个函数方程）。

- melpomene

---

我有一个情况，我想隐式地捕获所有内容，但仍然检查匹配的 ADT 构造函数，例如 toThing thing | Thing{} <- thing = thing。是否有其他方法可以捕获所有或部分内容而不必明确指定？在我的情况下，这有点像“否则”条件，但我仍然更愿意明确说明情况。 - Tom Palmer

Answer 2

正如评论中所指出的，这是错误的模式匹配。以下是一种实现您似乎正在寻找的方法：

isSmall :: Tree -> Bool
isSmall Null         = True
isSmall (Node a b c) = if b >= 10
                       then False
                       else isSmall a && isSmall c

你在问题中所提及的方法也会导致另一个错误：

* Couldn't match expected type `Bool' with actual type `Tree'
* In the expression: (Node a b c)
  In a stmt of a pattern guard for
                 an equation for `isSmall':
    (Node a b c)
  In an equation for `isSmall':
      isSmall _
        | Null = True
        | (Node a b c) = if b >= 10 then False else isSmall a && isSmall c

这表示在守卫语句中的表达式必须是Bool类型，但您提供了一个Tree（Null或Node）。

- dopamane

---

所以这就是我转换后的代码，但现在它仍然给出了错误的一部分：“Not in scope: data constructor ‘Node’”。然而，当我删除isSmall函数但保留Tree的定义（其中包含Node）时，它可以编译通过。Tree的定义实际上在一个文件中，该文件被导入到我的“test”文件中 - 这可能会引起问题吗？ - Addem

@Addem 文件中是否有定义“Tree”的“module”声明？如果有，它是什么样子的？ - melpomene

module BinarySearchTrees( Tree(Null) , size, member, insert, toList, eq, treeMin, delete) where - Addem

我开始觉得我误解了 Node 的工作方式。我以为它是 Haskell 的原始类型，但现在我认为它是在 Tree 的定义内部构建的，因此当我导入 Tree 而没有导入 Node 时，我就无法访问 Node。这似乎很奇怪，因为 Node 是 Tree 定义的一部分...但我想这就是它的工作方式。 - Addem

是的，这意味着你想要导出Tree类型及其Null数据构造器，但不包括Node。你需要在那里使用Tree(Null, Node)或Tree(..)。 - melpomene