[Haskell-cafe] Arrays performance

[Paolo Veronelli]

Quoting Udo Stenzel <u.stenzel at web.de>:
> paolo.veronelli at 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