Ottimizzazioni con piegature

Question

Sono curioso di sapere se ci sono ottimizzazioni (solo in ordine polimorfo) con pieghe.

Per le mappe, c'è la deforestazione: map g (map f ls) => map (g . f) ls e rev (map f ls) => rev_map f ls (più veloce in Ocaml).

Ma fold è così potente che sembra sfidare qualsiasi ottimizzazione.

Answer 1

Quelle ovvie:

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 *) 

Potresti essere interessato nella carta classica sul tema, "Programmazione funzionale con le banane, Lenti, buste e filo spinato". Fai attenzione però che è tecnico e ha una notazione impenetrabile.

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125

Edit: la mia prima versione della prima regola era sbagliato, a cura grazie a Vincent-Hugot.

Answer 2

È possibile utilizzare la deforestazione sulle pieghe. In effetti, la fusione map/map è un caso speciale di quello.

Il trucco è quello di sostituire la costruzione nell'elenco una speciale build funzione:

build :: (forall b. (a -> b -> b) -> b -> b) -> [a] 
build g = g (:) [] 

Ora, usando la definizione standard di foldr

foldr :: (a -> b -> b) -> b -> [a] -> b 
foldr c n []  = n 
foldr c n (x:xs) = c x (foldr c n xs) 

Abbiamo la seguente equivalenza:

foldr c n (build g) == g c n 

(In realtà questo è vero solo in certe , ma comuni, circostanze. Per dettagli vedere "Correctness of short-cut fusion").

Se si scrive l'elenco producendo funzioni (incluso map) utilizzando build e gli utenti che utilizzano foldr, l'uguaglianza di cui sopra può rimuovere la maggior parte degli elenchi intermedi. Le descrizioni delle liste di Haskell sono tradotte in combinazioni di build e foldr.

Lo svantaggio di questo approccio è che non può gestire le pieghe a sinistra. Stream Fusion gestisce questo bene, però. Esprime list produttori e trasformatori come flussi (tipi di dati coinduttivi, tipo di iteratori simili). Il documento sopra è molto leggibile, quindi consiglio di dare un'occhiata.

Il documento "banane" menzionato da gasche approfondisce i tipi di pieghe e le loro equivalenze.

Infine, c'è Bird & Moor's "Algebra of Programming", che menziona le trasformazioni come combining two folds into one.

Answer 3

Se ti interessa approfondire la teoria, ti suggerisco di leggere qualcosa su catamorphisms, anamorphisms e hylomorphisms. Mentre la teoria delle categorie che la circonda può sembrare un po 'spaventosa, il concetto non è così difficile.

I catamorfismi sono funzioni che consumano strutture dati ricorsive e producono un qualche tipo di valore.Gli anamorfismi sono funzioni che hanno un certo valore (una specie di seme) producono strutture dati ricorsive. In particolare, foldr e build menzionati negli altri registri sono funzioni per costruire catamorfismi e anamorfismi nelle liste. Ma questo concetto può essere applicato fondamentalmente a qualsiasi struttura dati ricorsiva, come diversi tipi di alberi ecc.

Ora se si costruisce una struttura dati ricorsiva con un anamorfismo e poi si consuma con un catamorfismo, si ottiene ciò che viene chiamato un ilemorfismo. In tal caso, in realtà non hai bisogno della struttura intermedia. Puoi saltare la creazione e distruggerlo. Questo è spesso chiamato deforestation.

---

Per quanto riguarda map: Questa funzione è interessante che è sia un catamorphism e un anamorfismo:

• map consuma una lista e produce qualcosa; ma anche
• map produce una lista, consumando qualcosa.

Così si può visualizzare la composizione di due mappe map f . map g come una composizione di un anamorfismo (map g) con una catamorphism (map f), formando un ilemorfismo. Quindi sai che puoi ottimizzare (deforest) non creando la lista intermedia.

essere specifici: Si potrebbe scrivere map in due modi: una con foldr e l'altro utilizzando 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 

e la composizione map f (map g zs) come mapCata f (mapAna g zs), che, dopo alcune semplificazioni e applicando foldr c n (build g) == g c n risultati in map (f . g).