Uso pratico di piega / ridurre in linguaggi funzionali

Question

Fold (aka reduce) è considerato un importante funzione di ordine superiore. Map può essere espressa in termini di fold ( Vedi qui ). Ma suona più accademico che pratico a me. Un utilizzo tipico potrebbe essere quello di ottenere la somma, o di un prodotto, o il massimo di numeri, ma di solito queste funzioni accetta qualunque numero di argomenti. Allora perché (fold + 0 '(2 3 5)) scrittura quando (+ 2 3 5) funziona bene. La mia domanda è, in quale situazione è più facile o più naturale per uso fold?

Answer 1

Il punto di fold è che è più astratto. Non è che si possono fare cose che non si poteva prima, è che si può fare più facilmente.

Utilizzando un fold, è possibile generalizzare qualsiasi funzione definita su due elementi da applicare ad un numero arbitrario di elementi. Questa è una vittoria, perché di solito è molto più facile da scrivere, testare, mantenere e modificare una singola funzione che si applica due argomenti che a una lista. Ed è sempre più facile da scrivere, testare, mantenere, ecc una funzione semplice, invece di due con funzionalità simili-ma-non-proprio.

Dal fold (e per questo, map, filter, e amici) hanno un comportamento ben definito, è spesso molto più facile da capire il codice utilizzando queste funzioni di ricorsione esplicita.

In sostanza, una volta che hai l'una versione, si ottiene l'altro "gratis". In definitiva, si finisce per fare meno lavoro per ottenere lo stesso risultato.

Answer 2

Ecco alcuni semplici esempi in cui reduce funziona davvero bene.

Trova la somma dei valori massimi di ogni sotto-list

Clojure:

user=> (def x '((1 2 3) (4 5) (0 9 1)))
#'user/x
user=> (reduce #(+ %1 (apply max %2)) 0 x)
17

Racket:

> (define x '((1 2 3) (4 5) (0 9 1)))
> (foldl (lambda (a b) (+ b (apply max a))) 0 x)
17

costruire una mappa da un elenco

Clojure:

user=> (def y '(("dog" "bark") ("cat" "meow") ("pig" "oink")))
#'user/y
user=> (def z (reduce #(assoc %1 (first %2) (second %2)) {} y))
#'user/z
user=> (z "pig")
"oink"

Per un esempio clojure più complicato con reduce, controlla mia soluzione ai problemi Project Euler 18 & 67 .

Vedere anche: ridurre vs. applicano

Answer 3

funzioni In Common Lisp non accetta qualunque numero di argomenti.

C'è una costante definita in ogni implementazione Common Lisp CALL-ARGOMENTI TERMINE , che deve essere di 50 o superiore.

Ciò significa che qualsiasi tale funzione portabile scritto dovrebbe accettare almeno 50 argomenti. Ma potrebbe essere solo 50.

Questo limite esiste per consentire compilatori a regimi chiamanti utilizzano eventualmente ottimizzato e di non fornire il caso generale in cui potrebbe essere passato un numero illimitato di argomenti.

Così realmente processare grande (maggiore di 50 elementi) elenchi o vettori in portatile codice Common Lisp, è necessario utilizzare iterazione costrutti, ridurre, carta e simili. Per questo è necessario anche di non usare (apply '+ large-list) ma l'uso (reduce '+ large-list).

Answer 4

1. Il vostro esempio (+ 2 3 4) funziona solo perché si conosce il numero di argomenti in anticipo. Pieghe lavoro sulle liste la cui dimensione può variare.

2. fold / reduce è la versione generale del modello di "cdr-ing un elenco". Ogni algoritmo che è circa l'elaborazione di ogni elemento di una sequenza in ordine e calcolare un valore di ritorno da quella può essere espresso con esso. E 'fondamentalmente la versione funzionale del ciclo foreach.

Answer 5

Codice utilizzando piega di solito è difficile da leggere. Ecco perché la gente preferisce mappa, filtro, esiste, somma, e così via, quando disponibile. In questi giorni sto scrivendo principalmente compilatori e interpreti; ecco alcuni modi che uso duplice:

• Calcola l'insieme di variabili libere per una funzione, espressione, o di tipo
• Aggiungi i parametri di una funzione per la tabella dei simboli, per esempio, per il controllo di tipo
• accumulare la raccolta di tutti i messaggi di errore sensibili generato da una sequenza di definizioni
• Aggiungi tutte le classi predefinite per un interprete di Smalltalk al momento del boot

Ciò che tutti questi usi hanno in comune è che sono accumulando informazioni su un sequenza in una sorta di set o dizionario . eminentemente pratico.

Answer 6

Ecco un esempio che nessun altro ancora citato.

Con l'utilizzo di una funzione con un piccolo, un'interfaccia ben definita come "piega", è possibile sostituire che l'applicazione senza rompere i programmi che lo utilizzano. Si potrebbe, ad esempio, fare una versione distribuita che gira su migliaia di PC , quindi un algoritmo di ordinamento quello utilizzato sarebbe diventato un distribuiti sorta , e così via. I vostri programmi diventano più robusto, più semplice e più veloce .

Il vostro esempio è un banale: + tiene già un numero qualsiasi di argomenti, corre rapidamente in poca memoria, ed è già stato scritto e debug da chi ha scritto il compilatore. Queste proprietà non sono spesso vero di algoritmi ho bisogno di correre.