文件列表:

.prettierrc (90, 2023-06-16)
.vscode/ (0, 2023-06-16)
.vscode/settings.json (57, 2023-06-16)
CONTRIBUTING.md (301, 2023-06-16)
LICENSE (1215, 2023-06-16)
file.txt (6, 2023-06-16)
images/ (0, 2023-06-16)
images/adt.png (40817, 2023-06-16)
images/associativity.png (23684, 2023-06-16)
images/category.png (40522, 2023-06-16)
images/chain.png (28468, 2023-06-16)
images/composition.png (13419, 2023-06-16)
images/contramap.png (43194, 2023-06-16)
images/eilenberg.jpg (17617, 2023-06-16)
images/flatMap.png (54964, 2023-06-16)
images/functor.png (83736, 2023-06-16)
images/identity.png (14208, 2023-06-16)
images/kleisli.jpg (15015, 2023-06-16)
images/kleisli_arrows.png (20306, 2023-06-16)
images/kleisli_category.png (29738, 2023-06-16)
images/kleisli_composition.png (45355, 2023-06-16)
images/liftA2-first-step.png (31202, 2023-06-16)
images/liftA2.png (36646, 2023-06-16)
images/maclane.jpg (16837, 2023-06-16)
images/map.png (27151, 2023-06-16)
images/moggi.jpg (185766, 2023-06-16)
images/monoid.png (175278, 2023-06-16)
images/morphism.png (8707, 2023-06-16)
images/mutable-immutable.jpg (15606, 2023-06-16)
images/objects-morphisms.png (42202, 2023-06-16)
images/of.png (35876, 2023-06-16)
images/semigroup.png (140131, 2023-06-16)
images/semigroupVector.png (43240, 2023-06-16)
images/spoiler.png (102170, 2023-06-16)
images/wadler.jpg (37303, 2023-06-16)
mind-map.png (388211, 2023-06-16)
monad-transformers.md (2682, 2023-06-16)
package-lock.json (304668, 2023-06-16)
... ...

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](https://gcanti.github.io/about.html)'s ["Introduction to Functional Programming (Italian)"](https://github.com/gcanti/functional-programming). 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](/CONTRIBUTING.md) file. ## Read it Online For a best reading experience, [read it online via Gitbook](https://enricopolanski.github.io/functional-programming/). - Quick-access side-bar - In-browser exercises - In-depth examples **Setup** ```sh git clone https://github.com/gcanti/functional-programming.git cd functional-programming npm i ``` # 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**: ```ts 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`](src/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? ```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 = [] for (let i = 0; i <= xs.length; i++) { ys.push(double(xs[i])) } ``` A `for` loop offers a lot of flexibility, I can modify: - the starting index, `let i = 0` - the looping condition, `i < xs.length` - the step change, `i++`. This also implies that I may introduce **errors** and that I have no guarantees about the returned value. **Quiz**. Is the `for loop` correct? > 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) ``` We can note how `map` lacks the same flexibility of a `for loop`, but it offers us some guarantees: - all the elements of the input array will be processed - the resulting array will always have the same number of elements as the starting one In functional programming, where there's an emphasis on code properties rather than implementation details, the `map` operation is interesting **due to its limitations** Think about how easier it is to review a PR that involves `map` rather than a `for` loop. # The two pillars of functional programming Functional programming is based on the following two pillars: - Referential transparency - Composition (as universal design pattern) All of the remaining content derives directly or indirectly from those two points. ## Referential transparency > **Definition**. An **expression** is said to be _referentially transparent_ if it can be replaced with its corresponding value without changing the program's behavior **Example** (referential transparency implies the use of pure functions) ```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 ```ts const x = 4 const y = x ``` Not every expression is referentially transparent, let's see an example. **Example** (referential transparency implies not throwing exceptions) ```ts 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) ```ts 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: ```ts // 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? ```ts const x = await question('What is your name?') const y = x ``` The answer is: there's no way to know without reading `question`'s _implementation_. As you can see, refactoring a program including non-referentially transparent expressions might be challenging. In functional programming, where every expression is referentially transparent, the cognitive load required to make changes is severely reduced. ## Composition Functional programming's fundamental pattern is _composition_: we compose small units of code accomplishing very specific tasks into larger and complex units. An example of a "from the smallest to the largest" composition pattern we can think of: - composing two or more primitive values (numbers or strings) - composing two or more functions - composing entire programs In the very last example we can speak of _modular programming_: > By modular programming I mean the process of building large programs by gluing together smaller programs - Simon Peyton Jones This programming style is achievable through the use of combinators. The term **combinator** refers to the [combinator pattern](https://wiki.haskell.org/Combinator): > 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` The general concept of a combinator is rather vague and it can appear in different forms, but the simplest one is this: ```ts combinator: Thing -> Thing ``` **Example**. The function `double` combines two numbers. The goal of a combinator is to create new *Thing*s from *Thing*s 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** ```ts import { pipe } from 'fp-ts/function' const double = (n: number): number => n * 2 console.log(pipe(2, double, double, double)) // => 16 ``` Thus the usual design you can find in a functional module is: - a model for some type `T` - a small set of "primitives" of type `T` - a set of combinators to combine the primitives in larger structures Let's try to implement such a module: **Demo** [`01_retry.ts`](src/01_retry.ts) As you can see from the previous demo, with merely 3 primitives and two combinators we've been able to express a pretty complex policy. Think at how just adding a single new primitive, or a single combinator to those already defined, adds expressive possibilities exponentially. Of the two combinators in `01_retry.ts` a special mention goes to `concat` since it refers to a very powerful functional programming abstraction: semigroups. # Modelling composition with Semigroups A semigroup is a recipe to combine two, or more, values. A semigroup is an **algebra**, which is generally defined as a specific combination of: - one or more sets - one or more operations on those sets - zero or more laws on the previous operations Algebras are how mathematicians try to capture an idea in its purest form, eliminating everything that is superfluous. > When an algebra is modified the only allowed operations are those defined by the algebra itself according to its own laws Algebras can be thought of as an abstraction of **interfaces**: > When an interface is modified the only allowed operations are those defined by the interface itself according to its own laws Before getting into semigroups, let's see first an example of an algebra, a _magma_. ## Definition of a Magma A Magma is a very simple algebra: - a set or type (A) - a `concat` operation - no laws to obey **Note**: in most cases the terms _set_ and _type_ can be used interchangeably. We can use a TypeScript `interface` to model a Magma. ```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. ```ts 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 ``` **Quiz**. The fact that `concat` is a _closed_ operation isn't a trivial detail. If `A` is the set of natural numbers (defined as positive integers) instead of the JavaScript number type (a set of positive and negative floats), could we define a `Magma` with `concat` implemented like in `MagmaSub`? Can you think of any other `concat` operation on natural numbers for which the `closure` property isn't valid? > See the [answer here](src/quiz-answers/magma-concat-closed.md) **Definition**. Given `A` a non empty set and `*` a binary operation _closed on_ (or _internal to_) `A`, then the pair `(A, *)` is called a _magma_. Magmas do not obey any law, they only have the closure requirement. Let's see an algebra that do requires another law: semigroups. ## Definition of a Semigroup > Given a `Magma` if the `concat` operation is **associative** then it's a _semigroup_. The term "associative" means that the equation: ```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. ```ts ("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. ```ts 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. ```ts 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`, `Semigroup`s are implemented through a TypeScript `interface`: ```ts // 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: ```ts 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`: ```ts import * as Se from 'fp-ts/Semigroup' const Semigroup: Se.Semigroup> = { concat: (first, second) => first.concat(second) } ``` The name `concat` makes sense for arrays (as we'll see later) but, depending on the context and the type `A` on whom we're implementing an instance, the `concat` semigroup operation may have different interpretations and meanings: - "concatenation" - "combination" - "merging" - "fusion" - "selection" - "sum" - "substitution" and many others. **Example** This is how to implement the semigroup `(number, +)` where `+` is the usual addition of numbers: ```ts import { Semigroup } from 'fp-ts/Semigroup' /** number `Semigroup` under addition */ const SemigroupSum: Semigroup = { concat: (first, second) => first + second } ``` **Quiz**. Can the `concat` combinator defined in the demo [`01_retry.ts`](src/01_retry.ts) be used to define a `Semigroup` instance for the `RetryPolicy` type? > See the [answer here](src/quiz-answers/semigroup-demo-concat.md) This is the implementation for the semigroup `(number, *)` where `*` is the usual number multiplication: ```ts import { Semigroup } from 'fp-ts/Semigroup' /** number `Semigroup` under multiplication */ const SemigroupProduct: Semigroup = { concat: (first, second) => first * second } ``` **Note** It is a common mistake to think about the _semigroup of numbers_, but for the same type `A` it is possible to define more **instances** of `Semigroup`. We've seen how for `number` we can define a semigroup under _addition_ and _multiplication_. It is also possible to have `Semigroup`s that share the same operation but differ in types. `SemigroupSum` could've been implemented on natural numbers instead of unsigned floats like `number`. Another example, with the `string` type: ```ts import { Semigroup } from 'fp-ts/Semigroup' const SemigroupString: Semigroup = { concat: (first, second) => first + second } ``` Another two examples, this time with the `boolean` type: ```ts import { Semigroup } from 'fp-ts/Semigroup' const SemigroupAll: Semigroup = { concat: (first, second) => first && second } const SemigroupAny: Semigroup = { concat: (first, second) => first || second } ``` ## The `concatAll` function By definition `concat` combines merely two elements of `A` every time. Is it possible to combine any number of them? The `concatAll` function takes: - an instance of a semigroup - an initial value - an array of elements ```ts 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**. Why do I need to provide an initial value? -> See the [answer here](src/quiz-answers/semigroup-concatAll-initial-value.md) **Example** Lets provide some applications of `concatAll`, by reimplementing some popular functions from the JavaScript standard library. ```ts import * as B from 'fp-ts/boolean' import { concatAll } from 'fp-ts/Semigroup' import * as S from 'fp-ts/struct' const every = (predicate: (a: A) => boolean) => ( as: ReadonlyArray ): boolean => concatAll(B.SemigroupAll)(true)(as.map(predicate)) const some = (predicate: (a: A) => boolean) => ( as: ReadonlyArray ): boolean => concatAll(B.SemigroupAny)(false)(as.map(predicate)) const assign: (as: ReadonlyArray