Haskell pattern matching with guards

Question

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’

Humdinger

Can you post the exact error? – Apospory

@DavOS Edited the error in. – Humdinger

Why are you trying to put the patterns in the guards? – Maffa

@Maffa So that I can return a certain value depending on the type and values in the pattern. Maybe I'm misunderstanding your question. – Humdinger

How would you not be able to do that if you skipped the guards and just pattern matched normally? The only use case for guards I see here would be to replace the if, but it doesn't look like you're trying to replace the if. – Maffa

"Is this not how you're supposed to do pattern matching in Haskell?" No. Guards are boolean expressions, not patterns. – Cleavland

@Cleavland Ah, that would explain why I hadn't found any such examples! Got it. – Humdinger

if A then False else B better written as not A && B. – Cleavland

Answer 1

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).

Cleavland

I have a case where I want to capture all the contents implicitly but still check the matching ADT constructor, such as toThing thing | Thing{} <- thing = thing. Any other way to capture all or some of the contents without being explicit? In my case, this is somewhat of an otherwise condition, but I'd still rather be explicit about the case. – Patti

Answer 2

As indicated in the comments, this is incorrect pattern matching. Here is one way to achieve what you seem to be looking for:

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

You also get another error by doing it the way you posted in the question:

* 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

This indicates that the expression inside the guard statements must be of type Bool but you are providing a Tree (either Null or Node).

Apospory

So this is what I turned it into but now it's still giving me the part of the error Not in scope: data constructor ‘Node’. However when I remove the isSmall function but leave the definitioon of the Tree (which contains Node) it compiles just fine. The definition of the Tree is actually in one file that is imported into my test file--could that be causing the problem? – Humdinger

@Humdinger Is there a module declaration in the file that defines Tree? If so, what does it look like? – Cleavland

module BinarySearchTrees( Tree(Null) , size, member, insert, toList, eq, treeMin, delete) where – Humdinger

I'm starting think I was misunderstanding how Node works. I thought that was a primitive Haskell type, but now I'm thinking it's made up inside the definition of Tree, therefore when I import Tree without importing Node, I don't have access to Node. Which seems strange because Node is part of the definition of Tree ... but I guess it is how it is. – Humdinger

@Humdinger Yeah, that says you want to export the Tree type and its Null data constructor, but not Node. You want either Tree(Null, Node) or Tree(..) there. – Cleavland