Insiemi · Dizionari, insiemi e tipi opachi

Conta solo se c’è

A volte di una collezione non ti interessa l’ordine, né quante volte compare un elemento: ti interessa solo se c’è. I tag di un articolo, le lettere già usate in una partita all’impiccato, le persone che hanno già votato. Con una lista, per sapere se un elemento c’è bisogna scorrerla (list.contains), e niente impedisce i doppioni. Per questi casi esiste l’insieme.

src/article_tags.gleam

import gleam/io
import gleam/list
import gleam/set
import gleam/string

pub fn main() -> Nil {
  let tags = set.from_list(["gleam", "beam", "gleam", "types", "beam"])
  io.println(string.inspect(set.size(tags)))
  io.println(string.inspect(set.contains(tags, "beam")))
  io.println(string.inspect(set.contains(tags, "rust")))

  let tags = set.insert(tags, "tests")
  let sorted = tags |> set.to_list |> list.sort(string.compare)
  io.println(string.join(sorted, with: ", "))
}

output

3
True
False
beam, gleam, tests, types

Il modulo gleam/set definisce il tipo Set(a). set.from_list ha scartato i doppioni: cinque etichette in ingresso, tre nell’insieme. set.contains risponde in un attimo, come la ricerca di una chiave in un dizionario; set.insert e set.delete restituiscono un insieme nuovo. E come i dizionari, gli insiemi non hanno ordine: per stampare, set.to_list e poi list.sort.

Le operazioni degli insiemi

Gli insiemi della matematica hanno tre operazioni classiche, e gleam/set le ha tutte:

Funzione	Cosa contiene	Esempio con `{a, b, c}` e `{b, c, d}`
`set.union(a, b)`	gli elementi di almeno uno dei due	`{a, b, c, d}`
`set.intersection(a, b)`	gli elementi comuni ai due	`{b, c}`
`set.difference(a, b)`	gli elementi di `a` che non sono in `b`	`{a}`

Sono il modo più chiaro per rispondere a domande come “quali corsi frequentano sia Ada sia Grace?” (intersezione), “quali lettere ha indovinato solo il primo giocatore?” (differenza), “tutti i tag usati in due articoli” (unione). Con le liste servirebbero filtri e list.contains annidati; con gli insiemi è una riga.

Quiz

Quanto vale set.size(set.union(set.from_list([1, 2, 3]), set.from_list([3, 4])))?

Esercizio · sul tuo computer

Interessi in comune

Nel progetto exercises crea src/interests.gleam. Gli interessi di Ada e di Grace sono due liste (con qualche doppione, perché i dati veri sono sempre un po’ sporchi):

gleam

  let ada = ["chess", "maths", "music", "cooking", "chess"]
  let grace = ["music", "hiking", "chess"]

Trasformale in insiemi e stampa, in ordine alfabetico: gli interessi in comune, quelli che ha solo Ada, e tutti gli interessi dei due insieme. Scrivi una piccola funzione show(interests: Set(String)) -> String che ordina e unisce con ", ".

output

In common: chess, music
Only Ada: cooking, maths
Together: chess, cooking, hiking, maths, music

Cosa ha stampato il programma?

Mostra una soluzione (prima prova da solo!)

src/interests.gleam

import gleam/io
import gleam/list
import gleam/set.{type Set}
import gleam/string

pub fn main() -> Nil {
  let ada = set.from_list(["chess", "maths", "music", "cooking", "chess"])
  let grace = set.from_list(["music", "hiking", "chess"])

  io.println("In common: " <> show(set.intersection(ada, grace)))
  io.println("Only Ada: " <> show(set.difference(ada, grace)))
  io.println("Together: " <> show(set.union(ada, grace)))
}

fn show(interests: Set(String)) -> String {
  interests
  |> set.to_list
  |> list.sort(string.compare)
  |> string.join(with: ", ")
}

Il doppione "chess" sparisce appena la lista diventa un insieme, senza bisogno di list.unique. Ogni domanda è una sola operazione sugli insiemi, e l’ordinamento avviene solo alla fine, per stampare.

Ricapitolando

Un Set(a) è una collezione senza doppioni e senza ordine: conta solo se un elemento c’è.
set.from_list, set.insert, set.delete, set.contains, set.size, set.to_list.
set.union (almeno uno), set.intersection (entrambi), set.difference (nel primo ma non nel secondo).
Per stampare in ordine: set.to_list e poi list.sort.
Dentro, un insieme è un dizionario di cui contano solo le chiavi; ma è un dettaglio nascosto.

Nella prossima lezione scopriamo come si nasconde un dettaglio: i tipi opachi.