> Then I wrote about a dozen lines of Haskell to do the job--and running time turned out to be O(n^2).

Do you still have the code?

2012/6/1 Doug McIlroy <doug@cs.dartmouth.edu>
> > I love Haskell. It is my absolute favorite language.
> > But I have a very hard time finding places where I can actually use it!
>
> have you considered "your head" as such a place that should be easy to find.

An excellent reason.  Haskell shines unusually brightly on
applications that have an algebraic structure. Laziness
relieves a plethora of sequencing concerns.  I particularly
treasure one experience:

I asked a guru about the complexity of converting regular
expressions to finite-state automata without epsilon transitions
(state transitions that don't produce output).  The best he
knew was O(n^3), which is the cost of removing epsilon transitions
from arbitrary automata.  Then I wrote about a dozen lines of Haskell
to do the job--and running time turned out to be O(n^2). Once
I'd written the code, it became clear how to do it in other
languages, but I never would have found the theorem without
the help of Haskell.  (This without even bringing in the heavy
artillery of higher-order functions and monads.)

Doug McIlroy

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe