CODEWITHSUNDEEP
haskellmax
jchitel
jchitel

Reputation: 3169

Haskell maximumBy for Ord instances

I keep finding myself wanting a function for this, and I always need to implement it myself, but I feel like there must be a built-in for it.

Basically, what I want is sort of halfway between maximum and maximumBy.

maximum takes a list of Ord values and returns the maximum. This is O(n).

maximum :: (Ord a) => [a] -> a

maximumBy takes a list of non-Ord values and a sort function that provides an ordering for them, and computes the maximum using that function. This is O(nlogn) (or whatever the complexity is for a sort).

maximumBy :: (a -> a -> Ordering) -> [a] -> a

I want a maximumBy that takes a list of values of type a and a function that returns Ord values for a values, and computes the maximum a using the Ord values. This would be O(n) because it only needs to keep track of the maximum as it goes along. This is what that signature would be:

maximumBy' :: (Ord b) => (a -> b) -> [a] -> a

And this is my rough implementation:

maximumBy' func list = foldl1' (\max i -> let (maxby, iby) = (func max, func i) in if iby > maxby then i else max) list

Is there such a function built-in, or perhaps an easy way to write this using existing built-ins?

Upvotes: 2

Views: 3882

Answers (4)

leftaroundabout
leftaroundabout

Reputation: 120741

That function is defined the tip-lib package as

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

The general idea has also been adopted in recent base, with

sortOn :: Ord b => (a -> b) -> [a] -> [a]

Note that thanks to laziness, you can use

maximumOn :: Ord b => (a -> b) -> [a] -> b
maximumOn f = head . sortOn f

and get the same asymptotic performance as a manual implementation.

Upvotes: 4

amalloy
amalloy

Reputation: 92117

I think what you are looking for is easily expressed using Data.Ord.comparing:

Instead of using your maximumBy' function:

maximumBy' head ["abc", "def", "geh"]

you can build a comparator with comparing and give that to the usual maximumBy:

maximumBy (comparing head) ["abc", "def", "geh"]

And as Willem Van Onsem says in another answer, you are incorrect to be concerned about the cost of maximumBy: it does not sort the list.

Upvotes: 5

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477264

First of all you make a claim that is wrong:

maximumBy takes a list of non-Ord values and a sort function that provides an ordering for them, and computes the maximum using that function. This is O(nlogn).

No sorting has to be done to calculate the maximum element. An ordering relation has to be reflexive, anti-symmetric and transitive, and therefore one can simply alsways hold the maximum thus far, and use the custom comparison to check whether the new item is greater.

Furthermore you can construct you maximumBy' function as:

maximumBy' f = maximumBy (compare `on` f)

Upvotes: 5

baxbaxwalanuksiwe
baxbaxwalanuksiwe

Reputation: 1494

I don't know any built-in function that does what you want, but you can really simplify your implementation of maximumBy'.

You could use on for example:

import Data.Function (on)

maximumBy' :: Ord b => (a -> b) -> [a] -> a
maximumBy' f = maximumBy (compare `on` f)

In fact, this definition is so simple you could use it as-is, without defining maximumBy' at all.

Upvotes: 1

Related Questions