Implementar el reverso en Haskell que corre en tiempo lineal.

performance complexity-theory

Question

Solo estoy aprendiendo a Haskell, lo siento mucho si mi pregunta es estúpida. Estoy leyendo learnyouahaskell.com y ahora estoy en el capítulo 5 "Recursión". Hay un ejemplo de implementación de la función ''reversa'' estándar:

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

Pero parece que se ejecuta en tiempo O (N ^ 2), mientras que la reversa estándar se ejecuta en O (N) (eso espero). El siguiente código ilustra esto:

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

Entonces, comencé a pensar cómo implementar mi propio revés más rápido. Es bastante fácil de hacer en lenguajes imperativos. ¿Tal vez necesito más material avanzado de los capítulos posteriores para hacer esto? Cualquier sugerencia es bienvenida.

Answer 1

Se puede implementar de manera eficiente utilizando un parámetro acumulador adicional, como el segundo parámetro de fac en este ejemplo:

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

Si solo quiere saber cómo se hace en la biblioteca estándar, también puede consultar el código fuente .

Answer 2

reverse se define en el Prelude .

Puedes implementarlo como:

reverse = foldl (flip (:)) []

Answer 3

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