List.sortBy has serious performance issue

[jvoigtlaender]

Let's say I call List.sortBy f on a list of length 3, where the following is true:

• Computing f for any input is extremely expensive.

That List.sortBy is reduced to a call of JavaScript's sort function on arrays. I don't know what sorting algorithm JavaScript implementations use, but it doesn't really matter. What matters is that due to the way List.sortBy is currently reduced to JavaScript's sort, the following is true:

• Function f is called at least four times. (It might even be six times.)

Very bad! At least one time too many.

A better strategy would be (essentially, though in details this can be even further improved):

List.newSortBy f = List.map snd << List.oldSortBy fst << List.map (\a -> (f a,a))

This new code is guaranteed to induce only three calls of f for an input list of length 3.

Since I can make f arbitrarily expensive to compute on certain arguments, I can give calls of the current implementation of List.sortBy that are arbitrarily (even asymptotically) more expensive than the proposed alternative. (The converse is not true. The new implementation is guaranteed to not be asymptotically worse than the current implementation.)

[jvoigtlaender]

For comparison, see the Haskell standard library version of this function: https://hackage.haskell.org/package/base-4.8.1.0/docs/Data-List.html#v:sortOn

[jvoigtlaender]

For comparison, see the Haskell standard library version of this function: https://hackage.haskell.org/package/base-4.8.1.0/docs/Data-List.html#v:sortOn

[jvoigtlaender]

Replaced by pull request: https://github.com/elm-lang/core/pull/631.

[jvoigtlaender]

Replaced by pull request: https://github.com/elm-lang/core/pull/631.