functional-programming

• Translations
• What is functional programming
• The two pillars of functional programming
  • Referential transparency
  • Composition
• Modelling composition with Semigroups
  • Definition of a Magma
  • Definition of a Semigroup
  • The concatAll function
  • The dual semigroup
  • Semigroup product
  • Finding a Semigroup instance for any type
  • Order-derivable Semigroups
• Modelling equivalence with Eq
  • Modeling ordering relations with Ord
  • Dual Ordering
• Modeling composition through Monoids
  • The concatAll function
  • Product monoid
• Pure and partial functions
• Algebraic Data Types
  • What is an ADT?
  • Product types
    • Why "product" types?
    • When can I use a product type?
  • Sum types
    • Constructors
    • Pattern matching
    • Why "sum" types?
    • When should I use a sum type?
  • Functional error handling
    • The Option type
    • An Eq instance
    • Semigroup and Monoid instances
    • The Either type
• Category theory
  • Definition
    • Part I (Constituents)
    • Part II (Composition)
  • Modeling programming languages with categories
  • A category for TypeScript
  • Composition's core problem
• Functors
  • Functions as programs
  • A boundary that leads to functors
  • Definition
  • Functors and functional error handling
  • Functors compose
  • Contravariant Functors
  • Functors in fp-ts
  • Do functors solve the general problem?
• Applicative functors
  • Currying
  • The ap operation
  • The of operation
  • Applicative functors compose
  • Do applicative functors solve the general problem?
• Monads
  • The problem with nested contexts
  • Monad Definition
  • The Kleisli category
  • Defining chain step by step
  • Manipulating programs

This repo introduces functional programming concepts using TypeScript and possibly libraries in the fp-ts ecosystem.

This fork is an edited translation of Giulio Canti's "Introduction to Functional Programming (Italian)". The author uses the original as a reference and supporting material for his lectures and workshops on functional programming.

The purpose of the edits is to expand on the material without changing the concepts nor structure, for more information about the edit's goals see the CONTRIBUTING file.

Translations

• Simplified Chinese and Japanese by @YiCChi

What is functional programming

Functional Programming is programming with pure functions. Mathematical functions.

A quick search on the internet may lead you to the following definition:

A (pure) function is a procedure that given the same input always return the same output without any observable side-effect.

The term "side effect" does not yet have any specific meaning (we'll see in the future how to give a formal definition), what matters is to have some sort of intuition, think about opening a file or writing into a database.

For the time being we can limit ourselves to say that a side effect is anything a function does besides returning a value.

What is the structure of a program that uses exclusively pure functions?

A functional program tends to be written like a pipeline:

const program = pipe(
  input,
  f1, // pure function
  f2, // pure function
  f3, // pure function
  ...
)

What happens here is that input is passed to the first function f1, which returns a value that is passed to the second function f2, which returns a value that is passed as an argument to the third function f3, and so on.

Demo

00_pipe_and_flow.ts

We'll see how functional programming provides us with tools to structure our code in that style.

Other than understanding what functional programming is, it is also essential to understand what is it's goal.

Functional programming's goal is to tame a system's complexity through the use of formal models, and to give careful attention to code's properties and refactoring ease.

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

What does it mean to give careful attention to code's properties? Let's see with an example:

Example

Why can we say that the Array's map method is "more functional" than a for loop?

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

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

// result: I want an array where each `xs`' element is doubled
const ys: Array = []
for (let i = 0; i  See the [answer here](src/quiz-answers/for-loop.md)

Let's rewrite the same exercise using `map`.

```ts
// input
const xs: Array = [1, 2, 3]

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

// result: I want an array where each `xs`' element is doubled
const ys: Array = xs.map(double)

…

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

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

The expression double(2) has the referential transparency property because it is replaceable with its value, the number 4.

Thus I can proceed with the following refactor

const x = 4
const y = x

Not every expression is referentially transparent, let's see an example.

Example (referential transparency implies not throwing exceptions)

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

const x = inverse(0) + 1

I can't replace inverse(0) with its value, thus it is not referentially transparent.

Example (referential transparency requires the use of immutable data structures)

const xs = [1, 2, 3]

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

append(xs)

const ys = xs

On the last line I cannot replace xs with its initial value [1, 2, 3] since it has been changed by calling append.

Why is referential transparency so important? Because it allows us to:

• reason about code locally, there is no need to know external context in order to understand a fragment of code
• refactor without changing our system's behaviour

Quiz. Suppose we have the following program:

// In TypeScript `declare` allows to introduce a definition without requiring an implementation
declare const question: (message: string) => Promise

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

Can I refactor in this way? Does the program's behavior change or is it going to change?

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

…

ts
combinator: Thing -> Thing

Example. The function double combines two numbers.

The goal of a combinator is to create new Things from Things already defined.

Since the output of a combinator, the new Thing, can be passed around as input to other programs and combinators, we obtain a combinatorial explosion of opportunities, which makes this pattern extremely powerful.

Example

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

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

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

…

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

Thus, we have have the ingredients for an algebra:

• a set A
• an operation on the set A, concat. This operation is said to be closed on the set A which means that whichever elements A we apply the operation on the result will still be an element of A. Since the result is still an A, it can be used again as an input for concat and the operation can be repeated how many times we want. In other words concat is a combinator for the type A.

Let's implement a concrete instance of Magma with A being the number type.

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

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

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

const concat = getPipeableConcat(MagmaSub)

// usage example

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

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

…

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

// or
concat(concat(a, b), c) = concat(a, concat(b, c))

holds for any x, y, z in A.

In layman terms associativity tells us that we do not have to worry about parentheses in expressions and that we can simply write x * y * z (there's no ambiguity).

Example

String concatenation benefits from associativity.

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

Every semigroup is a magma, but not every magma is a semigroup.

Example

The previous MagmaSub is not a semigroup because its concat operation is not associative.

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

const MagmaSub: Magma = {
  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

Semigroups capture the essence of parallelizable operations

If we know that there is such an operation that follows the associativity law, we can further split a computation into two sub computations, each of them could be further split into sub computations.

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

Sub computations can be run in parallel mode.

As for Magma, Semigroups are implemented through a TypeScript interface:

// fp-ts/lib/Semigroup.ts

interface Semigroup extends Magma {}

The following law has to hold true:

• Associativity: If S is a semigroup the following has to hold true:

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

for every x, y, z of type A

Note. Sadly it is not possible to encode this law using TypeScript's type system.

Let's implement a semigroup for some ReadonlyArray:

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

const Semigroup: Se.Semigroup> = {
  concat: (first, second) => first.concat(sec