Arc Forumnew | comments | leaders | submitlogin
2 points by rkts 6159 days ago | link | parent

I would argue that relying on overloaded comparison functions is a bad idea. Not all things have a 'natural ordering,' and even for those that do you might want to override it at some point.


2 points by raymyers 6159 days ago | link

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 6159 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 6159 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).

-----

0 points by gregwebs 6159 days ago | link

You have just seen a bunch of code that gets the job done, whereas there is still an argument about whether the lisp code should be passed a comparison function. If you are going to make this argument you should show some actual code, because it is obvious from looking at this example which way is better.

-----

2 points by pg 6159 days ago | link

You have just seen a bunch of code that gets the job done,

It seems to me more that you have redefined the job to be what the code does.

-----

3 points by raymyers 6159 days ago | link

Or maybe we just interpreted the job as "a non-destructive binary search tree". Sorry if we misread the syllabus :)

-----

3 points by gregwebs 6159 days ago | link

Sorry, that comment doesn't sound nice and is dumb because I didn't realize what the previous commenter was getting at.

-----