Programmazione · concetti · Haskell

Cos’è una funzione di ordine superiore?

Nella maggior parte dei linguaggi una funzione è qualcosa che si chiama. Nella programmazione funzionale una funzione è anche un valore: puoi metterla in una variabile, passarla a un’altra funzione e riceverne una come risultato. Una funzione di ordine superiore è esattamente quella che fa una di queste due ultime cose. Questa guida spiega cos’è una funzione di ordine superiore, perché map, filter e fold sono gli esempi classici, come sostituiscono i cicli e come appaiono in Haskell.

La definizione breve

Una funzione di ordine superiore è una funzione che riceve una o più funzioni come argomento, restituisce una funzione come risultato, o entrambe le cose. Una funzione che non fa né l’una né l’altra — che riceve e restituisce solo valori semplici come numeri o stringhe — si dice di primo ordine. Il termine «ordine superiore» significa semplicemente che opera su funzioni come una funzione ordinaria opera sui dati.

Questo funziona solo in un linguaggio in cui le funzioni sono valori di prima classe: cose che puoi nominare, passare e restituire, proprio come un intero. Haskell, JavaScript, Python, Swift e molti altri trattano così le funzioni, ed è ciò che rende possibili le funzioni di ordine superiore.

Le tre classiche: map, filter e fold

Quasi ogni base di codice funzionale si appoggia su tre funzioni di ordine superiore. Ciascuna riceve una funzione come argomento e la applica a una collezione:

• map applica una funzione a ogni elemento di una lista e restituisce una nuova lista dei risultati. map (+1) [1,2,3] dà [2,3,4] — la funzione (+1) è l’argomento.
• filter mantiene solo gli elementi per cui una funzione restituisce vero. filter even [1,2,3,4] dà [2,4] — qui even è la funzione che passi.
• fold (chiamato anche reduce) riduce una lista a un singolo valore combinando gli elementi a due a due. foldr (+) 0 [1,2,3] li somma fino a 6 — il passo di combinazione (+) è la funzione passata come argomento.

In ogni caso fornisci tu il piccolo pezzo di logica — incrementare, «è pari», sommare — e la funzione di ordine superiore si occupa di scorrere la lista. Descrivi cosa fare a ogni elemento, non la meccanica del come scorrerli.

Come sostituiscono i cicli

In un linguaggio imperativo scriveresti un ciclo con un contatore, un accumulatore e un indice esplicito. La stessa intenzione espressa con una funzione di ordine superiore sta in una sola riga, perché l’iterazione è già integrata in map o fold. Per questo il codice puramente funzionale, che evita i contatori di ciclo mutabili, si appoggia tanto a queste funzioni e alla ricorsione — insieme coprono il lavoro che altrove fanno i cicli. Le comprensioni di liste sono spesso una scorciatoia leggibile per la stessa combinazione di map e filter.

Restituire una funzione: dove diventa potente

L’altra metà della definizione — funzioni che restituiscono funzioni — è altrettanto comune. Una funzione può costruire e restituire una nuova funzione specializzata. Un esempio classico è il «creatore di moltiplicatori»: gli dai un numero e restituisce una funzione che moltiplica il suo input per quel numero. Chiamalo con 3 e ottieni una funzione «per tre» utilizzabile come qualsiasi altra. Il creatore è di ordine superiore perché il suo risultato è a sua volta una funzione.

In Haskell tutto ciò è intessuto nel linguaggio tramite il currying: ogni funzione con più argomenti è in realtà una catena di funzioni a un solo argomento, ciascuna che restituisce la successiva. Per questo map (+1) funziona — (+1) è la funzione di addizione con un argomento già fornito, che restituisce una funzione che attende ancora l’altro. Questa applicazione parziale sono le funzioni di ordine superiore al lavoro, spesso senza che te ne accorga.

Le funzioni di ordine superiore in Haskell

Haskell rende l’idea esplicita nelle sue firme di tipo. Il tipo di map si scrive map :: (a -> b) -> [a] -> [b]. Leggilo da sinistra a destra: il primo argomento (a -> b) è a sua volta una funzione — è la parte di ordine superiore — seguito da una lista di a, che produce una lista di b. Le frecce rendono visibile sulla carta che si sta passando una funzione. Lo stesso schema compare in filter :: (a -> Bool) -> [a] -> [a] e in tutta la libreria standard.

Spesso passi queste funzioni in linea come lambda, piccole funzioni anonime scritte con una barra rovesciata, come map (\x -> x * x) [1,2,3] per elevare al quadrato ogni elemento. Che tu passi una funzione con nome, una sezione di operatore come (*2) o una lambda, è lo stesso meccanismo: una funzione che viaggia come valore in una funzione di ordine superiore.

Perché contano

Le funzioni di ordine superiore permettono di estrarre la forma comune di un calcolo — «fare qualcosa a ogni elemento», «tenere quelli che corrispondono», «combinarli tutti» — e riutilizzarla con una logica diversa innestata. Il risultato: meno codice ripetuto, codice che si legge più vicino alla sua intenzione e piccoli pezzi di logica testabili e componibili. Sono il mattone su cui si esprime gran parte della programmazione funzionale di Haskell, e combinate con la valutazione pigra di Haskell permettono persino di mappare e filtrare liste concettualmente infinite.

I compromessi onesti

Le funzioni di ordine superiore richiedono un po’ di abitudine: leggere un foldr o una catena map . filter è un’abilità, e lambda profondamente annidate possono diventare difficili da seguire. Passare funzioni dappertutto può anche rendere meno evidente uno stack trace quando qualcosa va storto. Il vantaggio — molto meno codice di iterazione ripetitivo e una logica ricomponibile — spiega perché si sono diffuse ben oltre i linguaggi funzionali, fino al JavaScript, Python e Swift di tutti i giorni. Usate con misura, rendono il codice più corto e chiaro; abusate, possono offuscarlo come qualsiasi altro strumento.

Domande frequenti

Sfoglia altre spiegazioni chiare nel nostro indice delle guide.