Tengo curiosidad por si hay alguna (solo polimórfica de primer orden) optimizaciones con pliegues.Optimizaciones con pliegues
Para mapas, hay deforestación: map g (map f ls) => map (g . f) ls y rev (map f ls) => rev_map f ls (más rápido en Ocaml).
Pero doblar es tan poderoso que parece desafiar cualquier optimización.
las obvias:
fold_left f acc (List.map g li) => fold_left (fun acc x -> f acc (g x)) acc li
fold_right f li acc => fold_left f acc li (* if (f,acc) is a monoid *)
usted puede estar interesado en el artículo clásico sobre el tema, "programación funcional con plátanos, lentes, Sobres y alambre de púas". Sin embargo, ten en cuenta que es técnico y tiene una notación impenetrable.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125
Editar: mi primera versión de la primera regla que estaba mal, editado gracias a Vincent-hugot.
Puede utilizar la deforestación en pliegues. De hecho, la fusión map/map es un caso especial de eso.
El truco consiste en reemplazar la construcción de la lista por una especial build función:
build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []
Ahora, usando la definición estándar de foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr c n [] = n
foldr c n (x:xs) = c x (foldr c n xs)
Tenemos la siguiente equivalencia:
foldr c n (build g) == g c n
(En realidad esto solo es cierto bajo ciertos , pero común, las circunstancias. Para detalles, ver "Correctness of short-cut fusion").
Si escribe su lista produciendo funciones (incluyendo map) usando build y sus consumidores usando foldr, entonces la igualdad anterior puede eliminar la mayoría de las listas intermedias. Las comprensiones de la lista de Haskell se traducen en combinaciones de build y foldr.
La desventaja de este enfoque es que no puede manejar pliegues izquierdos. Stream Fusion maneja esto muy bien, sin embargo. Expresa listas de productores y transformadores como flujos (tipos de datos coinductivos, tipo de iteradores similares). El documento anterior es muy legible, por lo que recomiendo echar un vistazo.
El papel "plátanos" mencionado por gasche entra en más detalles sobre los tipos de pliegues y sus equivalencias.
Por último, está Bird and Moor's "Algebra of Programming", que menciona transformaciones como combining two folds into one.
como yo lo entiendo, la fusión requiere una recursión polimórfica de orden superior, y aunque mi lenguaje apenas apenas se las arregla para soportar Mónadas, no puede manejar fusiones; (Tal vez tengo algunos de los términos incorrectos aquí ... +1 para referirme al flujo de papel de fusión! – Yttrill
No hay recursión polimórfica en curso. No sé qué más * el orden de recursión polimórfica * es. Sin embargo, 'build' tiene un tipo de rango 2 (el' forall' en el primer argumento). La fusión de secuencias a su vez requiere tipos existenciales (la función stepper). Tal vez puedas explicar más sobre lo que estás intentando hacer (y su ajuste)? – nominolo
Mi configuración es mi lenguaje Felix. Principalmente estoy buscando optimizaciones. Idealmente, alguien ayudaría a diseñar un sistema de kinding adecuado para permitir optimizaciones de alto nivel como la fusión. – Yttrill
Si le interesa profundizar en la teoría, le sugiero que lea algo sobre catamorphisms, anamorphisms y hylomorphisms. Si bien la teoría de categorías que lo rodea puede parecer un poco aterradora, el concepto no es tan difícil.
Los catamorfismos son funciones que consumen estructuras de datos recursivas y producen algún tipo de valor.Los anamorfismos son funciones que, dado algún valor (una especie de semilla) producen estructuras de datos recursivas. En particular, foldr y build mencionados en las otras torres son funciones para construir catamorfismos y anamorphisms en listas. Pero este concepto se puede aplicar básicamente a cualquier estructura de datos recursiva, como diferentes tipos de árboles, etc.
Ahora, si construyes una estructura recursiva de datos con un anamorfismo y luego la consumes con un catamorfismo, obtienes lo que se llama hylomorphism. En tal caso, en realidad no necesita la estructura intermedia. Puedes saltarte la creación y la destrucción. Esto a menudo se llama deforestation.
En cuanto map: Esta función es interesante que es a la vez un catamorphism y una anamorfosis:
map consume una lista y produce algo; pero tambiénmap produce una lista, consumiendo algo.Así se puede ver la composición de los dos mapas map f . map g como una composición de una anamorfosis (map g) con un catamorphism (map f), formando una hilomorfismo. Por lo tanto, puede optimizar (deforestar) al no crear la lista intermedia.
Para ser más específicos: Se puede escribir map de dos maneras, uno con foldr y la otra usando build:
mapAna :: (a -> b) -> [a] -> [b]
mapAna f xs = build (mapAna' f xs)
mapAna' :: (a -> b) -> [a] -> (b -> c -> c) -> c -> c
mapAna' f [] cons nil = nil
mapAna' f (x : xs) cons nil = (f x) `cons` (mapAna' f xs cons nil)
mapCata :: (a -> b) -> [a] -> [b]
mapCata f xs = foldr (\x ys -> f x : ys) [] xs
y la composición map f (map g zs) como mapCata f (mapAna g zs), que después de algunas simplificaciones y aplicando foldr c n (build g) == g c n resultados en map (f . g).
Sí, debería leer más. Recientemente volví a mirar a Charity. – Yttrill
es posible que desee publicar esto en la página CS teórica, también – blueberryfields
@blueberryfields: [Intercambio de pila de informática teórica] (http://cstheory.stackexchange.com/) es para TCS de nivel de investigación, que esta pregunta no es posible. 't. @Yttril: Fold es una operación universal (cada acción secuencial en una estructura de datos se puede expresar como un doblez), lo que sugiere que pocas de esas ecuaciones se mantienen. – Gilles
@Giles: sí, es por eso que estaba curioso sobre cuántas optimizaciones hay en realidad. – Yttrill