# Depth-First search problems

**Dennis Schieferdecker
**
shiin@gmx.de

*Thu, 19 Sep 2002 19:00:49 +0200*

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"