# Depth-First search problems

**Paul Hudak
**
paul.hudak@yale.edu

*Thu, 19 Sep 2002 10:35:21 -0400*

I'm not sure whether your program is correct, but it's easy to see why
you're getting the type error. You define p(_, k) = empty k, but empty
has type BinTree t -> Bool, so clearly p has type (a, BinTree t) ->
Bool. However, you use p in "until p f ([], Push CreateStack b)".
Since until has type (a -> Bool) -> (a -> a) -> a -> a, this implies
that p must have type ([a], Keller (BinTree t)) -> Bool. So you need to
either fix the definition of p or fix how it is used.
By the way, you are missing the case (Bin _ _ _) == EmptyTree in the
instance decl. Also, note that Keller t is isomorphic to [t], i.e. to
the list data type. Specifically, CreateStack is [], Push is (:), top
is head, and pop is tail.
Hope this helps, -Paul Hudak
>* -- Binary Tree structure
*>* data BinTree t = EmptyTree | Bin (BinTree t) t (BinTree t)
*>* left (Bin b1 _ _) = b1
*>* right (Bin _ _ b2) = b2
*>* value (Bin _ v _) = v
*>* empty EmptyTree = True
*>* empty (Bin _ _ _) = False
*>*
*>* -- Give the Binary Tree ==
*>* instance Eq a => Eq (BinTree a) where
*>* (Bin b v c) == (Bin d w e) = (v == w) && (b == d) && (c == e)
*>* EmptyTree == EmptyTree = True
*>* EmptyTree == Bin _ _ _ = False
*>*
*>* -- Stack structure
*>* data Keller t = CreateStack | Push (Keller t) t
*>* top (Push s x) = x
*>* pop (Push s x) = s
*>*
*>* -- Depth-First search
*>* tiefensuche b = fst (until p f ([], Push CreateStack b))
*>* where p(_, k) = empty k
*>* f(erg, k) | (top k) == EmptyTree = (erg, pop k)
*>* | otherwise = ([v] ++ erg, Push( Push( pop k) b2) b1)
*>* where (Bin b1 v b2) = top k
*>*
*>* The error message says that p has a wrong types
*>* Haskell thinks it is p :: (b, BinTree c) -> Bool, instead of p :: ([a],
*>* Keller (BinTree a)) -> Bool
*