Depth-First search problems

Dennis Schieferdecker
Thu, 19 Sep 2002 15:45:51 +0200

I hope you can help me with this little problem I have:
I'm trying to implement a depth-first search on a binary tree from a
school book but somehow I always get Haskell error messages (more after
the source code).

The source is as follows:

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

I really don't know how I can tell to see the right type. Does anyone
have an idea what I have to change ?

"I hear and I forget,
 I see and I remember,
 I do and I understand"