Depth-First search problems

[Paul Hudak]

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