Реализация обратного в Haskell, который работает за линейное время - PullRequest
18 голосов
/ 23 августа 2010

Я только учу Хаскель, так что извините, если мой вопрос глупый. Я читаю 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

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

Ответы [ 3 ]

24 голосов
/ 23 августа 2010

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

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

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

14 голосов
/ 23 августа 2010

reverse определено в Prelude .

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

reverse = foldl (flip (:)) []
7 голосов
/ 10 мая 2014
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
...