haskell performance complexity-theory

Implementar el reverso en Haskell que corre en tiempo lineal.



performance complexity-theory (3)

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 .

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.


reverse se define en el Prelude .

Puedes implementarlo como:

reverse = foldl (flip (:)) []


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