Quoting Udo Stenzel <[EMAIL PROTECTED]>: > [EMAIL PROTECTED] wrote: > > It isn't, but not for the reasons you might suspect. You're using > 'nub', which is quadratic, and your 'coupage' is also quadratic because > it uses 'lookup' on a list, which is linear, a linear number of times. > You can get this down to O(n * log n) if you replace these lists by > Data.Map and Data.Set, to get down to O(n) you need arrays there, too, > but that would be pointless, because you're also using 'sort', which is > already in O(n * log n). The core of the algorithm is clearly linear in > the length of its input. > > (Btw, putting 'devil' into a state monad doesn't make much sense. I > think, ordinary recursion would be more clear. In fact, it's a > 'foldl'.)
Ok, I've simplified some code and moved to foldl, to collect the result. I paste new version in case you care give me some moe suggestion. Thanks. Paolino _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
