[Haskell-cafe] Beginner: (Another) Binary Search Tree Question
htc2011
jakobusbenne at gmail.com
Sat Feb 12 15:52:29 CET 2011
Hi all,
I just started learning Haskell but am having some trouble getting the
insertion into a binary search tree to
work and was hoping that somebody could advise me on a possible solution.
Thanks.
Given the data type definition of the tree to be:
Code:
data Ord a => BST a = EmptyBST | Node ( BST a ) a ( BST a ) deriving
(Show,
Eq)
And the insertion function to be:
Code:
insert v EmptyBST = Node EmptyBST v EmptyBST
insert v (Node b a c)
| v<= a = Node a ( insert v b ) c
| otherwise = Node a b ( insert v c )
GHCI keeps telling me that I 'cannot construct an infinite type':
' Occurs check: cannot construct the infinite type: a = BST (BST a)
Expected type: BST a -> BST (BST a) -> a
Inferred type: BST a -> BST (BST a) -> BST (BST a)
In the second argument of `Node', namely `(insert v b)'
In the expression: Node a (insert v b) c'
Upon adding the following signature:
Code:
insert :: Ord a => a -> BST a -> BST a
I get: Occurs check: cannot construct the infinite type.
Sorry, but I'm quite lost. Any thoughts?
Thanks.
Benjamin
--
View this message in context: http://haskell.1045720.n5.nabble.com/Beginner-Another-Binary-Search-Tree-Question-tp3382773p3382773.html
Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
More information about the Haskell-Cafe
mailing list