Я только учу Хаскель, так что извините, если мой вопрос глупый. Я читаю 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
Итак, я начал думать, как быстрее реализовать свой собственный реверс. Это довольно легко сделать на императивных языках. Может быть, мне нужны более продвинутые материалы из последующих глав, чтобы сделать это? Любые намеки приветствуются.