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"