> 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 <d...@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 >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe