If you are using so many local variables that it is becoming a problem, you might need to reorganize. However, I would suggest declaring them all at the beginning and only losing one indentation level.
arc> (with (a 1 b nil) (= b a) b)
1
arc> b
Error: "reference to undefined identifier: _b"
Amen. Try to think more functionally. "On Lisp" is available on-line, see chapter 3. The funny thing is that one can achieve good functional style by making one's code look a certain way.
If these had good performance and were interchangable with the native lists of the language, this would be really cool. Sadly, I don't think lazy lists as a library can approach the usefulness of lazy lists as a language feature.
There have been some pretty good library attempts over the years though, like CL Heresy.
I also enjoy currying and "pointfree" style. However, wouldn't it require giving up functions that take an arbitrary number of arguments? (In fact Scala has both, but it required introducing a special syntax.)
I find that Arc's shortcut closure [] notation is a surprisingly good curry-substitute. For example:
(map (act w) locs-to-check) ; currying
(map [act w _] locs-to-check) ; only one token longer
there's something to that. i didn't really think about it, but that might just be fine. that's actually exactly what scala's explicit partial application looks like, with the underscore.
i honestly haven't been doing a whole lot of practical arc programming. CL and Slime have spoiled me to the point where I find it difficult to use a language that doesn't have that convenience
The line deriving(Eq,Show) means that you can now do this:
Prelude BST> Tree 'a' Empty Empty
Tree 'a' Empty Empty
Prelude BST> let a = Tree 'a' Empty Empty
Prelude BST> a
Tree 'a' Empty Empty
Prelude BST> let b = Tree 'b' Empty Empty
Prelude BST> b
Tree 'b' Empty Empty
Prelude BST> a == b
False
Prelude BST> let c = Tree 'c' a b
Prelude BST> let d = Tree 'c' a b
Prelude BST> c == d
True
All this is guaranteed at compile time. Moreover, the haskell version is much more readable. The use of modules removes unnecessary function prefixing, and there is no doubt about what the arguments to functions are when they are pattern matched.
Curiously, though, the arc version actually has less tokens by my measurement
but here is the interesting thing- now lets count just the unique tokens
bst.arc 41
bst.hs 47
This is in part due to haskell's pattern matching semantics where the same function definition is repeated multiple times, and the '|' character is repeatedly used. Also, there are more functions in the arc version, and in both pieces of code, variable names are usually one character and function names have multiple characters.
A more balanced tree will speed up 'find' and 'insert'. If those actions are performed far more often than 'remove', it would indeed be a good idea. Without knowing the use case, I cannot say which I would prefer.
It's fairly easy to do by hand. Just count the number of tokens-- in the sense of things whose first character a parser would not treat as merely another character in the name it was previously reading-- that are not closing delimiters of a pair.
If by that you mean counting the nodes, you need to parse the source first. You can either do it by hand (if you know the grammar) or tweak the compiler/interpreter, if it doesn't have any statistics option.
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)
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"
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.
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.
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.
