Arc Forumnew | comments | leaders | submitlogin
4 points by lojic 5887 days ago | link | parent

Very nice - thanks!

  Haskel:
  36 total lines; 1,167 chars
  Arc:
  53 total lines; 1,215 chars
I don't know the formula for a "code tree".


4 points by gregwebs 5887 days ago | link

This doesn't tell the whole story. The haskell version is doing some balancing. For an AVL tree with rotations implemented through pattern matching see here. http://www.nabble.com/Re%3A-Why-functional-programming-matte...

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

  ruby -e 'p File.read(ARGV[0]).split(/\s|\.|!/).reject{|s| s==""}.map{|tok| tok.gsub(/\(|\)/,"")}.flatten.uniq.size'

  bst.arc 205
  bst.hs  253
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.

-----

2 points by rkts 5886 days ago | link

> The haskell version is doing some balancing.

Balancing that causes remove to be O(n). Probably not a good idea.

-----

2 points by raymyers 5886 days ago | link

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.

-----

3 points by pg 5887 days ago | link

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.

-----

2 points by vrk 5887 days ago | link

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.

-----