Внедрить реверс в Haskell, который работает в линейном времени

Я просто изучаю Хаскелл, извините, если мой вопрос глуп. Я читаю learnyouahaskell.com, и теперь я нахожусь в главе 5 "Рекурсия". Вот пример реализации стандартной "обратной" функции:

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]

Но кажется, что он работает в O (N ^ 2) времени, тогда как стандартный обратный ход выполняется в O (N) (надеюсь, так). Следующий код иллюстрирует это:

sum (reverse [1,2..1000000]) -- runs pretty fast
sum (reverse' [1,2..1000000]) -- never finishes

Итак, я начал думать, как быстрее реализовать свой собственный обратный ход. Это довольно легко сделать на императивных языках. Может быть, мне понадобится более продвинутый материал из последующих глав, чтобы сделать это? Любые подсказки приветствуются.

Ответ 1

Он может быть эффективно реализован с использованием дополнительного параметра аккумулятора, такого как второй параметр fac в этом примере:

factorial n = fac n 1
  where
    fac 0 r = r
    fac n r = fac (n-1) (r*n)

Если вы просто хотите знать, как это делается в стандартной библиотеке, вы также можете посмотреть исходный код.

Ответ 2

reverse определяется в Prelude.

Вы можете реализовать его как:

reverse = foldl (flip (:)) []

Ответ 3

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)