Как я могу улучшить производительность этой реализации 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]

Я хочу увидеть, как далеко я могу пойти с haskell по сравнению с C++ rust и, возможно, используя три подхода на всех языках. Наивный, наивный параллель и использование матриц (repa для Хаскелла и 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 (GHC 8.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 должен выяснить, что этот код должен быть строгим, и оптимизировать его.