haskell - "Simultaneous"列表的最小值和最大值

Question

此函数返回一个 2 元组，其中包含列表的最小值和最大值:

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

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

例子:

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

是否比 (minimum x, maximum x) 更有效？ ?

或者还有比 (minimum x, maximum x) 更有效的方法吗？ ?

Answer 1

首先，您的两个函数的行为不同。 (minimum xs, maximum xs)死于 xs是一个空列表。

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

它们都是 O(n)，但回答此类问题的唯一方法是对它们进行竞争性基准测试。我想我会期待 foldMap解决方案更快，因为它只通过列表一次，但让我们找出答案。

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]

制表，就是

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

所以 (minimum xs, maximum xs)结果比 foldMap 快想法，全面。