some algorithms are hard to code in O(n) in Haskell
Ch. A. Herrmann
Thu, 25 Apr 2002 13:13:03 +0200
first of, you should consider whether you really need O(n).
Since you want to use Haskell, your aim is probably more
on elegance than on performance. Maybe, an Theta(n * log n) program
in Haskell would be easier to verify.
Surely, you can program in imperative style in Haskell achieving
optimal complexity, using arrays with destructive updates
(check the Glasgow extensions).
For some O(n) graph algorithms (like connected components),
there is an elegant optimal solution by John Launchbury:
"Graph algorithms with a functional flavour",
Springer Lecture Notes in Computer Science 925, pp. 308--331, 1995.