Ridurre con fold

Da tanti a uno

list.map e list.filter prendono una lista e restituiscono una lista. Ma molte domande sulle liste hanno come risposta un valore solo: la somma, il più grande, la parola più lunga, il testo che le unisce tutte. Per queste c’è list.fold, che ripiega una lista su se stessa fino a ridurla a un valore.

Hai già scritto un fold senza saperlo, nella lezione 3.3:

fn sum_loop(numbers: List(Int), total: Int) -> Int {
  case numbers {
    [] -> total
    [first, ..rest] -> sum_loop(rest, total + first)
  }
}

Di questa funzione, solo due cose sono davvero “sulla somma”: il valore iniziale dell’accumulatore (0) e come si combina l’accumulatore con un elemento (total + first). Tutto il resto, la ricorsione, il caso base, la chiamata in coda, è identico per qualsiasi accumulo. list.fold è quel resto, già scritto: tu gli dai la lista, il valore iniziale e la funzione che combina.

list.fold

import gleam/int
import gleam/io
import gleam/list

pub fn main() -> Nil {
  let numbers = [18, 25, 30]
  let total = list.fold(numbers, 0, fn(total, n) { total + n })
  let product = list.fold(over: numbers, from: 1, with: fn(acc, n) { acc * n })
  io.println("Total: " <> int.to_string(total))
  io.println("Product: " <> int.to_string(product))
}

Total: 73
Product: 13500

list.fold riceve tre cose, e le etichette dicono quali:

• over: la lista da percorrere;
• from: il valore iniziale dell’accumulatore;
• with: una funzione fn(accumulatore, elemento) -> nuovo_accumulatore.

Parte dal valore iniziale e, per ogni elemento, da sinistra a destra, chiama la funzione con l’accumulatore attuale e l’elemento; quello che la funzione restituisce diventa il nuovo accumulatore. Alla fine della lista, l’accumulatore è il risultato. Per la somma di [18, 25, 30]:

accumulatore:  0
elemento 18:   0 + 18  = 18
elemento 25:   18 + 25 = 43
elemento 30:   43 + 30 = 73
fine:          73

L’accumulatore può essere qualsiasi cosa

L’accumulatore non deve essere dello stesso tipo degli elementi. Può essere un numero, un testo, un Bool, una lista: quello che serve alla domanda.

• La parola più lunga: l’accumulatore è la parola migliore finora.

  list.fold(words, "", fn(best, word) {
    case string.length(word) > string.length(best) {
      True -> word
      False -> best
    }
  })

• Il testo al contrario: l’accumulatore è una stringa, e ogni elemento va davanti. list.fold(["a", "b", "c"], "", fn(acc, s) { s <> acc }) vale "cba".

• Una lista rovesciata: l’accumulatore è una lista, e ogni elemento va in testa. list.fold(l, [], fn(acc, x) { [x, ..acc] }) è list.reverse.

In effetti con fold si può scrivere quasi tutto: map, filter, count, length… Ma se c’è una funzione che dice già cosa fai, usa quella: int.sum(numbers) si legge meglio di un fold con un’addizione. fold è per quando nessuna funzione pronta fa al caso tuo.

Contare senza una lista: int.range

Ricordi int.range, rimandata alla lezione 3.3? Ora puoi capirla: è un fold sui numeri di un intervallo, senza bisogno di costruire la lista.

  int.range(from: 1, to: 11, with: 0, run: fn(acc, n) { acc + n })

vale 55, la somma dei numeri da 1 a 10. Attenzione al limite: to è escluso. L’intervallo va da 1 fino a 11, 11 escluso. Con un accumulatore lista puoi ottenere i numeri stessi, ma al contrario: int.range(from: 1, to: 4, with: [], run: fn(acc, n) { [n, ..acc] }) vale [3, 2, 1].

Numerare le righe: list.index_map

Un bisogno frequente quando si stampa una lista: numerare gli elementi. list.index_map è come list.map, ma la funzione riceve anche la posizione dell’elemento, contando da 0:

import gleam/int
import gleam/io
import gleam/list

pub fn main() -> Nil {
  ["Tea", "Coffee", "Cake"]
  |> list.index_map(fn(item, index) { int.to_string(index + 1) <> ". " <> item })
  |> list.each(io.println)
}

1. Tea
2. Coffee
3. Cake

Qui l’ordine è elemento, poi posizione. E il + 1 serve perché le persone contano da 1, le liste da 0.

1. 1.20
2. 2.50
3. 0.99
4. 13.40
Total: 18.09
Most expensive: 13.40

import gleam/int
import gleam/io
import gleam/list
import gleam/string

pub fn main() -> Nil {
  let prices = [120, 250, 99, 1340]

  prices
  |> list.index_map(fn(price, index) {
    int.to_string(index + 1) <> ". " <> format_cents(price)
  })
  |> list.each(io.println)

  let total = list.fold(prices, 0, fn(total, price) { total + price })
  let highest = list.fold(prices, 0, int.max)
  io.println("Total: " <> format_cents(total))
  io.println("Most expensive: " <> format_cents(highest))
}

fn format_cents(cents: Int) -> String {
  int.to_string(cents / 100)
  <> "."
  <> { cents % 100 |> int.to_string |> string.pad_start(2, "0") }
}

Ricapitolando

• list.fold(over: l, from: iniziale, with: f) riduce una lista a un valore: parte da iniziale e combina l’accumulatore con ogni elemento.
• La funzione è fn(accumulatore, elemento): prima l’accumulatore. Se i tipi non tornano, controlla l’ordine.
• L’accumulatore può essere di qualsiasi tipo: numero, testo, lista.
• fold sa fare quasi tutto, ma se esiste una funzione più specifica (int.sum, list.count…) usa quella.
• int.add, int.multiply, int.max si passano direttamente a fold.
• int.range(from:, to:, with:, run:) è un fold su un intervallo di numeri, con to escluso.
• list.index_map(l, fn(elemento, posizione) { ... }) è map con la posizione, contando da 0.

Nella prossima lezione tiriamo le somme del modulo, e la macchina del resto del modulo 2 si libera finalmente del suo trucco.