some algorithms are hard to code in O(n) in Haskell

[Ch. A. Herrmann]

Hi,

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.

Good luck
-- 
 Christoph Herrmann