如何提高此minmax实现的性能？

Question

这是我当前的代码。这是一个天真的实现。

import System.Environment (getArgs)

minmax [] = Nothing
minmax [x] = Just (x, x)
minmax (a:b:xs) = Just $ minmax' xs $ sort a b
    where minmax' [] lohi = lohi
          minmax' [x] lohi@(lo, hi)
            | x < lo = (x, hi)
            | x > hi = (lo, x)
            | otherwise = lohi
          minmax' (x:y:xs) (lo, hi) = minmax' xs $ newlo `seq` newhi `seq` (newlo, newhi)
              where (lo', hi') = sort x y
                    newlo = if lo' < lo then lo' else lo
                    newhi = if hi' > hi then hi' else hi

sort x y = if x < y then (x, y) else (y, x)

main = do
    args <- getArgs
    let [from, till] = map read args :: [Int]
    print $ minmax [from..till]

我想看看与c++ rust相比，我能用haskell走多远，也许还能在所有语言中使用三种方法。Naive、naive并行和使用矩阵(repa用于Haskell，eigen用于C++)

从这个分析器报告中，我看到Haskell分配了大量内存。

   minmax +RTS -p -RTS 1 10000000

total time  =        0.13 secs   (132 ticks @ 1000 us, 1 processor)
total alloc = 800,062,584 bytes  (excludes profiling overheads)

我是用ghc -O2 -fllvm (GHC8.2.1)编译的。在我看来，朴素的实现不应该分配太多的内存，因为它应该成对地迭代一个列表。如何实现这一点，我还能做些什么来提高性能？

我想试一下stream-fusion包，但它不支持base 4.10。有解决这个问题的方法吗？找不到有关此问题的任何内容。

Answer 1

可以在线性时间和常量空间中找到最小值和最大值，如下所示：

sort :: (Int, Int) -> Int -> (Int, Int)
sort (min, max) val
    | val < min = (val, max)
    | val > max = (min, val)
    | otherwise = (min, max)

minmax :: [Int] -> Maybe (Int, Int)
minmax []     = Nothing
minmax (x:xs) = Just $ foldl sort (x, x) xs

Haskell的严格性分析器应该知道这段代码必须是严格的，并对其进行优化。