Contare e raggruppare

Quante volte?

“Quante volte compare ogni parola in questo testo?” È una delle domande più comuni che un programma si sente fare, in mille varianti: quanti voti ha preso ogni candidato, quante vendite per prodotto, quanti errori per tipo. La risposta è sempre un dizionario: la chiave è la cosa da contare, il valore è il conteggio.

L’idea: si parte da un dizionario vuoto e si percorre la lista con un fold. Per ogni parola, se è già nel dizionario si aumenta il suo conteggio di uno, altrimenti la si aggiunge con 1. Quel “se c’è aggiorna, altrimenti inserisci” è così comune che ha una funzione tutta sua: dict.upsert (da update più insert).

import gleam/dict
import gleam/io
import gleam/list
import gleam/option.{None, Some}
import gleam/string

pub fn main() -> Nil {
  let words = string.split("the cat and the hat and the bat", on: " ")
  let counts =
    list.fold(words, dict.new(), fn(counts, word) {
      dict.upsert(counts, word, fn(existing) {
        case existing {
          Some(count) -> count + 1
          None -> 1
        }
      })
    })
  io.println(string.inspect(dict.get(counts, "the")))
  io.println(string.inspect(dict.get(counts, "and")))
  io.println(string.inspect(dict.size(counts)))
}

Ok(3)
Ok(2)
5

dict.upsert(d, chiave, f) chiama la funzione f con il valore attuale della chiave, dentro un Option (lezione 4.5): Some(valore) se la chiave c’è, None se non c’è. Quello che f restituisce diventa il nuovo valore. Il case nella funzione si legge proprio come la frase: “se c’era un conteggio, uno in più; se non c’era, 1”.

Riassumere un dizionario: dict.fold

Come le liste, anche un dizionario si può ridurre a un valore con dict.fold. La funzione riceve l’accumulatore, la chiave e il valore:

  dict.fold(counts, 0, fn(total, _word, count) { total + count })

vale 8, il numero totale di parole. (La chiave qui non serve, e il trattino basso davanti a _word lo dice al compilatore.) Due parenti di list.map e list.filter lavorano su chiavi e valori insieme:

• dict.map_values(d, fn(chiave, valore) { ... }) trasforma ogni valore, tenendo le chiavi;
• dict.filter(d, fn(chiave, valore) { ... }) tiene solo le coppie per cui la funzione dice True.

Ordinare per valore

Per mostrare le parole dalla più frequente, serve una lista ordinata per conteggio, dal più grande. Nella lezione 3.4 abbiamo ordinato con int.compare; qui serve un confronto su misura, una funzione che riceve due coppie e restituisce un Order:

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

pub fn main() -> Nil {
  [#("hat", 1), #("the", 3), #("bat", 1), #("and", 2), #("cat", 1)]
  |> list.sort(fn(a, b) {
    int.compare(b.1, a.1)
    |> order.break_tie(string.compare(a.0, b.0))
  })
  |> list.each(fn(pair) { io.println(pair.0 <> ": " <> int.to_string(pair.1)) })
}

the: 3
and: 2
bat: 1
cat: 1
hat: 1

Due trucchi in una funzione:

• int.compare(b.1, a.1) confronta i conteggi al contrario (prima b, poi a): così i più grandi vanno in cima.
• order.break_tie(primo, secondo): se il primo confronto dice “uguali” (Eq), decide il secondo. A parità di conteggio, le parole vanno in ordine alfabetico. Senza, l’ordine delle parità dipenderebbe dall’ordine (casuale) del dizionario.

Raggruppare: list.group

Una domanda parente di “quante volte?” è “quali?”: raggruppare gli elementi di una lista secondo una loro caratteristica. list.group(lista, funzione) restituisce un dizionario: la chiave è il risultato della funzione, il valore è la lista degli elementi che l’hanno prodotto.

import gleam/dict
import gleam/io
import gleam/list
import gleam/string

pub fn main() -> Nil {
  let groups =
    ["apple", "avocado", "banana", "blueberry", "cherry"]
    |> list.group(fn(fruit) { string.slice(fruit, at_index: 0, length: 1) })
  io.println(string.inspect(dict.get(groups, "a")))
  io.println(string.inspect(dict.get(groups, "b")))
  io.println(string.inspect(dict.get(groups, "z")))
}

Ok(["avocado", "apple"])
Ok(["blueberry", "banana"])
Error(Nil)

La funzione estrae la prima lettera (string.slice prende un pezzo di stringa), e i frutti vengono raggruppati per iniziale. Nota un dettaglio: dentro ogni gruppo gli elementi sono al contrario rispetto alla lista di partenza. Se l’ordine conta, list.reverse sul gruppo (o un list.sort).

  let ballots = ["Ada", "Joe", "Ada", "Grace", "Joe", "Linus", "Ada", "Joe"]

Ada: 3
Joe: 3
Grace: 1
Linus: 1
Votes: 8
Winners: Ada, Joe

import gleam/dict.{type Dict}
import gleam/int
import gleam/io
import gleam/list
import gleam/option.{None, Some}
import gleam/order
import gleam/string

pub fn main() -> Nil {
  let ballots = ["Ada", "Joe", "Ada", "Grace", "Joe", "Linus", "Ada", "Joe"]
  let results = count(ballots)

  results
  |> dict.to_list
  |> list.sort(fn(a, b) {
    int.compare(b.1, a.1)
    |> order.break_tie(string.compare(a.0, b.0))
  })
  |> list.each(fn(pair) { io.println(pair.0 <> ": " <> int.to_string(pair.1)) })

  let total = dict.fold(results, 0, fn(total, _name, votes) { total + votes })
  io.println("Votes: " <> int.to_string(total))

  let best = results |> dict.values |> list.fold(0, int.max)
  let winners =
    results
    |> dict.filter(fn(_name, votes) { votes == best })
    |> dict.keys
    |> list.sort(string.compare)
  io.println("Winners: " <> string.join(winners, with: ", "))
}

fn count(ballots: List(String)) -> Dict(String, Int) {
  list.fold(ballots, dict.new(), fn(counts, name) {
    dict.upsert(counts, name, fn(existing) {
      case existing {
        Some(votes) -> votes + 1
        None -> 1
      }
    })
  })
}

Ricapitolando

• Per contare: list.fold partendo da dict.new(), e dict.upsert per ogni elemento.
• dict.upsert(d, chiave, fn(existing) { ... }) riceve Some(valore) o None, e restituisce il nuovo valore.
• dict.fold(d, iniziale, fn(acc, chiave, valore) { ... }) riassume un dizionario.
• dict.map_values e dict.filter lavorano su chiave e valore insieme.
• Per ordinare in modo decrescente, scambia gli argomenti del confronto: int.compare(b, a); order.break_tie decide le parità.
• list.group(l, f) raggruppa in un Dict(chiave, List(elemento)), con gli elementi di ogni gruppo al contrario.

Nella prossima lezione un parente stretto del dizionario: l’insieme, per le collezioni in cui conta solo se una cosa c’è.