On Saturday 12 February 2011 15:52:29, htc2011 wrote: > 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 )
You got the argument order wrong here, it should be tree-value-tree, but you wrote value-tree-tree on both right hand sides (that would mean that a and BST a are the same type, which would be an infinite type). > > 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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
