Note.

• There is an adaptation written in english: https://github.com/enricopolanski/functional-programming
• 한글 번역본이 있습니다: https://github.com/alstn2468/functional-programming

Setup

git clone https://github.com/gcanti/functional-programming.git
cd functional-programming
npm i

Che cos'è la programmazione funzionale

Functional Programming is programming with pure functions. Mathematical functions.

Una rapida ricerca su internet vi può portare alla seguente definizione:

Una funzione (pura) è una procedura che dato lo stesso input restituisce sempre lo stesso output e non ha alcun side effect osservabile.

Il termine "side effect" non ha ancora un significato preciso (vedremo in seguito come darne una definizione formale), ciò che conta per ora è averne una qualche intuizione, pensate per esempio ad aprire un file per leggerne il contenuto, oppure scrivere su un database.

Per ora possiamo limitarci a dire che un side effect è qualsiasi cosa fa una procedura oltre a restituire un valore.

Ma com'è strutturato un programma che usa solo funzioni pure?

Un programma in stile funzionale tende ad essere scritto come una pipeline:

const program = pipe(
  input,
  f1, // funzione pura
  f2, // funzione pura
  f3, // funzione pura
  ...
)

Ciò che accade è che input viene passato come input alla prima funzione f1, la quale restituisce un valore in output che viene passato come input alla seconda funzione f2, la quale restituisce un valore in output che viene passato come input alla terza funzione f3, e così di seguito.

Demo

00_pipe_and_flow.ts

Vedremo come la programmazione funzionale ci fornisce i mezzi per strutturare il nostro codice in questo stile.

Oltre a capire cosa sia la programmazione funzionale, è altrettanto fondamentale capire quale sia il suo scopo.

L'obbiettivo della programmazione funzionale è dominare la complessità di un sistema usando modelli formali e ponendo particolare attenzione alle proprietà del codice e alla facilità di refactoring.

Functional programming will help teach people the mathematics behind program construction:

• how to write composable code
• how to reason about side effects
• how to write consistent, general, less ad-hoc APIs

Che vuol dire porre attenzione alle proprietà del codice? Vediamo un esempio

Esempio

Perché possiamo dire che la funzione map di Array è "più funzionale" di un ciclo for?

// input
const xs: Array<number> = [1, 2, 3]

// trasformazione
const double = (n: number): number => n * 2

// risultato: voglio un array con tutti gli elementi di `xs` raddoppiati
const ys: Array<number> = []
for (let i = 0; i < xs.length; i++) {
  ys.push(double(xs[i]))
}

Un ciclo for è molto flessibile, posso modificare:

• l'indice di partenza
• la condizione di fine
• il passo

Ma ciò vuol dire anche che ci sono più possibilità di introdurre errori e non ho alcuna garanzia sul risultato.

Quiz. Avete controllato che io abbia scritto bene il ciclo?

Vediamo ora come si utilizza map

// risultato: voglio un array con tutti gli elementi di `xs` raddoppiati
const ys = xs.map(double)

Notate come map sia meno flessibile, tuttavia dà più garanzie:

• gli elementi dell'input verrano processati tutti dal primo all'ultimo
• qualunque sia l'operazione che viene fatta nella callback, il risultato sarà sempre un array con lo stesso numero di elementi dell'array in input

Dal punto di vista funzionale, ambito in cui sono importanti le proprietà del codice piuttosto che i dettagli implementativi, l'operazione map è interessante proprio in quanto limitata.

Pensate per esempio a quanto sia più facile la review di una PR che coinvolga una map rispetto ad un ciclo for.

I due pilastri della programmazione funzionale

La programmazione funzionale si appoggia su questi due pilastri:

• trasparenza referenziale
• composizione come design pattern universale

Tutto ciò che vedremo in seguito nel corso deriva direttamente o indirettamente da questi due punti.

Incominciamo dalla trasparenza referenziale.

Trasparenza referenziale

Definition. An expression is said to be referentially transparent if it can be replaced with its corresponding value without changing the program's behavior

