¿Cuál es el algoritmo puramente funcional más eficiente para generar todos los prefijos de una lista?

Question

prefixes ls = zipWith take [1 .. length ls] (repeat ls) 

¿Hay alguna manera de hacerlo mejor que esto? Intuitivamente, me parece que uno no puede obtener un algoritmo por debajo de O (n²) en un lenguaje puramente funcional, ya sea porque invertir o agregar se debe aplicar n veces. Aunque no tengo idea de cómo probar esto.

Answer 1

Creo que tienes razón. No se puede compartir el lomo de la lista porque todas las colas son diferentes. Por lo tanto, la lista de prefijos, si se evaluara por completo, tomaría el espacio completo de(n), que debe tomar Ω (n) para generar.

Tenga en cuenta que (la versión más lenta) de la función que escribió está disponible en Data.List como inits.

Sin embargo, hay una buena optimización que puedes hacer. Esta ecuación es válida:

map (foldl f z) . inits = scanl f z 

Y scanl se ejecuta en tiempo lineal. Entonces, si puede expresar lo que desea hacer con cada prefijo como un doblez a la izquierda, entonces puede evitar la complejidad cuadrática de compilar la lista de prefijos.

Answer 2

¿No es dependiente de la representación? Si representa listas como almacenamiento contiguo más índice de inicio y final (similar a cadenas de bytes), puede compartir el almacenamiento y solo necesita recorrer una vez para compilar la lista de índices. El algoritmo no cambiaría, solo la representación. Para este caso de uso en particular, el uso de listas snoc (listas binarias, pero anidadas desde el final, no el inicio, de la lista) también permitiría compartir sublistas, ¿verdad?