Use an index instead of uncons to make array functions more efficient.

[jutaro]

The implementation of many array functions, like filterM, span, groupBy, ... uses uncons for implementation. It would be more efficient to use an index and has no known disadvantages (other then maybe some subjective aesthetic property).

If we can agree on this I can contribute code, but I don't want to work on this if it is not wanted.

[paf31]

Let's list out the functions which have possible issues, since I think each could have a slightly different fix.

filterM - I'm not sure how you could make this more efficient for a general Monad.

span and groupBy could potentially make use of STArray. Something like discrimination is probably worth investigating for sorting and grouping too.

[hdgarrood]

I think converting to a list before doing filterM and then converting back to an Array at the end would be better than the current implementation; right now it's at least O(n^2) I think.

[hdgarrood]

Mostly a note to myself: now, it's just groupBy, nubBy, unzip, and foldM that use uncons (and perhaps shouldn't).

[hdgarrood]

groupBy is now done, so I'll make a checklist for the remaining ones:

• nubBy (now called nubByEq in the 0.12 branch)
• unzip
• foldM

[matthewleon]

how about having foldM just be a re-export?

[hdgarrood]

That sounds good to me, provided that the Foldable version has better performance than the current foldM — which is almost certainly true but probably still worth checking, at least for one or two monads.

[hdgarrood]

nubByEq was the last problematic one, so I'm going to close this, but of course please continue to open issues if you find places where performance could be improved.