Monday, January 23, 2006

Loops Considered Harmful (personal reprise)

Paul Gearon posted a short rant on Java's verbosity and general clunkiness. The problem is to write a function that takes a string and returns a string containing the distinct characters of that string in sorted order. While Paul does provide a solution in java, he only alludes to the sort of function you might expect to write. So I thought I might have a go at the problem:

Assuming we have a string type, and a sorted-set in our standard library:

(lambda str (reverse-list->string
                (sorted-set-fold (compose cons flip) '()
                     (string-fold insert (sorted-set) str))))
Note: The reverse reduces the complexity from O(n^2 log m) to O(n log m)
3 lines. No mess, no fuss.

1 comment:

Paula said...

It's only "3 lines, no mess, no fuss" because you're using a more powerful language. You're also not having to live with library decisions made by others at a previous date! :-)