检查列表是否升序排列（Haskell）

Question

我正在编写一个函数来检查一棵树是否为BST。我尝试的方法是将树按中序遍历打印到列表中，然后检查列表是否递增。然而我遇到了这个错误：

Couldn't match expected type `a' against inferred type `[t]'
  `a' is a rigid type variable bound by
      the type signature for `checkList' at BST.hs:24:18
In the pattern: x : y : xs
In the pattern: [x : y : xs]
In the definition of `checkList':
    checkList [x : y : xs] = x <= y && checkList (y : xs)

下面是我目前的代码（只有一个checkList函数）。

checkList :: (Ord a) => [a] -> Bool
checkList [] = True
checkList [x] = True
checkList [x:y:xs] = x <= y && checkList (y:xs)

- Walle

---

相关链接：http://stackoverflow.com/questions/28389008/haskell-non-exhaustive-pattern-checking-if-list-is-ascending - jub0bs

Answer 1

你想要：

checkList :: (Ord a) => [a] -> Bool
checkList [] = True
checkList [x] = True
checkList (x:y:xs) = x <= y && checkList (y:xs)

当您尝试在最终模式中使用[ ]时，您是在说“匹配包含x：y：xs（也是列表！）作为其唯一元素的列表”。这与类型[a]不匹配。

- Jay Kominek

---

一个简短的版本：checkList xs = and $ zipWith (<=) xs $ drop 1 xs。意思是检查列表xs是否是按顺序排列的。 - bheklilr

谢谢大家，那是一个愚蠢的错误。 - Walle

@Walle，请在答案对您有帮助时接受它。 - awesoon

@bheklilr，为什么不直接使用tail xs而非drop 1 xs呢？ - awesoon

我原则上避免使用tail函数，如果我从不使用它，那么我就永远不会被它咬伤。在这种情况下它可以工作，但有很多情况下它并不是很有效。这就像我们为什么要使用模式匹配而不是使用head和其他部分函数一样。 - bheklilr

Answer 2

通常的做法是使您的树可折叠：

data BST a = Node (BST a) a (BST a) | Leaf

-- Use `deriving Foldable` or this instance
instance Foldable BST where
  foldMap _ Leaf = mempty
  foldMap f (Node l v r) =
    foldMap f l <> (f v <> foldMap f r)

那么你可以像这样跳过转换为列表。这类似于bmk的答案，但避免使用head标签。

-- Is this increasing? If so, what is the maximum?
data Result a = Empty | NotInc | Inc a

finalInc :: Result a -> Bool
finalInc NotInc = False
finalInc _ = True 

increasing :: (Foldable f, Ord a) => f a -> Bool
increasing = finalInc . foldl' go Empty where
  go Empty y = Inc y
  go NotInc _ = NotInc
  go (Inc x) y
    | x <= y = Inc y
    | otherwise = NotInc

警告！

此检查的属性比传统的二叉搜索树属性弱，也比通常接受的弱化该属性的方法要弱。特别是，通常您至少希望确保每个子树的根节点严格大于其左子树的所有元素，或者每个子树的根节点严格小于其右子树的所有元素。这些弱属性不能用Foldable实例或转换为列表来表示；它们必须直接检查。但是，您可以通过将<=替换为<来使用这些技术来验证经典的BST属性。

---

关于空间的说明

所有答案（包括本答案）都有一个不幸的特点：对于非常左重的树（例如，Node (Node (...) 2 Leaf) 1 Leaf），它们将使用O(n)的额外空间来验证搜索树属性。有没有什么办法可以写成不会有这样糟糕情况的形式呢？不幸的是，答案似乎是否定的。经典的BST属性可以这样陈述：

每个节点必须大于其左子树的所有元素并小于其右子树的所有元素。

问题在于“和”。如果我们决定先检查左子树，那么我们必须记得之后检查右子树，反之亦然。

因此，使验证高效的唯一方法是确保树是平衡的。

- dfeuer

Answer 3

使用 foldl' 的代码有些丑陋

checkList :: Ord a => [a] -> Bool
checkList xs = fst $ foldl' (\(b,x1) x2 -> (b && x1 <= x2,x2)) (True,head xs) xs

注意：由于惰性求值，这里使用 head xs 是可行的。

- bmk

---

我认为你也可能存在潜在的空间泄漏问题，因为你只强制使用了一对构造器，而没有使用其中的 Bool。 - dfeuer