"Simultaneous" minimum and maximum of a list

Question

This function returns a 2-tuple with the minimum and the maximum of a list:

import Control.Arrow ((***), (>>>), (&&&))
import Data.Semigroup (getMin, getMax, Min(..), Max(..))

bounds :: (Bounded a, Ord a) => [a] -> (a,a)
bounds = foldMap (Min &&& Max) >>> getMin *** getMax

Example:

> x = [1..10 :: Int]
> bounds x
(1,10)

Is it more efficient than (minimum x, maximum x) ?

Or is there another way more efficient than (minimum x, maximum x) ?

Answer 1

First off, your two functions do not behave the same. (minimum xs, maximum xs) dies when xs is an empty list.

Is it more efficient than (minimum x, maximum x)?

They're both O(n), but the only way to answer questions like this is to benchmark them competitively. I think I'd expect the foldMap solution to be faster, as it makes only a single pass over the list, but let's find out.

import Control.Arrow ((***), (>>>), (&&&))
import Data.Semigroup (getMin, getMax, Min(..), Max(..))
import System.Random
import Criterion.Main

bounds1, bounds2 :: (Bounded a, Ord a) => [a] -> (a,a)
bounds1 = foldMap (Min &&& Max) >>> getMin *** getMax
bounds2 xs = (minimum xs, maximum xs)

randomList :: Int -> IO [Int]
randomList count = take count <$> randoms <$> newStdGen

mkBench n = env (randomList n) $ \list -> bgroup (show n) [
    bench "foldMap" $ nf bounds1 list,
    bench "minMax" $ nf bounds2 list
    ]

main = defaultMain $ map mkBench [100, 1000, 10000, 100000, 1000000]

Tabulated, that's

100/foldMap 1.411 μs
100/minMax 517.6 ns

1000/foldMap 28.94 μs
1000/minMax 5.078 μs

10000/foldMap 488.4 μs
10000/minMax 51.56 μs

100000/foldMap 21.08 ms
100000/minMax 537.3 μs

1000000/foldMap 268.9 ms
1000000/minMax 8.989 ms

So (minimum xs, maximum xs) turns out to be faster than the foldMap idea, across the board.