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 l = rev l []
where
rev [] a = a
rev (x:xs) a = rev xs (x:a)