Depth-First search problems

[Dennis Schieferdecker]

Paul Hudak wrote:

> 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

Thanks, that really helped.
My fault was that the depth-search algorithm expected an empty-method for the
stack not for the binary tree.

--
ciao
dennis

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