Depth-First search problems
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.
"I hear and I forget,
I see and I remember,
I do and I understand"