Esempio (la trasparenza referenziale implica l'uso di funzioni pure)

const double = (n: number): number => n * 2

const x = double(2)
const y = double(2)

L'espressione double(2) gode della proprietà di trasparenza referenziale perché posso sostituirla con il suo valore 4.

Posso perciò tranquillamente procedere con il seguente refactoring

const x = 4
const y = x

Non tutte le espressioni godono della proprietà di trasparenza referenziale, vediamo qualche esempio

Esempio (la trasparenza referenziale implica non lanciare eccezioni)

const inverse = (n: number): number => {
  if (n === 0) throw new Error('cannot divide by zero')
  return 1 / n
}

const x = inverse(0) + 1

Non posso sostituire l'espressione inverse(0) con il suo valore, perciò l'espressione non gode della proprietà di trasparenza referenziale.

Esempio (la trasparenza referenziale può implicare l'utilizzo di strutture dati immutabili)

const xs = [1, 2, 3]

const append = (xs: Array<number>): void => {
  xs.push(4)
}

append(xs)

const ys = xs

Nell'ultima riga non posso sostituire l'espressione xs con il suo valore iniziale [1, 2, 3] dato che il suo valore attuale è stato cambiato dalla chiamata alla funzione append.

Perché è così importante la trasparenza referenziale? Perché permette di:

• ragionare localmente sul codice (ovvero non ho bisogno di conoscere un contesto più ampio per capire un frammento di codice)
• rifattorizzare senza cambiare il comportamento del programma (per la definizione stessa di trasparenza referenziale)

Quiz. Supponiamo di avere il seguente programma:

// In TypeScript `declare` permette di introdurre una definizione senza specificarne l'implementazione.
declare const question: (message: string) => Promise<string>

const x = await question('What is your name?')
const y = await question('What is your name?')

Posso rifattorizzarlo in questo modo? Il comportamento del programma è lo stesso o è cambiato?

const x = await question('What is your name?')
const y = x

Come potete vedere il refactoring di un programma che contiene espressioni che non godono della proprietà di trasparenza referenziale va affontato con molta cautela. Nella programmazione funzionale, ove ogni espressione gode della proprietà di trasparenza referenziale, il carico cognitivo in fase di refactoring è ridotto.

Parliamo ora del secondo pilastro, la composizione.

Composizione

Il pattern fondamentale della programmazione funzionale è la componibilità, ovvero la costruzione di piccole unità che fanno qualcosa di specifico in grado di essere combinate tra loro al fine di ottenere entità più grandi e complesse.

Come esempi, e in un percorso dal "più piccolo al più grande", possiamo pensare:

• alla composizione di due semplici valori (come due numeri o due stringhe)
• oppure alla composizione di funzioni
• o anche alla composizione di interi programmi

In questo ultimo caso possiamo parlare di "programmazione modulare":

By modular programming I mean the process of building large programs by gluing together smaller programs - Simon Peyton Jones

Vediamo nella pratica come è possibile tendere verso questo stile di programmazione attraverso l'uso di quelli che vengono chiamati combinatori.

Il termine combinatore si riferisce al combinator pattern:

A style of organizing libraries centered around the idea of combining things. Usually there is some type T, some "primitive" values of type T, and some "combinators" which can combine values of type T in various ways to build up more complex values of type T

Il concetto di combinatore è piuttosto sfumato e si può presentare in diverse forme, ma la sua forma più semplice è questa:

combinator: Thing -> Thing

Esempio. Possiamo pensare alla funzione double come ad un combinatore di numeri.

Lo scopo di un combinatore è quello di creare nuove "cose" da "cose" definite precedentemente.

Notate che il risultato del combinatore può essere nuovamente passato come input, si ottiene perciò una esplosione combinatoria di possibilità, il che rende questo pattern molto potente.

Esempio

import { pipe } from 'fp-ts/function'

const double = (n: number): number => n * 2

console.log(pipe(2, double, double, double)) // => 16

Perciò il design generale che potete spesso trovare in un modulo funzionale è questo:

• un modello per T
• un insieme di semplici "primitive" di tipo T
• un insieme di combinatori per combinare le primitive in strutture più complesse

Proviamo ad implementare un modulo di questo tipo:

Demo

01_retry.ts

Come potete vedere dalla demo precedente, con sole tre primitive e due combinatori siamo stati in grado di esprimere una policy piuttosto complessa.

Pensate a come, aggiungendo anche una sola nuova primitiva (o un nuovo combinatore) a quelli già definiti, le possibilità espressive aumentano esponenzialmente.

Dei due combinatori definiti in 01_retry.ts una menzione speciale va a concat dato che è possibile collegarlo ad una importante astrazione della programmazione funzionale: i semigruppi.

Modellare la composizione con i semigruppi

Un semigruppo è una ricetta per combinare due (o più) valori.

Tecnicamente un semigruppo è un'algebra, in generale con il termine "algebra" si intende una particolare combinazione di:

• uno o più insiemi
• una o più operazioni sugli insiemi precedenti
• zero o più leggi a cui devono obbedire le operazioni precedenti

Le algebre sono il modo in cui i matematici catturano un concetto nel modo più diretto eliminando tutto ciò che è superfluo.

Quando si manipola un'algebra sono permesse solo le operazioni definite dall'algebra stessa e in conformità alle sue leggi

L'equivalente delle algebre in programmazione sono le interfacce:

Quando si manipola una interfaccia sono permesse solo le operazioni definite dall'interfaccia stessa e in conformità alle sue leggi.

Prima di affrontare i semigruppi vediamo un primo semplice esempio di algebra che li precede: il magma.

Definizione di magma

Possiamo usare una interface di TypeScript per modellare un magma:

interface Magma<A> {
  readonly concat: (first: A, second: A) => A
}

Abbiamo quindi un'operazione concat che prende due valori di un certo tipo A e restituisce un nuovo valore dello stesso tipo (proprietà di chiusura). Dato che il risultato può a sua volta essere utilizzato come input l'operazione può essere ripetuta a piacimento. In altre parole concat è un combinatore per il tipo A.

Quiz. Il fatto che una operazione sia chiusa non è una proprietà banale, potete fare un esempio di operazione sui numeri naturali (ovvero i numeri interi positivi) per cui la proprietà di chiusura non vale?

Per avere una istanza concreta di magma per un determinato tipo occorre perciò definire un oggetto conforme a questa interfaccia.

Esempio (una istanza di Magma per il tipo number)

import { Magma } from 'fp-ts/Magma'

const MagmaSub: Magma<number> = {
  concat: (first, second) => first - second
}

console.log(
  MagmaSub.concat(
    MagmaSub.concat(MagmaSub.concat(MagmaSub.concat(10, 2), 3), 1),
    2
  )
)
// => 2

// helper
const getPipeableConcat = <A>(M: Magma<A>) => (second: A) => (first: A): A =>
  M.concat(first, second)

const concat = getPipeableConcat(MagmaSub)

// esempio di utilizzo

import { pipe } from 'fp-ts/function'

pipe(10, concat(2), concat(3), concat(1), concat(2), console.log)
// => 2

Notate che la definizione di concat è stata concepita per agevolarne l'uso con pipe.

Quiz. Consideriamo la seguente funzione che trasforma una lista in un dizionario, perché si richiede un Magma come parametro?

import { pipe } from 'fp-ts/function'
import { Magma } from 'fp-ts/Magma'

declare const fromReadonlyArray: <A>(
  M: Magma<A>
) => (as: ReadonlyArray<readonly [string, A]>) => Record<string, A>

// esempio di utilizzo

const MagmaSub: Magma<number> = {
  concat: (first, second) => first - second
}

pipe(
  [
    ['a', 1],
    ['b', 2]
  ],
  fromReadonlyArray(MagmaSub),
  console.log
) // => { a: 1, b: 2 }
pipe(
  [
    ['a', 1],
    ['b', 2],
    ['a', 3]
  ],
  fromReadonlyArray(MagmaSub),
  console.log
) // => { a: -2, b: 2 }

Un Magma<A> è un'algebra molto semplice:

• un insieme (A)
• una operazione (concat)
• nessuna legge

vediamo ora un'algebra che definisce una legge: i semigruppi.

Definizione di semigruppo

Se l'operazione concat di un Magma è anche associativa allora parliamo di semigruppo.

Un'operazione binaria * si dice "associativa" se vale:

(x * y) * z = x * (y * z)

per ogni x, y, z.

L'associatività ci dice che non dobbiamo preoccuparci delle parentesi nelle espressioni e che, volendo, possiamo scrivere semplicemente x * y * z (non c'è ambiguità).

Esempio

La concatenazione di stringhe (+) gode della proprietà associativa.

("a" + "b") + "c" = "a" + ("b" + "c") = "abc"

Ogni semigruppo è un magma, ma non ogni magma è un semigruppo.

Esempio

Il magma MagmaSub che abbiamo visto nella sezione precedente non è un semigruppo poiché la sua operazione concat non è associativa:

import { pipe } from 'fp-ts/function'
import { Magma } from 'fp-ts/Magma'

const MagmaSub: Magma<number> = {
  concat: (first, second) => first - second
}

pipe(MagmaSub.concat(MagmaSub.concat(1, 2), 3), console.log) // => -4
pipe(MagmaSub.concat(1, MagmaSub.concat(2, 3)), console.log) // => 2

I semigruppi catturano l'essenza delle operazioni parallelizzabili.

Infatti se sappiamo che una data operazione * gode della proprietà associativa possiamo suddividere una computazione in due sotto computazioni, ognuna delle quali può essere ulteriormente suddivisa

a * b * c * d * e * f * g * h = ((a * b) * (c * d)) * ((e * f) * (g * h))

Le sotto computazioni possono essere distribuite ed eseguite parallelamente per poi raccoglierne i risultati parziali e comporre il risultato finale.

Come già successo per Magma, i semigruppi possono essere modellati con una interface di TypeScript:

interface Semigroup<A> {
  readonly concat: (first: A, second: A) => A
}

Come vedete la definizione è identica a quella di Magma ma c'è una differenza importante, deve valere la seguente legge (che purtroppo non può essere codificata nel type system di TypeScript):

Associativity. Se S è un semigruppo deve valere:

S.concat(S.concat(x, y), z) = S.concat(x, S.concat(y, z))

per ogni x, y, z in A

Esempio

Implementiamo un semigruppo per ReadonlyArray<string>

import * as Se from 'fp-ts/Semigroup'

const Semigroup: Se.Semigroup<ReadonlyArray<string>> = {
  concat: (first, second) => first.concat(second)
}

Come potete vedere il nome concat ha particolarmente senso per i ReadonlyArray ma, in base al contesto e al tipo A per il quale stiamo implementando una istanza, l'operazione di semigruppo concat può essere interpretata con diversi significati:

• "concatenare"
• "combinare"
• "merging"
• "fondere"
• "selezionare"
• "sommare"
• "sostituire"

e altri ancora.

Esempio

Ecco come implementare il semigruppo (number, +) dove + è l'usuale addizione di numeri:

import { Semigroup } from 'fp-ts/Semigroup'

/** number `Semigroup` under addition */
const SemigroupSum: Semigroup<number> = {
  concat: (first, second) => first + second
}

Quiz. Il combinatore concat definito nella demo 01_retry.ts può essere utilizzato per definire una istanza di Semigroup per il tipo RetryPolicy?

Si noti che, fissato un tipo, si possono definire molteplici istanze dell'interfaccia Semigroup.

Per esempio, considerando ancora il tipo number, possiamo definire il semigruppo (number, *) dove * è l'usuale moltiplicazione di numeri:

import { Semigroup } from 'fp-ts/Semigroup'

/** number `Semigroup` under multiplication */
const SemigroupProduct: Semigroup<number> = {
  concat: (first, second) => first * second
}

Un altro esempio, con le stringhe questa volta:

import { Semigroup } from 'fp-ts/Semigroup'

const SemigroupString: Semigroup<string> = {
  concat: (first, second) => first + second
}

E ancora altri due esempi, con boolean:

import { Semigroup } from 'fp-ts/Semigroup'

const SemigroupAll: Semigroup<boolean> = {
  concat: (first, second) => first && second
}

const SemigroupAny: Semigroup<boolean> = {
  concat: (first, second) => first || second
}

La funzione concatAll

Per definizione concat combina solo due elementi di A alla volta, è possibile combinare più elementi?

La funzione concatAll prende in input una istanza di semigruppo, un valore iniziale e un array di elementi da combinare:

import * as S from 'fp-ts/Semigroup'
import * as N from 'fp-ts/number'

const sum = S.concatAll(N.SemigroupSum)(2)

console.log(sum([1, 2, 3, 4])) // => 12

const product = S.concatAll(N.SemigroupProduct)(3)

console.log(product([1, 2, 3, 4])) // => 72

Quiz. Perché ho bisogno di un valore iniziale?

Esempio

Come altri esempi di applicazione di concatAll, possiamo reimplementare alcune popolari funzioni della standard library di JavaScript:

import * as B from 'fp-ts/boolean'
import { concatAll } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/struct'

const every = <A>(predicate: (a: A) => boolean) => (
  as: ReadonlyArray<A>
): boolean => concatAll(B.SemigroupAll)(true)(as.map(predicate))

const some = <A>(predicate: (a: A) => boolean) => (
  as: ReadonlyArray<A>
): boolean => concatAll(B.SemigroupAny)(false)(as.map(predicate))

const assign: (as: ReadonlyArray<object>) => object = concatAll(
  S.getAssignSemigroup<object>()
)({})

Quiz. La seguente istanza è "legale" (ovvero rispetta le leggi dei semigruppi)?

import { Semigroup } from 'fp-ts/Semigroup'

/** Always return the first argument */
const first = <A>(): Semigroup<A> => ({
  concat: (first, _second) => first
})

Quiz. La seguente istanza è legale?

import { Semigroup } from 'fp-ts/Semigroup'

/** Always return the second argument */
const last = <A>(): Semigroup<A> => ({
  concat: (_first, second) => second
})

Il semigruppo duale

Data una istanza di semigruppo, è possibile ricavarne un'altra semplicemente scambiando l'ordine in cui sono combinati gli elementi:

import { pipe } from 'fp-ts/function'
import { Semigroup } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

// questo è un combinatore di semigruppi...
const reverse = <A>(S: Semigroup<A>): Semigroup<A> => ({
  concat: (first, second) => S.concat(second, first)
})

pipe(S.Semigroup.concat('a', 'b'), console.log) // => 'ab'
pipe(reverse(S.Semigroup).concat('a', 'b'), console.log) // => 'ba'

Quiz. Questo combinatore ha senso perché in generale l'operazione concat non è commutativa, ovvero non è detto che valga sempre concat(x, y) = concat(y, x), potete portare un esempio in cui concat non è commutativa? E uno in cui è commutativa?

Semigruppo prodotto

Proviamo a definire delle istanze di semigruppo per tipi più complessi:

import * as N from 'fp-ts/number'
import { Semigroup } from 'fp-ts/Semigroup'

// modella un vettore che parte dall'origine
type Vector = {
  readonly x: number
  readonly y: number
}

// modella la somma di due vettori
const SemigroupVector: Semigroup<Vector> = {
  concat: (first, second) => ({
    x: N.SemigroupSum.concat(first.x, second.x),
    y: N.SemigroupSum.concat(first.y, second.y)
  })
}

Esempio

const v1: Vector = { x: 1, y: 1 }
const v2: Vector = { x: 1, y: 2 }

console.log(SemigroupVector.concat(v1, v2)) // => { x: 2, y: 3 }

Troppo boilerplate? La buona notizia è che la teoria matematica che sta dietro al concetto di semigruppo ci dice che possiamo costruire una istanza di semigruppo per una struct come Vector se siamo in grado di fornire una istanza di semigruppo per ogni suo campo.

Convenientemente il modulo fp-ts/Semigroup esporta una combinatore struct:

import { struct } from 'fp-ts/Semigroup'

// modella la somma di due vettori
const SemigroupVector: Semigroup<Vector> = struct({
  x: N.SemigroupSum,
  y: N.SemigroupSum
})

Nota. Esiste un combinatore simile a struct ma che lavora con le tuple: tuple

import * as N from 'fp-ts/number'
import { Semigroup, tuple } from 'fp-ts/Semigroup'

// modella un vettore che parte dall'origine
type Vector = readonly [number, number]

// modella la somma di due vettori
const SemigroupVector: Semigroup<Vector> = tuple(N.SemigroupSum, N.SemigroupSum)

const v1: Vector = [1, 1]
const v2: Vector = [1, 2]

console.log(SemigroupVector.concat(v1, v2)) // => [2, 3]

Quiz. E' vero che dato un semigruppo per A e scelto un qualsiasi elemento middle di A, se lo infilo tra i due parametri di concat, ottengo ancora un semigruppo?

import { pipe } from 'fp-ts/function'
import { Semigroup } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

export const intercalate = <A>(middle: A) => (
  S: Semigroup<A>
): Semigroup<A> => ({
  concat: (first, second) => S.concat(S.concat(first, middle), second)
})

const SemigroupIntercalate = pipe(S.Semigroup, intercalate('|'))

pipe(
  SemigroupIntercalate.concat('a', SemigroupIntercalate.concat('b', 'c')),
  console.log
) // => 'a|b|c'

Non riesco a trovare una istanza!

L'associatività è una proprietà molto forte, cosa accade se, dato un particolare tipo A, non si riesce a trovare una operazione associativa su A?

Supponiamo di avere un tipo User definito come:

type User = {
  readonly id: number
  readonly name: string
}

e che nel mio database ci siano molte copie dello stesso User (per esempio potrebbero essere la storia della sue modifiche)

// API interne
declare const getCurrent: (id: number) => User
declare const getHistory: (id: number) => ReadonlyArray<User>

e di dover disegnare una API pubblica

export declare const getUser: (id: number) => User

che tiene conto di tutte le copie in base a qualche criterio, per esempio il criterio potrebbe essere restituire la copia più recente, oppure quella meno recente, oppure sempre la copia corrente, ecc...

Naturalmente possiamo definire delle API specifiche per ogni criterio, dunque:

export declare const getMostRecentUser: (id: number) => User
export declare const getLeastRecentUser: (id: number) => User
export declare const getCurrentUser: (id: number) => User
// ecc...

In questa sede però vorrei parlare del problema di design dal punto di vista più generale possibile.

Dunque per restituire un valore di tipo User devo considerare tutte le copie a farne un "merge" (o una "selezione").

In altre parole possiamo modellare il criterio con un semigruppo!

Tuttavia non è evidente cosa voglia dire "fare merge di due utenti", né come questa operazione di merge possa essere associativa.

Potete sempre definire una istanza di semigruppo per un qualsiasi tipo costruendo una istanza di semigruppo non per A ma per ReadonlyNonEmptyArray<A> (array non vuoto di A) chiamata il semigruppo libero di A.

import { Semigroup } from 'fp-ts/Semigroup'

// modella un array non vuoto, ovvero con almeno un elemento
type ReadonlyNonEmptyArray<A> = ReadonlyArray<A> & {
  readonly 0: A
}

// la concatenazione di due array non vuoti è ancora un array non vuoto
const getSemigroup = <A>(): Semigroup<ReadonlyNonEmptyArray<A>> => ({
  concat: (first, second) => [first[0], ...first.slice(1), ...second]
})

e poi mappare gli elementi di A ai "singoletti" di ReadonlyNonEmptyArray<A>, ovvero un array con un solo elemento:

// inserisce un valore in un array non vuoto
const of = <A>(a: A): ReadonlyNonEmptyArray<A> => [a]

Applichiamo questa tecnica al tipo User:

import {
  getSemigroup,
  of,
  ReadonlyNonEmptyArray
} from 'fp-ts/ReadonlyNonEmptyArray'
import { Semigroup } from 'fp-ts/Semigroup'

type User = {
  readonly id: number
  readonly name: string
}

// questo è un semigruppo non per `User` ma per `ReadonlyNonEmptyArray<User>`
const S: Semigroup<ReadonlyNonEmptyArray<User>> = getSemigroup<User>()

declare const user1: User
declare const user2: User
declare const user3: User

// const merge: ReadonlyNonEmptyArray<User>
const merge = S.concat(S.concat(of(user1), of(user2)), of(user3))

// ottengo lo stesso risultato "impacchettando a mano" gli utenti
const merge2: ReadonlyNonEmptyArray<User> = [user1, user2, user3]

Il semigruppo libero di A quindi non è altro che il semigruppo in cui gli elementi sono tutte le possibili sequenze finite e non vuote di elementi di A.

Il semigruppo libero di A può essere visto come un modo lazy di concatenare elementi di A, mantenendo in tal modo tutto il contenuto informativo.

Infatti il valore merge, che contiene [user1, user2, user3], mi dice ancora quali sono gli elementi da concatenare e in che ordine.

Ora ho tre opzioni possibili in fase di design della API getUser:

1. sono in grado di definire un Semigroup<User> e voglio procedere subito al merging

declare const SemigroupUser: Semigroup<User>

export const getUser = (id: number): User => {
  const current = getCurrent(id)
  const history = getHistory(id)
  // procedo subito al merging
  return concatAll(SemigroupUser)(current)(history)
}

2. non sono in grado di definire un Semigroup<User> oppure voglio lasciare come configurabile la strategia di merging, perciò la chiedo al consumer della mia API

export const getUser = (SemigroupUser: Semigroup<User>) => (
  id: number
): User => {
  const current = getCurrent(id)
  const history = getHistory(id)
  // procedo subito al merging
  return concatAll(SemigroupUser)(current)(history)
}

3. non sono in grado di definire un Semigroup<User> e non voglio chiederlo al consumer della mia API

Questo è il caso in cui il semigruppo libero di User ci può venire in aiuto.

export const getUser = (id: number): ReadonlyNonEmptyArray<User> => {
  const current = getCurrent(id)
  const history = getHistory(id)
  // decido di NON procedere al merging e restituisco il semigruppo libero di `User`
  return [current, ...history]
}

Inoltre, anche se ho a disposizione una istanza di semigruppo per A, potrei decidere ugualmente di usare il suo semigruppo libero per i seguenti motivi:

• evita di eseguire computazioni possibilmente inutili (supponete che il merging sia costoso)
• evita di passare in giro l'istanza di semigruppo
• permette ancora al consumer delle mie API di stabilire la strategia di merging (usando concatAll)

Semigruppi derivabili da un ordinamento

Dato che number è totalmente ordinabile (ovvero dati due qualsiasi numeri x e y, una tra le seguenti condizioni vale: x <= y oppure y <= x) possiamo definire due sue ulteriori istanze di semigruppo usando min e max come operazioni:

import { Semigroup } from 'fp-ts/Semigroup'

const SemigroupMin: Semigroup<number> = {
  concat: (first, second) => Math.min(first, second)
}

const SemigroupMax: Semigroup<number> = {
  concat: (first, second) => Math.max(first, second)
}

Quiz. Perché è importante che number sia totalmente ordinabile?

Sarebbe utile poter definire questi due semigruppi (SemigroupMin e SemigroupMax) anche per altri tipi oltre a number.

È possibile catturare la nozione di totalmente ordinabile per altri tipi? Per farlo dobbiamo prima di tutto catturare la nozione di uguaglianza.

Modellare l'uguaglianza con Eq

Ancora una volta possiamo modellare la nozione di uguaglianza tramite una interface di TypeScript:

interface Eq<A> {
  readonly equals: (first: A, second: A) => boolean
}

Intuitivamente:

• se equals(x, y) è uguale a true allora diciamo che x e y sono uguali
• se equals(x, y) è uguale a false allora diciamo che x e y sono diversi

Esempio

Proviamo a definire una istanza di Eq per il tipo number:

import { Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'

const EqNumber: Eq<number> = {
  equals: (first, second) => first === second
}

pipe(EqNumber.equals(1, 1), console.log) // => true
pipe(EqNumber.equals(1, 2), console.log) // => false

Devono valere le seguenti leggi:

1. Reflexivity: equals(a, a) === true, per ogni a in A
2. Symmetry: equals(a, b) === equals(b, a), per ogni a, b in A
3. Transitivity: se equals(a, b) === true e equals(b, c) === true, allora equals(a, c) === true, per ogni a, b, c in A

Quiz. Ha senso un combinatore reverse: <A>(E: Eq<A>) => Eq<A>?

Quiz. Ha senso un combinatore not: <A>(E: Eq<A>) => Eq<A>?

import { Eq } from 'fp-ts/Eq'

export const not = <A>(E: Eq<A>): Eq<A> => ({
  equals: (first, second) => !E.equals(first, second)
})

Esempio

Come primo esempio di utilizzo dell'astrazione Eq definiamo una funzione elem che indica se un dato valore è un elemento di un ReadonlyArray:

import { Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'

// restituisce `true` se l'elemento `a` compare nella lista `as`
const elem = <A>(E: Eq<A>) => (a: A) => (as: ReadonlyArray<A>): boolean =>
  as.some((e) => E.equals(a, e))

pipe([1, 2, 3], elem(N.Eq)(2), console.log) // => true
pipe([1, 2, 3], elem(N.Eq)(4), console.log) // => false

Ma perché non usare il metodo nativo includes degli array?

console.log([1, 2, 3].includes(2)) // => true
console.log([1, 2, 3].includes(4)) // => false

Per avere una risposta proviamo a definire una istanza per un tipo più complesso:

import { Eq } from 'fp-ts/Eq'

type Point = {
  readonly x: number
  readonly y: number
}

const EqPoint: Eq<Point> = {
  equals: (first, second) => first.x === second.x && first.y === second.y
}

console.log(EqPoint.equals({ x: 1, y: 2 }, { x: 1, y: 2 })) // => true
console.log(EqPoint.equals({ x: 1, y: 2 }, { x: 1, y: -2 })) // => false

e utilizzare fianco a fianco elem e includes

const points: ReadonlyArray<Point> = [
  { x: 0, y: 0 },
  { x: 1, y: 1 },
  { x: 2, y: 2 }
]

const search: Point = { x: 1, y: 1 }

console.log(points.includes(search)) // => false :(
console.log(pipe(points, elem(EqPoint)(search))) // => true :)

Quiz (JavaScript). Come mai usando includes ottengo false?

Aver catturato il concetto di uguaglianza è fondamentale, soprattutto in un linguaggio come JavaScript in cui alcune strutture dati possiedono delle API poco usabili rispetto ad un concetto di uguaglianza custom. E' anche il caso di Set per esempio:

type Point = {
  readonly x: number
  readonly y: number
}

const points: Set<Point> = new Set([{ x: 0, y: 0 }])

points.add({ x: 0, y: 0 })

console.log(points)
// => Set { { x: 0, y: 0 }, { x: 0, y: 0 } }

Dato che Set utilizza === ("strict equality") come concetto di uguaglianza (fisso), points ora contiene due copie identiche di { x: 0, y: 0 }, un risultato certo non voluto. Conviene perciò definire una nuova API per aggiungere un elemento ad un Set che sfrutti l'astrazione Eq.

Quiz. Che firma potrebbe avere questa nuova API?

Per definire EqPoint occorre troppo boilerplate? La buona notizia è che la teoria ci dice che possiamo costruire una istanza di Eq per una struct come Point se siamo in grado di fornire una istanza di Eq per ogni suo campo.

Convenientemente il modulo fp-ts/Eq esporta un combinatore struct:

import { Eq, struct } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'

type Point = {
  readonly x: number
  readonly y: number
}

const EqPoint: Eq<Point> = struct({
  x: N.Eq,
  y: N.Eq
})

Nota. Esiste un combinatore simile a struct ma che lavora con le tuple: tuple

import { Eq, tuple } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'

type Point = readonly [number, number]

const EqPoint: Eq<Point> = tuple(N.Eq, N.Eq)

console.log(EqPoint.equals([1, 2], [1, 2])) // => true
console.log(EqPoint.equals([1, 2], [1, -2])) // => false

Ci sono altri combinatori messi a disposizione da fp-ts, ecco un combinatore che permette di derivare una istanza di Eq per i ReadonlyArray:

import { Eq, tuple } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'
import * as RA from 'fp-ts/ReadonlyArray'

type Point = readonly [number, number]

const EqPoint: Eq<Point> = tuple(N.Eq, N.Eq)

const EqPoints: Eq<ReadonlyArray<Point>> = RA.getEq(EqPoint)

Come succede con i semigruppi, potete definire più di una istanza di Eq per lo stesso tipo. Supponiamo di aver modellato un utente con il seguente tipo

type User = {
  readonly id: number
  readonly name: string
}

possiamo definire una istanza di Eq "standard" usando il combinatore struct:

import { Eq, struct } from 'fp-ts/Eq'
import * as N from 'fp-ts/number'
import * as S from 'fp-ts/string'

type User = {
  readonly id: number
  readonly name: string
}

const EqStandard: Eq<User> = struct({
  id: N.Eq,
  name: S.Eq
})

Nota. In un linguaggio come Haskell l'istanza di Eq standard per una struct come User può essere prodotta automaticamente dal compilatore.

data User = User Int String
     deriving (Eq)

Potremmo però avere delle situazioni particolari in cui ci può interessare avere un tipo di uguaglianza tra utenti differente, per esempio potremmo considerare due utenti uguali se hanno il campo id uguale

/** due utenti sono uguali se sono uguali il loro campi `id` */
const EqID: Eq<User> = {
  equals: (first, second) => N.Eq.equals(first.id, second.id)
}

Avendo "reificato" l'azione di confrontare due valori, cioè l'abbiamo resa concreta rappresentandola come una struttura dati, possiamo manipolare programmaticamente le istanze di Eq come facciamo per altre strutture dati, vediamo un esempio.

Esempio. Invece di definire EqId "a mano", possiamo utilizzare l'utile combinatore contramap: data una istanza di Eq per A e una funzione da B ad A, possiamo derivare una istanza di Eq per B

import { Eq, struct, contramap } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import * as S from 'fp-ts/string'

type User = {
  readonly id: number
  readonly name: string
}

const EqStandard: Eq<User> = struct({
  id: N.Eq,
  name: S.Eq
})

const EqID: Eq<User> = pipe(
  N.Eq,
  contramap((_: User) => _.id)
)

console.log(
  EqStandard.equals({ id: 1, name: 'Giulio' }, { id: 1, name: 'Giulio Canti' })
) // => false (le proprietà `name` sono diverse)

console.log(
  EqID.equals({ id: 1, name: 'Giulio' }, { id: 1, name: 'Giulio Canti' })
) // => true (nonostante le proprietà `name` siano diverse)

console.log(EqID.equals({ id: 1, name: 'Giulio' }, { id: 2, name: 'Giulio' }))
// => false (nonostante le proprietà `name` siano uguali)

Quiz. Dato un tipo A, è possibile definire una istanza di semigruppo per Eq<A>? Cosa potrebbe rappresentare?

Modellare l'ordinamento con Ord

Ora che abbiamo modellato il concetto di uguaglianza, vediamo in questo capitolo come modellare il concetto di ordinamento.

Una relazione d'ordine totale può essere modellata in TypeScript con i seguenti tipi:

import { Eq } from 'fp-ts/Eq'

type Ordering = -1 | 0 | 1

interface Ord<A> extends Eq<A> {
  readonly compare: (first: A, second: A) => Ordering
}

Intuitivamente:

• x < y se e solo se compare(x, y) = -1
• x = y se e solo se compare(x, y) = 0
• x > y se e solo se compare(x, y) = 1

Esempio

Proviamo a definire una istanza di Ord per il tipo number:

import { Ord } from 'fp-ts/Ord'

const OrdNumber: Ord<number> = {
  equals: (first, second) => first === second,
  compare: (first, second) => (first < second ? -1 : first > second ? 1 : 0)
}

Devono valere le seguenti leggi:

1. Reflexivity: compare(x, x) <= 0, per ogni x in A
2. Antisymmetry: se compare(x, y) <= 0 e compare(y, x) <= 0 allora x = y, per ogni x, y in A
3. Transitivity: se compare(x, y) <= 0 e compare(y, z) <= 0 allora compare(x, z) <= 0, per ogni x, y, z in A

In più compare deve essere compatibile con l'operazione equals di Eq:

compare(x, y) === 0 se e solo se equals(x, y) === true, per ogni x, y in A

Nota. equals può essere derivato da compare nel modo seguente

equals: (first, second) => compare(first, second) === 0

Perciò il modulo fp-ts/Ord esporta un comodo helper fromCompare che permette di definire una istanza di Ord semplicemente specificando la funzione compare:

import { Ord, fromCompare } from 'fp-ts/Ord'

const OrdNumber: Ord<number> = fromCompare((first, second) =>
  first < second ? -1 : first > second ? 1 : 0
)

Quiz. E' possibile definire un ordinamento per il gioco Sasso-Carta-Forbice compatibile con le mosse vincenti (ovvero move1 <= move2 se move2 batte move1)?

Come primo esempio di utilizzo definiamo una funzione sort che ordina gli elementi di un ReadonlyArray

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord } from 'fp-ts/Ord'

export const sort = <A>(O: Ord<A>) => (
  as: ReadonlyArray<A>
): ReadonlyArray<A> => as.slice().sort(O.compare)

pipe([3, 1, 2], sort(N.Ord), console.log) // => [1, 2, 3]

Quiz (JavaScript). Perché nell'implementazione viene chiamato il metodo slice?

Come altro esempio di utilizzo definiamo una funzione min che restituisce il minimo fra due valori:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord } from 'fp-ts/Ord'

const min = <A>(O: Ord<A>) => (second: A) => (first: A): A =>
  O.compare(first, second) === 1 ? second : first

pipe(2, min(N.Ord)(1), console.log) // => 1

L'ordinamento duale

Così come possiamo invertire l'operazione concat per ottenere il semigruppo duale (con il combinatore reverse), così anche l'operazione compare può essere invertita per ottenere l'ordinamento duale.

Definiamo perciò il combinatore reverse per Ord:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { fromCompare, Ord } from 'fp-ts/Ord'

export const reverse = <A>(O: Ord<A>): Ord<A> =>
  fromCompare((first, second) => O.compare(second, first))

Come esempio di utilizzo di reverse possiamo ricavare la funzione max dalla funzione min:

import { flow, pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord, reverse } from 'fp-ts/Ord'

const min = <A>(O: Ord<A>) => (second: A) => (first: A): A =>
  O.compare(first, second) === 1 ? second : first

// const max: <A>(O: Ord<A>) => (second: A) => (first: A) => A
const max = flow(reverse, min)

pipe(2, max(N.Ord)(1), console.log) // => 2

La totalità dell'ordinamento (ovvero dati due qualsiasi x e y, una tra le seguenti condizioni vale: x <= y oppure y <= x) può sembrare ovvia quando parliamo di numeri, ma non è sempre così. Consideriamo un caso più complesso

type User = {
  readonly name: string
  readonly age: number
}

Non è così chiaro stabilire quando un utente "è minore o uguale" ad un altro utente.

Come possiamo definire un Ord<User>?

Dipende davvero dal contesto, ma una possibile scelta potrebbe essere quella per esempio di ordinare gli utenti a seconda della loro età:

import * as N from 'fp-ts/number'
import { fromCompare, Ord } from 'fp-ts/Ord'

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = fromCompare((first, second) =>
  N.Ord.compare(first.age, second.age)
)

Possiamo eliminare un po' di boilerplate usando il combinatore contramap: data una istanza di Ord per A e una funzione da B ad A, possiamo derivare una istanza di Ord per B:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { contramap, Ord } from 'fp-ts/Ord'

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = pipe(
  N.Ord,
  contramap((_: User) => _.age)
)

Ora possiamo ottenere il più giovane di due utenti usando la funzione min che abbiamo precedentemente definito

// const getYounger: (second: User) => (first: User) => User
const getYounger = min(byAge)

pipe(
  { name: 'Guido', age: 50 },
  getYounger({ name: 'Giulio', age: 47 }),
  console.log
) // => { name: 'Giulio', age: 47 }

Quiz. Nel modulo fp-ts/ReadonlyMap è contenuta la seguente API

/**
 * Get a sorted `ReadonlyArray` of the keys contained in a `ReadonlyMap`.
 */
declare const keys: <K>(
  O: Ord<K>
) => <A>(m: ReadonlyMap<K, A>) => ReadonlyArray<K>

per quale motivo questa API richiede un Ord<K>?

Torniamo finalmente al quesito iniziale: definire i due semigruppi SemigroupMin e SemigroupMax anche per altri tipi oltre a number:

import { Semigroup } from 'fp-ts/Semigroup'

const SemigroupMin: Semigroup<number> = {
  concat: (first, second) => Math.min(first, second)
}

const SemigroupMax: Semigroup<number> = {
  concat: (first, second) => Math.max(first, second)
}

Ora che abbiamo a disposizione l'astrazione Ord possiamo farlo:

import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { Ord, contramap } from 'fp-ts/Ord'
import { Semigroup } from 'fp-ts/Semigroup'

export const min = <A>(O: Ord<A>): Semigroup<A> => ({
  concat: (first, second) => (O.compare(first, second) === 1 ? second : first)
})

export const max = <A>(O: Ord<A>): Semigroup<A> => ({
  concat: (first, second) => (O.compare(first, second) === 1 ? first : second)
})

type User = {
  readonly name: string
  readonly age: number
}

const byAge: Ord<User> = pipe(
  N.Ord,
  contramap((_: User) => _.age)
)

console.log(
  min(byAge).concat({ name: 'Guido', age: 50 }, { name: 'Giulio', age: 47 })
) // => { name: 'Giulio', age: 47 }
console.log(
  max(byAge).concat({ name: 'Guido', age: 50 }, { name: 'Giulio', age: 47 })
) // => { name: 'Guido', age: 50 }

Esempio

Ricapitoliamo tutto con un esempio finale (adattato da Fantas, Eel, and Specification 4: Semigroup)

Supponiamo di dover costruire un sistema in cui, in un database, sono salvati dei record di un cliente, modellati nel seguente modo

interface Customer {
  readonly name: string
  readonly favouriteThings: ReadonlyArray<string>
  readonly registeredAt: number // since epoch
  readonly lastUpdatedAt: number // since epoch
  readonly hasMadePurchase: boolean
}

Per qualche ragione potreste finire per avere dei record duplicati per la stessa persona.

Abbiamo bisogno di una strategia di merging. Ma questo è proprio quello di cui si occupano i semigruppi!

import * as B from 'fp-ts/boolean'
import { pipe } from 'fp-ts/function'
import * as N from 'fp-ts/number'
import { contramap } from 'fp-ts/Ord'
import * as RA from 'fp-ts/ReadonlyArray'
import { max, min, Semigroup, struct } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

interface Customer {
  readonly name: string
  readonly favouriteThings: ReadonlyArray<string>
  readonly registeredAt: number // since epoch
  readonly lastUpdatedAt: number // since epoch
  readonly hasMadePurchase: boolean
}

const SemigroupCustomer: Semigroup<Customer> = struct({
  // keep the longer name
  name: max(pipe(N.Ord, contramap(S.size))),
  // accumulate things
  favouriteThings: RA.getSemigroup<string>(),
  // keep the least recent date
  registeredAt: min(N.Ord),
  // keep the most recent date
  lastUpdatedAt: max(N.Ord),
  // boolean semigroup under disjunction
  hasMadePurchase: B.SemigroupAny
})

console.log(
  SemigroupCustomer.concat(
    {
      name: 'Giulio',
      favouriteThings: ['math', 'climbing'],
      registeredAt: new Date(2018, 1, 20).getTime(),
      lastUpdatedAt: new Date(2018, 2, 18).getTime(),
      hasMadePurchase: false
    },
    {
      name: 'Giulio Canti',
      favouriteThings: ['functional programming'],
      registeredAt: new Date(2018, 1, 22).getTime(),
      lastUpdatedAt: new Date(2018, 2, 9).getTime(),
      hasMadePurchase: true
    }
  )
)
/*
{ name: 'Giulio Canti',
  favouriteThings: [ 'math', 'climbing', 'functional programming' ],
  registeredAt: 1519081200000, // new Date(2018, 1, 20).getTime()
  lastUpdatedAt: 1521327600000, // new Date(2018, 2, 18).getTime()
  hasMadePurchase: true
}
*/

Quiz. Dato un tipo A è possibile definire una istanza di semigruppo per Ord<A>? Cosa potrebbe rappresentare?

Demo

02_ord.ts

Modellare la composizione con i monoidi

Se aggiungiamo una condizione in più alla definizione di un semigruppo, ovvero che esista un elemento empty in A tale che per ogni elemento a in A vale

• Right identity: concat(a, empty) = a
• Left identity: concat(empty, a) = a

allora parliamo di monoide e l'elemento empty viene detto unità (o "elemento neutro").

Come già successo per Magma e Semigroup, i monoidi possono essere modellati con una interface di TypeScript:

import { Semigroup } from 'fp-ts/Semigroup'

interface Monoid<A> extends Semigroup<A> {
  readonly empty: A
}

Molti dei semigruppi che abbiamo visto nelle sezioni precedenti possono essere arricchiti e diventare istanze di Monoid:

import { Monoid } from 'fp-ts/Monoid'

/** number `Monoid` under addition */
const MonoidSum: Monoid<number> = {
  concat: (first, second) => first + second,
  empty: 0
}

/** number `Monoid` under multiplication */
const MonoidProduct: Monoid<number> = {
  concat: (first, second) => first * second,
  empty: 1
}

const MonoidString: Monoid<string> = {
  concat: (first, second) => first + second,
  empty: ''
}

/** boolean monoid under conjunction */
const MonoidAll: Monoid<boolean> = {
  concat: (first, second) => first && second,
  empty: true
}

/** boolean monoid under disjunction */
const MonoidAny: Monoid<boolean> = {
  concat: (first, second) => first || second,
  empty: false
}

Quiz. Nella sezione sui semigruppi abbiamo visto che ReadonlyArray<string> ammette una istanza di Semigroup:

import { Semigroup } from 'fp-ts/Semigroup'

const Semigroup: Semigroup<ReadonlyArray<string>> = {
  concat: (first, second) => first.concat(second)
}

esiste anche l'unità? E' possibile generalizzare il risultato per ReadonlyArray<A> per qualsiasi tipo A?

Quiz (difficile). Dimostrare che, dato un monoide, l'elemento neutro è unico.

La conseguenza pratica è che se avete trovato una unità smettete di cercare!

Ogni monoide è un semigruppo, ma non ogni semigruppo è un monoide.

Esempio

Si consideri il seguente esempio:

import { pipe } from 'fp-ts/function'
import { intercalate } from 'fp-ts/Semigroup'
import * as S from 'fp-ts/string'

const SemigroupIntercalate = pipe(S.Semigroup, intercalate('|'))

console.log(S.Semigroup.concat('a', 'b')) // => 'ab'
console.log(SemigroupIntercalate.concat('a', 'b')) // => 'a|b'
console.log(SemigroupIntercalate.concat('a', '')) // => 'a|'

Notate come non sia possibile trovare un valore empty di tipo string tale che concat(a, empty) = a.

Infine un esempio più "esotico", sulle funzioni:

Esempio

Un endomorfismo è una funzione in cui il tipo in input e il tipo in output coincidono:

type Endomorphism<A> = (a: A) => A

Dato un tipo A, gli endomorfismi su A costituiscono un monoide, tale che:

• l'operazione concat è l'usuale composizione di funzioni
• l'unità è la funzione identità

import { Endomorphism, flow, identity } from 'fp-ts/function'
import { Monoid } from 'fp-ts/Monoid'

export const getEndomorphismMonoid = <A>(): Monoid<Endomorphism<A>> => ({
  concat: flow,
  empty: identity
})

La funzione concatAll

Quando usiamo un monoide invece di un semigruppo, la concatenazione di più elementi è ancora più semplice: non è necessario fornire esplicitamente un valore iniziale.

Quiz. Perché non è necessario fornire un valore iniziale?

import { concatAll } from 'fp-ts/Monoid'
import * as S from 'fp-ts/string'
import * as N from 'fp-ts/number'
import * as B from 'fp-ts/boolean'

console.log(concatAll(N.MonoidSum)([1, 2, 3, 4])) // => 10
console.log(concatAll(N.MonoidProduct)([1, 2, 3, 4])) // => 24
console.log(concatAll(S.Monoid)(['a', 'b', 'c'])) // => 'abc'
console.log(concatAll(B.MonoidAll)([true, false, true])) // => false
console.log(concatAll(B.MonoidAny)([true, false, true])) // => true

Monoide prodotto

Come abbiamo già visto per i semigruppi, è possibile costruire una istanza di monoide per una struct se siamo in grado di fornire una istanza di monoide per ogni suo campo.

Esempio

import { Monoid, struct } from 'fp-ts/Monoid'
import * as N from 'fp-ts/number'

type Point = {
  readonly x: number
  readonly y: number
}

const Monoid: Monoid<Point> = struct({
  x: N.MonoidSum,
  y: N.MonoidSum
})

Nota. Esiste un combinatore simile a struct ma che lavora con le tuple: tuple.

import { Monoid, tuple } from 'fp-ts/Monoid'
import * as N from 'fp-ts/number'

type Point = readonly [number, number]

const Monoid: Monoid<Point> = tuple(N.MonoidSum, N.MonoidSum)

Quiz. E' possibile definire il "monoide libero" di un generico tipo A?

Demo (implementare un sistema per disegnare forme geometriche su un canvas)

03_shapes.ts

Funzioni pure e funzioni parziali

Nel primo capitolo del corso abbiamo visto una definizione informale di funzione pura:

Una funzione pura è una procedura che dato lo stesso input restituisce sempre lo stesso output e non ha alcun side effect osservabile.

Un tale enunciato può lasciare spazio a qualche dubbio (per esempio, che cos'è un "side effect"?)

Vediamo perciò una definizione formale:

Ricordiamo che se X e Y sono due insiemi, allora con X × Y si indica il loro prodotto cartesiano, ovvero l'insieme

X × Y = { (x, y) | x ∈ X, y ∈ Y }

Definizione. Una funzione f: X ⟶ Y è un sottoinsieme f di X × Y tale che per ogni x ∈ X esiste esattamente un y ∈ Y tale che la coppia (x, y) ∈ f.

L'insieme X si dice il dominio di f, Y il suo codominio.

Si noti che l'insieme f deve essere descritto staticamente in fase di definizione della funzione (ovvero gli elementi di quell'insieme non possono variare nel tempo e per nessuna condizione interna o esterna).

Esempio

La funzione double: Nat ⟶ Nat, ove Nat è l'insieme dei numeri naturali, è il sottoinsieme del prodotto cartesiano Nat × Nat dato dalle coppie { (1, 2), (2, 4), (3, 6), ...}.

In TypeScript f potrebbe essere definita così:

const f: Record<number, number> = {
  1: 2,
  2: 4,
  3: 6
  ...
}

Quella dell'esempio viene detta definizione estensionale di una funzione, ovvero si enumerano uno per uno gli elementi del dominio e per ciascuno di essi si indica il corrispondente elemento del codominio. Naturalmente quando l'insieme è infinito, come in questo caso, la definizione può risultare un po' "scomoda".

Si può ovviare a questo problema introducendo quella che viene detta definizione intensionale, ovvero si esprime una condizione che deve valere per tutte le coppie (x, y) appartenenti all'insieme f, ovvero y = x * 2. Questa è la forma familiare con cui scriviamo la funzione double e come la definiamo in TypeScript:

const double = (x: number): number => x * 2

La definizione di funzione come sottoinsieme di un prodotto cartesiano mostra come in matematica tutte le funzioni siano pure: non c'è azione, modifica di stato o modifica degli elementi (che sono considerati immutabili) degli insiemi coinvolti. Nella programmazione funzionale l'implementazione delle funzioni deve tendere a questo modello ideale.

Quiz. Quali delle seguenti procedure sono funzioni pure?

const coefficient1 = 2
export const f1 = (n: number) => n * coefficient1

// ------------------------------------------------------

let coefficient2 = 2
export const f2 = (n: number) => n * coefficient2++

// ------------------------------------------------------

let coefficient3 = 2
export const f3 = (n: number) => n * coefficient3

// ------------------------------------------------------

export const f4 = (n: number) => {
  const out = n * 2
  console.log(out)
  return out
}

// ------------------------------------------------------

interface User {
  readonly id: number
  readonly name: string
}

export declare const f5: (id: number) => Promise<User>

// ------------------------------------------------------

import * as fs from 'fs'

export const f6 = (path: string): string =>
  fs.readFileSync(path, { encoding: 'utf8' })

// ------------------------------------------------------

export const f7 = (
  path: string,
  callback: (err: Error | null, data: string) => void
): void => fs.readFile(path, { encoding: 'utf8' }, callback)

Che una funzione sia pura non implica necessariamente che sia bandita la mutabilità, localmente è ammissibile se non esce dai confini della implementazione.

Esempio (Implementazione della funzione concatAll dei monoidi)

import { Monoid } from 'fp-ts/Monoid'

const concatAll = <A>(M: Monoid<A>) => (as: ReadonlyArray<A>): A => {
  let out: A = M.empty // <= mutabilità locale
  for (const a of as) {
    out = M.concat(out, a)
  }
  return out
}

L'obbiettivo vero è sempre quello di garantire la proprietà fondamentale di trasparenza referenziale.

Il contratto che stipuliamo con l'utente della nostra API è definito dalla sua firma:

declare const concatAll: <A>(M: Monoid<A>) => (as: ReadonlyArray<A>) => A

e dalla promessa di rispettare la trasparenza referenziale, i dettagli tecnici di come la funzione è concretamente implementata non interessano e non sono sotto esame, c'è quindi la massima libertà.

Dunque come si definisce un "side effect"? Semplicemente negando la trasparenza referenziale:

Una espressione contiene un "side effect" se non gode della trasparenza referenziale.

Non solo le funzioni appoggiano sul primo dei due pilastri della programmazione funzionale, ma sono un esempio anche del secondo pilastro: la composizione.

Infatti le funzioni compongono:

Definizione. Siano f: Y ⟶ Z e g: X ⟶ Y due funzioni, allora la funzione h: X ⟶ Z definita da

h(x) = f(g(x))

si dice composizione di f e g e si scrive h = f ∘ g

Si noti che affinché due funzioni f e g possano comporre, il dominio di f deve coincidere col codominio di g.

Definizione. Una funzione parziale è una funzione che non è definita per tutti i valori del dominio.

Viceversa una funzione definita per tutti i valori del dominio è detta totale.

Esempio

// Get the first element of a `ReadonlyArray`
declare const head: <A>(as: ReadonlyArray<A>) => A

Quiz. Perché la funzione head è parziale?

Quiz. La funzione JSON.parse è totale?

parse: (text: string, reviver?: (this: any, key: string, value: any) => any) =>
  any

Quiz. La funzione JSON.stringify è totale?

stringify: (
  value: any,
  replacer?: (this: any, key: string, value: any) => any,
  space?: string | number
) => string

In ambito funzionale si tende a definire solo funzioni pure e totali (d'ora in poi userò il termine "funzione" come sinonimo di "funzione pura e totale"), quindi come ci si deve comportare se si ha a che fare con una funzione parziale?

Fortunatamente una funzione parziale f: X ⟶ Y può essere sempre ricondotta ad una funzione totale aggiungendo al codominio un valore speciale non appartenente a Y, chiamiamolo None, e associandolo ad ogni valore di X per cui f non è definita

f': X ⟶ Y ∪ None

Chiamiamo Option(Y) = Y ∪ None.

f': X ⟶ Option(Y)

E' possibile definire Option(Y) in TypeScript? Nei prossimi due capitoli vedremo come poterlo fare.

Algebraic Data Types

Un buon primo passo quando si sta construendo una nuova applicazione è quello di definire il suo modello di dominio. TypeScript offre molti strumenti che aiutano in questo compito. Gli Algebraic Data Types (abbreviato in ADT) sono uno di questi strumenti.

Che cos'è un algebraic Data Types?

In computer programming, especially functional programming and type theory, an algebraic data type is a kind of composite type, i.e., a type formed by combining other types.

Due famiglie comuni di algebraic data types sono: product types e sum types.

Cominciamo da quelli più familiari: i product type.

Product types

Un product type è una collezione di tipi T_i indicizzati da un insieme I.

Due membri comuni di questa famiglia sono le n-tuple, dove I è un intervallo di numeri naturali:

type Tuple1 = [string] // I = [0]
type Tuple2 = [string, number] // I = [0, 1]
type Tuple3 = [string, number, boolean] // I = [0, 1, 2]

// Accessing by index
type Fst = Tuple2[0] // string
type Snd = Tuple2[1] // number

e le struct, ove I è un insieme di label:

// I = {"name", "age"}
interface Person {
  name: string
  age: number
}

// Accessing by label
type Name = Person['name'] // string
type Age = Person['age'] // number

I product type possono essere polimorfici.

Esempio

//                ↓ type parameter
type HttpResponse<A> = {
  readonly code: number
  readonly body: A
}

Da dove viene il nome "product types"?

Se indichiamo con C(A) il numero di abitanti del tipo A, chiamata cardinalità, allora vale la seguente uguaglianza:

C([A, B]) = C(A) * C(B)

la cardinalità del prodotto è il prodotto delle cardinalità

Esempio

Il tipo null ha cardinalità 1 perchè ha un solo abitante: null.

Esempio

Il tipo boolean ha cardinalità 2 perchè ha due abitanti: true e false.

Esempio

type Hour = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
type Period = 'AM' | 'PM'
type Clock = readonly [Hour, Period]

Il tipo Hour ha 12 abitanti. Il tipo Period ha 2 abitanti. Il tipo Clock ha 12 * 2 = 24 abitanti.

Quiz. Quanti abitanti ha il seguente tipo Clock?

// same as before
type Hour = 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
// same as before
type Period = 'AM' | 'PM'

type Clock = {
  readonly hour: Hour
  readonly period: Period
}

Quando posso usare un product type?

Ogniqualvolta le sue componenti sono indipendenti.

type Clock = readonly [Hour, Period]

Qui Hour e Period sono indipendenti, ovvero il valore di Hour non influisce sul valore di Period e viceversa, tutte le coppie sono legali e hanno senso.

Sum types

Un sum type è una struttura dati che contiene un valore che può assumere diversi tipi (ma fissi). Solo uno dei tipi può essere in uso in un dato momento, e un campo che fa da "tag" indica quale di questi è in uso.

Nella documentazione ufficiale di TypeScript sono indicati col nome discriminated union.

E' importante sottolineare che i membri dell'unione che forma un sum type devono essere disgiunti, ovvero non devono esistere valori che appartengono a più di un membro.

Esempio

Il tipo

type StringsOrNumbers = ReadonlyArray<string> | ReadonlyArray<number>

non è una unione disgiunta perché il valore [] (array vuoto) appartiene ad ambedue i membri dell'unione.

Quiz. La seguente unione è disgiunta?

type Member1 = { readonly a: string }
type Member2 = { readonly b: number }
type MyUnion = Member1 | Member2

In programmazione funzionale si tende ad usare sempre unioni disgiunte.

Fortunatamente in TypeScript c'è un modo sicuro per garantire che una unione sia disgiunta: aggiungere un apposito campo che fa da tag.

Esempio (redux actions)

Il sum type Action modella una porzione delle operazioni che si possono compiere in una todo app.

export type Action =
  | {
      readonly type: 'ADD_TODO'
      readonly text: string
    }
  | {
      readonly type: 'UPDATE_TODO'
      readonly id: number
      readonly text: string
      readonly completed: boolean
    }
  | {
      readonly type: 'DELETE_TODO'
      readonly id: number
    }

Il campo type, essendo obbligatorio e avendo un tipo diverso per ogni membro dell'unione, può essere eletto come tag e assicura che i membri siano disgiunti.

Nota. Il nome del campo che fa da tag è a discrezione dello sviluppatore, non deve essere necessariamente "type" (in fp-ts per esempio, per convenzione si usa il nome "_tag").

Ora che abbiamo visto un po' di esempi possiamo riformulare in modo più esplicito che cos'è un algebraic data type:

In general, an algebraic data type specifies a sum of one or more alternatives, where each alternative is a product of zero or more fields.

I sum type possono essere polimorfici e ricorsivi.

Esempio (linked lists)

//               ↓ type parameter
export type List<A> =
  | { readonly _tag: 'Nil' }
  | { readonly _tag: 'Cons'; readonly head: A; readonly tail: List<A> }
//                                                              ↑ recursion

Quiz (TypeScript). Delle seguenti strutture dati dire se sono dei product type o dei sum type

• ReadonlyArray<A>
• Record<string, A>
• Record<'k1' | 'k2', A>
• ReadonlyMap<string, A>
• ReadonlyMap<'k1' | 'k2', A>

Costruttori

Un sum type con n membri necessita di (almeno) n costruttori, uno per ogni membro.

Esempio (redux action creators)

export type Action =
  | {
      readonly type: 'ADD_TODO'
      readonly text: string
    }
  | {
      readonly type: 'UPDATE_TODO'
      readonly id: number
      readonly text: string
      readonly completed: boolean
    }
  | {
      readonly type: 'DELETE_TODO'
      readonly id: number
    }

export const add = (text: string): Action => ({
  type: 'ADD_TODO',
  text
})

export const update = (
  id: number,
  text: string,
  completed: boolean
): Action => ({
  type: 'UPDATE_TODO',
  id,
  text,
  completed
})

export const del = (id: number): Action => ({
  type: 'DELETE_TODO',
  id
})

Esempio (TypeScript, linked lists)

export type List<A> =
  | { readonly _tag: 'Nil' }
  | { readonly _tag: 'Cons'; readonly head: A; readonly tail: List<A> }

// a nullary constructor can be implemented as a constant
export const nil: List<never> = { _tag: 'Nil' }

export const cons = <A>(head: A, tail: List<A>): List<A> => ({
  _tag: 'Cons',
  head,
  tail
})

// equivalente ad un array [1, 2, 3]
const myList = cons(1, cons(2, cons(3, nil)))

Esempio (Haskell, linked lists)

data List a = Nil | Cons a (List a)

myList :: List Int
myList = Cons 1 (Cons 2 (Cons 3 Nil))

Pattern matching

JavaScript non ha il pattern matching (e quindi neanche TypeScript).

Esempio (Haskell, linked lists)

data List a = Nil | Cons a (List a)

-- restituisce `True` se la lista è vuota
isEmpty :: List a -> Bool
isEmpty Nil = True
isEmpty (Cons _ _) = False

Tuttavia possiamo simulare il pattern matching tramite una funzione match.

Esempio (TypeScript, linked lists)

interface Nil {
  readonly _tag: 'Nil'
}

interface Cons<A> {
  readonly _tag: 'Cons'
  readonly head: A
  readonly tail: List<A>
}

export type List<A> = Nil | Cons<A>

export const match = <R, A>(
  onNil: () => R,
  onCons: (head: A, tail: List<A>) => R
) => (fa: List<A>): R => {
  switch (fa._tag) {
    case 'Nil':
      return onNil()
    case 'Cons':
      return onCons(fa.head, fa.tail)
  }
}

// restituisce `true` se la lista è vuota
export const isEmpty = match(
  () => true,
  () => false
)

// restituisce il primo elemento della lista oppure `undefined`
export const head = match(
  () => undefined,
  (head, _tail) => head
)

// calcola la lunghezza di una lista (ricorsivamente)
export const length: <A>(fa: List<A>) => number = match(
  () => 0,
  (_, tail) => 1 + length(tail)
)

Quiz. Perchè l'API head è sub ottimale?

Nota. TypeScript offre una ottima feature legata ai sum type: exhaustive check. Ovvero il type checker è in grado di determinare se tutti i casi sono stati gestiti nello switch definito nel body della funzione match.

Da dove viene il nome "sum types"?

Vale la seguente uguaglianza:

C(A | B) = C(A) + C(B)

la cardinalità della somma è la somma delle cardinalità

Esempio (the Option type)

interface None {
  readonly _tag: 'None'
}

interface Some<A> {
  readonly _tag: 'Some'
  readonly value: A
}

type Option<A> = None | Some<A>

Dalla formula generale ottengo C(Option<A>) = C(None) + C(Some<A>) = 1 + C(A), da cui possiamo derivare per esempio la cardinalità di Option<boolean>, ovvero 1 + 2 = 3 abitanti:

• { _tag: 'None' }
• { _tag: 'Some', value: true }
• { _tag: 'Some', value: false }

Quando dovrei usare un sum type?

Quando le sue componenti sarebbero dipendenti se implementate con un product type.

Esempio (React props)

import * as React from 'react'

interface Props {
  readonly editable: boolean
  readonly onChange?: (text: string) => void
}

class Textbox extends React.Component<Props> {
  render() {
    if (this.props.editable) {
      // error: Cannot invoke an object which is possibly 'undefined' :(
      this.props.onChange('a')
    }
    return <div />
  }
}

Il problema qui è che Props è modellato come un prodotto ma onChange dipende da editable.

Un sum type è una scelta migliore:

import * as React from 'react'

type Props =
  | {
      readonly type: 'READONLY'
    }
  | {
      readonly type: 'EDITABLE'
      readonly onChange: (text: string) => void
    }

class Textbox extends React.Component<Props> {
  render() {
    switch (this.props.type) {
      case 'EDITABLE':
        this.props.onChange('a') // :)
    }
    return <div />
  }
}

Esempio (node callbacks)

declare function readFile(
  path: string,
  //         ↓ ---------- ↓ CallbackArgs
  callback: (err?: Error, data?: string) => void
): void

Il risultato dell'operazione readFile è modellato con un product type (più precisamente una tupla) che viene passato come input alla funzione callback:

type CallbackArgs = [Error | undefined, string | undefined]

tuttavia le sue componenti sono dipendenti: si riceve un errore oppure una stringa:

Questa API non è modellata seguendo questo adagio:

Make impossible state unrepresentable

Un sum type sarebbe una scelta migliore, ma quale? Vediamo come si gestiscono gli errori in modo funzionale.

Quiz. Recentemente alle API a callback si preferiscono le API che restituiscono una Promise

declare function readFile(path: string): Promise<string>

potete indicare un contro di questa seconda soluzione quando si utilizza un linguaggio a tipi statici come TypeScript?

Functional error handling

Vediamo come gestire gli errori in modo funzionale.

Una funzione che restituisce un errore o lancia una eccezione è un esempio di funzione parziale.

Nel capitolo Funzioni pure e funzioni parziali abbiamo visto che ogni funzione parziale f può essere sempre ricondotta ad una funzione totale f'

f': X ⟶ Option(Y)

Ora che sappiamo qualcosa di più sui sum type in TypeScript possiamo definire Option senza ulteriore indugio.

Il tipo Option

Il tipo Option<A> rappresenta l'effetto di una computazione che può fallire (caso None) oppure restituire un valore di tipo A (caso Some):

// represents a failure
interface None {
  readonly _tag: 'None'
}

// represents a success
interface Some<A> {
  readonly _tag: 'Some'
  readonly value: A
}

type Option<A> = None | Some<A>

Vediamone anche i costruttori e la sua funzione match di "pattern matching":

const none: Option<never> = { _tag: 'None' }

const some = <A>(value: A): Option<A> => ({ _tag: 'Some', value })

const match = <R, A>(onNone: () => R, onSome: (a: A) => R) => (
  fa: Option<A>
): R => {
  switch (fa._tag) {
    case 'None':
      return onNone()
    case 'Some':
      return onSome(fa.value)
  }
}

Il tipo Option può essere usato per evitare di lanciare eccezioni e/o rappresentare i valori opzionali, così possiamo passare da:

//                        this is a lie ↓
const head = <A>(as: ReadonlyArray<A>): A => {
  if (as.length === 0) {
    throw new Error('Empty array')
  }
  return as[0]
}

let s: string
try {
  s = String(head([]))
} catch (e) {
  s = e.message
}

in cui il type system è all'oscuro di un possibile fallimento, a:

import { pipe } from 'fp-ts/function'

//                                      ↓ the type system "knows" that this computation may fail
const head = <A>(as: ReadonlyArray<A>): Option<A> =>
  as.length === 0 ? none : some(as[0])

declare const numbers: ReadonlyArray<number>

const result = pipe(
  head(numbers),
  match(
    () => 'Empty array',
    (n) => String(n)
  )
)

ove la possibilità di errore è codificata nel type system.

Infatti se proviamo ad accedere alla proprietà value di una Option senza controllare in quale dei due casi siamo, il type system ci avverte del possibile errore:

declare const numbers: ReadonlyArray<number>

const result = head(numbers)
result.value // type checker error: Property 'value' does not exist on type 'Option<number>'

L'unico modo per accedere al valore contenuto in una Option è gestire anche il caso di fallimento utilizzando la funzione match

pipe(result, match(
  () => ...handle error...
  (n) => ...go on with my business logic...
))

E' possibile definire delle istanze per le astrazioni che abbiamo visto nei capitoli precedenti? Cominciamo da Eq.

Una istanza per Eq

Supponiamo di avere due valori di tipo Option<string> e volerli confrontare per capire se sono uguali:

import { pipe } from 'fp-ts/function'
import { match, Option } from 'fp-ts/Option'

declare const o1: Option<string>
declare const o2: Option<string>

const result: boolean = pipe(
  o1,
  match(
    // onNone o1
    () =>
      pipe(
        o2,
        match(
          // onNone o2
          () => true,
          // onSome o2
          () => false
        )
      ),
    // onSome o1
    (s1) =>
      pipe(
        o2,
        match(
          // onNone o2
          () => false,
          // onSome o2
          (s2) => s1 === s2 // <= qui uso l'uguaglianza tra stringhe
        )
      )
  )
)

E se avessimo due Option<number>? Il codice sarebbe pressoché uguale tranne alla fine quando confronto i valori contenuti nelle due Option, per i quali userò l'uguaglianza tra numeri.

Ma allora possiamo generalizzare il codice richiedendo all'utente una istanza di Eq per A e quindi derivare una istanza di Eq per Option<A>.

In altre parole possiamo definire un combinatore getEq: dato un Eq<A> il combinatore restituisce un Eq<Option<A>>:

import { Eq } from 'fp-ts/Eq'
import { pipe } from 'fp-ts/function'
import { match, Option, none, some } from 'fp-ts/Option'

export const getEq = <A>(E: Eq<A>): Eq<Option<A>> => ({
  equals: (first, second) =>
    pipe(
      first,
      match(
        () =>
          pipe(
            second,
            match(
              () => true,
              () => false
            )
          ),
        (a1) =>
          pipe(
            second,
            match(
              () => false,
              (a2) => E.equals(a1, a2) // <= qui uso l'uguaglianza tra `A`
            )
          )
      )
    )
})

import * as S from 'fp-ts/string'

const EqOptionString = getEq(S.Eq)

console.log(EqOptionString.equals(none, none)) // => true
console.log(EqOptionString.equals(none, some('b'))) // => false
console.log(EqOptionString.equals(some('a'), none)) // => false
console.log(EqOptionString.equals(some('a'), some('b'))) // => false
console.log(EqOptionString.equals(some('a'), some('a'))) // => true