That's exactly the approach I was thinking of. Leaving off the `reverse` saves some time in cases where it's not required. Of course, there's also a perfectly reasonable version using foldr', in case the data structure leans the other way. One variation or another of this approach should be a decent constant factor faster than partially sorting the list. On Wed, Sep 26, 2018 at 11:03 AM, Viktor Dukhovni <ietf-dane@dukhovni.org> wrote:
On Sep 26, 2018, at 6:27 AM, Tom Ellis <tom-lists-haskell-cafe-2017@jaguarpaw.co.uk> wrote:
Actually what we want is more like
minimumsBy :: ... => (a -> a -> Ordering) -> t a -> [a]
There can be many distinct minimizers. For example when I want to get the collection of the youngest people from [(Age, Person)] I want
minimumsBy (compare `on` fst) [(12, alice), (15, balaji), (12, cho)]
to return
[(12, alice), (12, cho)]
It is a rather elementary function:
import Data.Foldable import Data.Ord
-- Stable version that keeps the input order for elements that are -- equal. If this were to be a library function, I'd drop the -- 'reverse' post-processing step, and leave the choice of stability -- to the caller. -- minimumsBy :: Foldable t => (a -> a -> Ordering) -> t a -> [a] minimumsBy cmp xs = reverse $ foldl' acc [] xs where acc [] x = [x] acc mins@(m:_) x = case cmp m x of LT -> mins EQ -> x:mins GT -> [x]
-- Viktor.
_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.