sortinghaskellfoldable

Is there such a thing as maximumWith?


Specifically I'm searching for a function 'maximumWith',

maximumWith :: (Foldable f, Ord b) => (a -> b) -> f a -> a

Which behaves in the following way:

maximumWith length [[1, 2], [0, 1, 3]] == [0, 1, 3]
maximumWith null [[(+), (*)], []] == []
maximumWith (const True) x == head x

My use case is picking the longest word in a list.
For this I'd like something akin to maximumWith length.

I'd thought such a thing existed, since sortWith etc. exist.


Solution

  • Let me collect all the notes in the comments together...

    Let's look at sort. There are 4 functions in the family:

    The first two have analogues in maximum: maximumBy and maximum. sortWith has no analogy; you may as well write out maximumBy (comparing _) every time. There is also no maximumOn, even though such a thing would be more efficient. The easiest way to define a maximumOn is probably just to copy sortOn:

    maximumOn :: (Functor f, Foldable f, Ord r) => (a -> r) -> f a -> a
    maximumOn rank = snd . maximumBy (comparing fst) . fmap annotate
      where annotate e = let r = rank e in r `seq` (r, e)
    

    There's a bit of interesting code in maximumBy that keeps this from optimizing properly on lists. It also works to use

    maximumOn :: (Foldable f, Ord r) => (a -> r) -> f a -> a
    maximumOn rank = snd . fromJust . foldl' max' Nothing
        where max' Nothing x = let r = rank x in r `seq` Just (r, x)
              max' old@(Just (ro, xo)) xn = let rn = rank xn
                                             in case ro `compare` rn of
                                                     LT -> Just (rn, xo)
                                                     _ -> old
    

    These pragmas may be useful:

    {-# SPECIALIZE maximumOn :: Ord r => (a -> r) -> [a] -> a #-}
    {-# SPECIALIZE maximumOn :: (a -> Int) -> [a] -> a #-}