# [Haskell-cafe] Beginner: (Another) Binary Search Tree Question

htc2011 jakobusbenne at gmail.com
Sat Feb 12 17:15:26 CET 2011

Ha, of course -- I feel stupid now hehe. Thanks very much! :-)

On 12 February 2011 15:06, Daniel Fischer [via Haskell] <
ml-node+3382792-1536654726-149885 at n5.nabble.com> wrote:

> 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
>
>
> _______________________________________________
> [hidden email] <http://user/SendEmail.jtp?type=node&node=3382792&i=0>
>
>
> ------------------------------
> below:
>
>  To unsubscribe from Beginner: (Another) Binary Search Tree Question, click