Post by @mildsunrise@tech.lgbt

is there any fold in Haskell that will balance the grouping so as to minimize depth? i.e. for 4 elements it'd do (a <> b) <> (c <> d)

0 Boosts

0 Likes

princess pancake :butterfly_::neofox_lesbian:

@natty@astolfo.social 8 hr. ago

@mildsunrise@tech.lgbt sounds a bit difficult on a linked list, if it doesn't know the length ahead of time

Maybe the source for quick sort would have one?

Verity :transHaskell::verifiedtransfem:

@monoidmusician@tech.lgbt 7 hr. ago

@natty @mildsunrise ohh right, it was in the sorting algorithms post:

https://apfelmus.nfshost.com/articles/quicksearch.html#message-1---mergesort

they just iteratively decimate the list until it is a singleton

apfelmus - Quicksort and k-th smallest elements

Finding the minimum element of a list can be implemented by first sorting the list and then taking the first element. Thanks to lazy evaluation, this is still efficient and takes time O(n)! We also discuss how this generalizes to finding the k-th smallest element.

Alba 🌸 :v_pat:

@mildsunrise@tech.lgbt 2 hr. ago

@monoidmusician @natty amusingly my monoid is also merge, but I am not trying to implement a mergesort (instead I have a bunch of equally long sorted lists that i need to merge into a single one)

Jamey Sharp

@jamey@toot.cat 33 min. ago

@mildsunrise @monoidmusician @natty I think you can do the same trick though? Merge adjacent pairs of lists, then merge adjacent pairs of the result of the first pass, and so on recursively.

That said, I wonder if it's any better to put all your lists into a priority queue ordered by the next element of each list? I learned that trick from the Python standard library and I dunno if it works as well when the data structure is immutable/persistent.