Реализовать реверс в Хаскеле, который работает за линейное время
Я только изучаю Haskell, извините, если мой вопрос глупый. Я читаю learnyouahaskell.com и сейчас я нахожусь в главе 5 "Рекурсия". Есть пример реализации стандартной функции 'reverse':
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
Итак, я начал думать, как быстрее реализовать свой собственный реверс. Это' Это довольно легко сделать на императивных языках. Может быть, мне понадобится более продвинутый материал из последующих глав, чтобы сделать это? Любые намеки приветствуются.
2 ответа
Это может быть эффективно реализовано с использованием дополнительного параметра аккумулятора, такого как второй параметр fac в этом примере:
factorial n = fac n 1
where
fac 0 r = r
fac n r = fac (n-1) (r*n)
Если вы просто хотите знать, как это делается в стандартной библиотеке, вы также можете посмотрите исходный код .