Metodo map

Si supponga di voler scrivere una funzione scaleList che, dati una lista di interi xs e un numero intero factor, restituisca una nuova lista ottenuta moltiplicando ogni elemento di xs per factor.

def scaleList(xs: List[Int], factor: Int): List[Int] = xs match {
	case Nil => Nil
	case y :: ys => (y * factor) :: scaleList(ys, factor)
}

Questo schema è generalizzato, dalla funzione map, che applica un arbitraria funzione a tutti gli elementi di una lista. Essa funzione è disopnibile nella libreria standard di Scala come metodo della classe List[+T] (e di molte altre strutture dati). Concettualmente, la sua implementazione potrebbe essere la seguente:

sealed abstract class List[+T] {
	// ...
	def map[U](f: T => U): List[U] = this match {
		case Nil => Nil
		case x :: xs => f(x) :: xs.map(f)
	}
	// ...
}

(la reale implementazione evita gli svantaggi della ricorsione non in coda presente in quest’implementazione semplificata facendo uso delle parti imperative di Scala). Si osservi che il tipo di map è parametrico nel codominio U della funzione f applicata agli elementi della lista originale, ovvero nel tipo degli elementi della nuova lista, che sono appunto generati applicando la funzione f e quindi appartengono al codominio di tale funzione.

Utilizzando mapla funzione scaleList può essere riscritta come:

def scaleList(xs: List[Int], factor: Int): List[Int] =
	xs map (x => x * factor)

Funzioni all’ordine superiore delle liste

Mentre i metodi di List[+T] visti in precedenza sono funzioni al primo ordine, il metodo map appena introdotto è un esempio di funzione all’ordine superiore, in quanto prende come argomento una funzione.

In generale, le funzioni all’ordine superiore sulle liste (map, e alre che verranno presentate nel seguito) appartengono a tre principali famiglie:

• funzioni di map, che trasformano gli elementi di una lista
• funzioni di filtering, che selezionano una parte degli elementi di una lista, restituendo una nuova lista costituita dai soli elementi che soddisfano un determinato criterio
• funzioni di reduce, che combinano gli elementi di una lista usando un operatore

Questi tipi di funzioni esistono non solo per le liste, ma per praticamente tutte le strutture dati.

Metodo filter

Un esempio di filtering è la seguente funzione, che restituisce la lista di tutti i valori positivi contenuti in una lista di interi:

def posElem(xs: List[Int]): List[Int] = xs match {
	case Nil => Nil
	case y :: ys => if (y > 0) y :: posElem(ys) else posElem(ys)
}

Generalizzando lo schema di posElem si ottiene il metodo filter, che è definito nella classe List[+T] e potrebbe essere implementato in questo modo:

sealed abstract class List[+T] {
	// ...
	def filter(p: T => Boolean): List[T] = this match {
		case Nil => Nil
		case x :: xs => if (p(x)) x :: xs.filter(p) else xs.filter(p)
	}
	// ...
}