Hi! I hope you can help me with this little problem I have: I'm trying to implement a depth-first search on a binary tree from a school book but somehow I always get Haskell error messages (more after the source code). The source is as follows: -- 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 I really don't know how I can tell to see the right type. Does anyone have an idea what I have to change ? -- ciao dennis "I hear and I forget, I see and I remember, I do and I understand"
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
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"
participants (2)
-
Dennis Schieferdecker -
Paul Hudak