Arc Forumnew | comments | leaders | submitlogin
2 points by raymyers 5886 days ago | link | parent

I think reasonable people can differ on this. Passing comparators as arguments is an approach more typical of dynamically-typed languages (e.g. CL and Scheme 'sort'). In a statically-typed language, it is more common to use a comparison operator that specializes on type (e.g. Haskell Prelude 'sort'). If a set of objects don't have a 'natural ordering', they might not belong in a Binary Search Tree in the first place.


3 points by pg 5886 days ago | link

What do you do if you want to maintain a list of strings sorted according to their length?

-----

4 points by raymyers 5886 days ago | link

If I wanted to keep using the Ord type-class for comparison, I might use a container type, like this:

    data Elem = Elem String deriving (Show, Eq)
    instance Ord Elem where
        Elem x < Elem y = length x < length y
    
    tree1 = insert (Elem "Some string") Empty
    tree2 = remove (Elem "Some string") tree1
If I really wanted to pass in the comparison function, I would have to change my code slightly. See: "A More Faithful Translation" (http://ray.codezen.org/wiki/doku.php?id=binary-search-tree).

-----