Exhaustivity checking by tree coloring

Tree.hs

module Tree where

data Binder = Wildcard | Zero | Succ Binder deriving (Show)

data Tree = Covered | Uncovered | Branch Tree Tree

color :: Tree -> Binder -> Tree
color _            Wildcard = Covered
color Covered      _        = Covered
color Uncovered    Zero     = Branch Covered Uncovered
color Uncovered    (Succ b) = Branch Uncovered (color Uncovered b) 
color (Branch z s) Zero  = Branch Covered s
color (Branch z s) (Succ b)  = Branch z (color s b)

check :: [Binder] -> Bool
check = covered . foldl color Uncovered

covered :: Tree -> Bool
covered Covered = True
covered (Branch z s) = covered z && covered s
covered _ = False