Binary Search Tree Haskell

Question

I have an insert function for a Binary Search Tree in Haskel. My insert functions first two lines look like this

insert :: (Ord a) => BST a -> a -> BST a
insert Nil x = Node x Nil Nil

I know the function works, I have tested it on single numbers. But now I am trying to apply the insert to a list. I tried this code

let mBST = foldr insert Nil [1,2,7,9,3,5]

and I get the following error

Occurs check: cannot construct the infinite type: a0 = BST a0
Expected type: BST (BST a0) -> BST a0 -> BST a0
Actual type: BST (BST a0) -> BST a0 -> BST (BST a0)
In the first argument of `foldr', namely `insert'
In the expression: foldr insert Nil [1, 2, 7, 9, ....]

I there is an error in the BST a -> a -> BST a but I am not sure how to fix it.

Charles Welton · Accepted Answer · 2015-02-13 05:03:10Z

4

foldr has type (a -> b -> b) -> b -> [a] -> b, which means it expects a function of type a -> b -> b as its first argument. In your particular example, that translates to Integer -> BST Integer -> BST Integer, which is different than insert's type.

The easiest solution would be to flip the insert function:

let mBST = foldr (flip insert) ...

answered Feb 13, 2015 at 5:03

Charles Welton

8617 silver badges14 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

dfeuer · Accepted Answer · 2015-02-13 05:03:47Z

2

The reason for this is that foldr f init lst passes f an element of the list and the result of folding up the rest of the list in that order. You can either write

insert :: (Ord a) => a -> BST a -> BST a
insert x Nil = Node x Nil Nil

(which would be more idiomatic) or write foldr (flip insert) Nil.

As you will probably learn soon, it's more efficient in cases like this to use a strict left fold instead of a right fold. Using your implementation, this is foldl' insert Nil. Using my (more idiomatic) one, this is foldl' (flip insert) Nil.

answered Feb 13, 2015 at 5:03

dfeuer

48.8k5 gold badges69 silver badges171 bronze badges

Collectives™ on Stack Overflow

Binary Search Tree Haskell

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related