Implementar marcha atrás en Haskell que se ejecuta en tiempo lineal

Question

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

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

pero parece que se ejecuta en O (n^2), mientras que el revés norma 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 reverso más rápido. Es bastante fácil de hacer en idiomas imperativos. Tal vez necesito algún material más avanzado de capítulos posteriores para hacer esto? Cualquier sugerencia es bienvenida.

Answer 1

Se puede implementar de manera eficiente utilizando un parámetro acumulador adicional, al igual que 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 lo que desea es saber cómo se hace en la biblioteca estándar, también puede look at the source code.

Answer 2

reverse se define en el Prelude.

Se puede implementar como:

reverse = foldl (flip (:)) [] 

Answer 3

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