I've been curious in the past why Data.List.partition has not found a more generic implementation. I always assumed this was because of performance. I've given the performance hypothesis a test and it seems that a generic implementation outperforms the list implementation. I'm not terribly sure why this is the case, but I also haven't dumped core. Implementation and bench: https://github.com/eborden/partition Should this function be made generic? This implementation is surely leveraging the perf characteristics of the Monoid instance of List. Other types could have terrible performance. - Evan
On Thu, 20 Oct 2016, evan@evan-borden.com wrote:
I've given the performance hypothesis a test and it seems that a generic implementation outperforms the list implementation. I'm not terribly sure why this is the case, but I also haven't dumped core.
Implementation and bench: https://github.com/eborden/partition
I do not propose to add this to 'base', but if you are after a generic implementation why is the input container type the same as the output type (both 't')? Why not using Alternative.<|> instead of Monoid.<> ?
I'm not sure I propose adding it to base either :) Relaxing `t` as the output is certainly correct. I'm not sure if there is a correct choice between Alternative or Monoid. That would be an indicator that a generic function of this form is arbitrarily opinionated. On Thu, Oct 20, 2016 at 3:18 PM, Henning Thielemann < lemming@henning-thielemann.de> wrote:
On Thu, 20 Oct 2016, evan@evan-borden.com wrote:
I've given the performance hypothesis a test and it seems that a generic
implementation outperforms the list implementation. I'm not terribly sure why this is the case, but I also haven't dumped core.
Implementation and bench: https://github.com/eborden/partition
I do not propose to add this to 'base', but if you are after a generic implementation why is the input container type the same as the output type (both 't')? Why not using Alternative.<|> instead of Monoid.<> ?
Wild guessing: This seems fairly likely to relate somehow to the potential space leak in certain "optimized" compilations of partition (where the GC can't see and reduce selector application). Your Foldable version may benefit in some cases by not being inlined and therefore not getting the problematic optimization. I don't really know for sure. What is clear is that the GC trick isn't as reliable as one might hope, given its performance. On Oct 20, 2016 3:41 PM, "evan@evan-borden.com" < evan@evanrutledgeborden.dreamhosters.com> wrote:
I'm not sure I propose adding it to base either :)
Relaxing `t` as the output is certainly correct. I'm not sure if there is a correct choice between Alternative or Monoid. That would be an indicator that a generic function of this form is arbitrarily opinionated.
On Thu, Oct 20, 2016 at 3:18 PM, Henning Thielemann < lemming@henning-thielemann.de> wrote:
On Thu, 20 Oct 2016, evan@evan-borden.com wrote:
I've given the performance hypothesis a test and it seems that a generic
implementation outperforms the list implementation. I'm not terribly sure why this is the case, but I also haven't dumped core.
Implementation and bench: https://github.com/eborden/partition
I do not propose to add this to 'base', but if you are after a generic implementation why is the input container type the same as the output type (both 't')? Why not using Alternative.<|> instead of Monoid.<> ?
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
participants (3)
-
David Feuer -
evan＠evan-borden.com -
Henning Thielemann