Search code examples
haskellpattern-matchingguard-clause

Haskell pattern matching with guards

Suppose I want to model a tree structure in Haskell with 

data Tree = Null | Node Tree Integer Tree deriving Show

and I'd like to test if every entry is, say, less than 10. I thought I would use pattern matching and write 

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

However it gives errors about a, b, and c being out of scope. I would have thought putting them in the guards would basically put them in the scope. Is this not how you're supposed to do pattern matching in Haskell? I've looked around for examples that would guide me but I haven't found any examples of pattern matching in guards that uses a data structure composed of several other data structures.

The error:

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’
Solution

  • Is this not how you're supposed to do pattern matching in Haskell?

    No. Guards are boolean expressions, not patterns.

    You can do pattern matching like this:

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

    ... or like this:

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

    ... or even like this:

    {-# LANGUAGE LambdaCase #-}

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

    (using the LambdaCase language extension). This is perhaps closest to your original attempt.

    That said, it is possible to embed patterns in guards by using <-. This is known as "pattern guards":

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

    However, this syntax doesn't buy you much here. You still have to give the argument a name (x in this case) and you have to explicitly say <- x everywhere. It would be clearer to use pattern matching directly (using case or multiple function equations).