Arc Forumnew | comments | leaders | submitlogin
2 points by gregwebs 6104 days ago | link | parent

no need for bst-trav since there is an elements function. You can just map over the elements.

in the data declaration 'a' is a generic type, but Haskell will infer that the type must be an instance or class Ord (i.e. implement <,<=,>=,>,max,min,==). (If the type is not an instance of Ord it will tell you so at compile time)



2 points by pg 6104 days ago | link

no need for bst-trav since there is an elements function. You can just map over the elements

Mapping over elements is not the same if you're looking for the 4th element of a huge tree; which is probably what you have if you're using a bst.

-----

7 points by raymyers 6104 days ago | link

Actually yes, in Haskell it is the same. Lazy evaluation means you could take the 4th element of a map over an infinite list. For example: "map (*2) [1..] !! 4"

-----

2 points by rkts 6104 days ago | link

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 6104 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 6104 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 6104 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 6104 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 6104 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 6104 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 6104 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.

-----