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 _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
