CODEWITHSUNDEEP
haskell
Aleksander Monk
Aleksander Monk

Reputation: 2907

haskell, bst - Inferred type is not general enough

I'm trying to write a program that will find element in a tree and return how many elements in the tree is < my element. 

data Bst a = Empty | Node (Bst a) a (Bst a)

lElems :: Ord a => a -> Bst a -> Int
lElems n t = (counto (findEl n 0 0 t) t)

counto :: Ord a => a -> Bst a -> Int
counto n Empty = 0
counto n (Node l m r)
        | m == n = counto n l
        | n > m =  1 + (counto n l) + (counto n r)
        | n < m = counto n l

findEl:: Ord a => a -> a -> a -> Bst a -> a
findEl n anc sta Empty = anc
findEl n anc sta (Node l m r) 
            | m == n = anc
            | n > m = if anc == sta || anc > m  then findEl n m sta r else findEl n anc sta r
            | n < m = if anc > m || anc == sta  then findEl n m sta l else findEl n anc sta r

counto and findEl are working good, but when I try to use them together I have this error Error

Here's my test tree

lElems 2 (Node (Node (Node Empty 1 (Node Empty 2 Empty)) 3 (Node Empty 5 (Node Empty 4 Empty))) 6 (Node (Node Empty 7 Empty) 8 (Node Empty 9 Empty)))

And I'd like to not change anything in data Bst definition

So, why a cant be Integer? And what's wrong in lElems?

|||EDIT|||

First 0 it's 0 which will be returned if there is no such element in the tree. Second 0 it's 0 to compare with first 0 and it's only one way how findEl work on my computer

However, if I change zeros to variables p and m ,and call lElems with zeros lElems 2 0 0 tree it works

Upvotes: 0

Views: 182

Answers (1)

sshine
sshine

Reputation: 16105

If you augment each subtree with the number of elements it contains,

data BinaryTree a = Empty | Node a Integer (BinaryTree a) (BinaryTree a)

insert :: Ord a => a -> BinaryTree a -> BinaryTree a
insert x Empty = Node x 1 Empty Empty
insert x (Node y n left right) =
  case x `compare` y of
    LT -> Node y (n+1) (insert x left) right
    GT -> Node y (n+1) left (insert x right)
    EQ -> Node y n left right

numElems :: BinaryTree a -> Integer
numElems Empty = 0
numElems (Node _ n _ _) = n

Then the number of elements less than an element (disregarding duplicates) is found more easily:

countLT :: Ord a => a -> BinaryTree a -> Integer
countLT x Empty = 0
countLT x (Node y n left right) =
  case x `compare` y of
    LT -> countLT x left
    GT -> 1 + numElems left + countLT x right
    EQ -> numElems left

E.g.

ghci> let t = insert 43 (insert 41 (insert 42 Empty))
ghci> map (\i -> countLT i t) [41,42,43,44]
[0,1,2,3]

Upvotes: 1

Related Questions