Quoting Udo Stenzel
paolo.veronelli@gmail.com 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