CODEWITHSUNDEEP
haskellbinary-search-tree
Jan Drozen
Jan Drozen

Reputation: 984

Binary search tree in haskell, comparsion

I have problem with BST in Haskell. I guess I've problem with defining the "key" variable in Node(Uzel) to be Ord. But I absolutely don't have any idea more.

I though, if I once defined the "key" argument for the Tree type as Ord, it is valid and every use in code will get this information too.

Following code is not complete, but there is the thing I'm talking about:

data (Ord key) => Tree key value = List key value |Uzel (Tree key value) key value (Tree key value) | Null deriving (Show)

prazdny :: Ord key => Tree key value
prazdny = Null

najdi :: (Ord key,Ord k) => k -> Tree key value -> Maybe a
najdi k Null = Nothing
najdi k (Uzel levy klic hodnota pravy) = if k < klic
                then najdi k levy
                else najdi k pravy

When trying to compile i get this:

bvs.hs:9:49:
Could not deduce (key ~ k)
from the context (Ord key, Ord k)
  bound by the type signature for
             najdi :: (Ord key, Ord k) => k -> Tree key value -> Maybe a
  at bvs.hs:(8,1)-(11,58)
  `key' is a rigid type variable bound by
        the type signature for
          najdi :: (Ord key, Ord k) => k -> Tree key value -> Maybe a
        at bvs.hs:8:1
  `k' is a rigid type variable bound by
      the type signature for
        najdi :: (Ord key, Ord k) => k -> Tree key value -> Maybe a
      at bvs.hs:8:1
In the second argument of `(<)', namely `klic'
In the expression: k < klic
In the expression: if k < klic then najdi k levy else najdi k pravy

Lot of thanks for any idea!!

Upvotes: 0

Views: 377

Answers (2)

Gabriella Gonzalez
Gabriella Gonzalez

Reputation: 35089

The problem is that k and key must be the same type in order to compare them, but you declare them to possibly be different, so the compiler complains. If you make them the same type it will type check.

Upvotes: 2

ja.
ja.

Reputation: 4249

comment out this line and it'll compile:

--najdi :: (Ord key,Ord k) => k -> Tree key value -> Maybe a

Upvotes: 0

Related Questions