Check if the list is ascending (Haskell)

Question

I am writing a function to check if a tree if a BST. All I've tried is to print the tree in an in-order traversal to a list and then check if the list is increasing. However I am having this error:

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)

Here is what I have so far (only a checkList function).

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

Answer 1

You want:

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

When you tried to use [ ] in the final pattern, you were saying "match against a list that contains x:y:xs (also a list!) as its sole element". Which doesn't match the type [a].

Answer 2

A somewhat ugly one using foldl'

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

Note: Using head xs is OK here because of lazy evaluation.

Answer 3

The usual way to do this is to make your tree foldable:

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)

Then you can skip conversion to a list like this. This is similar to bmk's answer, but avoids 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

Warning! Warning!

The property this checks is weaker than the traditional binary search tree property, and weaker than the commonly accepted ways to weaken that property. In particular, you generally want to ensure, at least, that the root of each subtree is strictly greater than all elements of its left subtree, or that the root of each subtree is strictly less than all elements of its right subtree. These weak properties cannot be expressed in terms of the Foldable instance or conversion to a list; they must be checked directly. You can, however, use these techniques to verify the classical BST property by simply replacing <= with <.

---

A remark on space

All of the answers, including this one, have a somewhat unfortunate property: given a very left-heavy tree (e.g., Node (Node (...) 2 Leaf) 1 Leaf) they will use O(n) additional space to verify the search tree property. Is there some way to write this so it won't have any such bad cases? Unfortunately, the answer seems to be no. The classical BST property can be stated thus:

Each node must be greater than all elements of its left subtree and less than all elements of its right subtree.

The trouble is that "and". If we decide to check the left subtree first, we have to remember to check the right subtree afterwards, and vice versa.

Thus the only way to make verification efficient is to ensure that the tree is balanced.