# Functional programming
](https://ithelp.ithome.com.tw/upload/images/20200904/20106426bGnG71Oiho.jpg)
# Ref
Order from easier to harder, from conceptual to practical.

1. [Mostly adequate guide to FP](https://mostly-adequate.gitbook.io/mostly-adequate-guide/)
1. [What i wish someone had explained about functional programming](https://jrsinclair.com/articles/2019/what-i-wish-someone-had-explained-about-functional-programming/)
2. [Fantas, Eel, and Specification - Tom Harding](http://www.tomharding.me/fantasy-land/)
3. [Functors, Applicatives, And Monads In Pictures - adit.io](https://www.adit.io/posts/2013-04-17-functors,_applicatives,_and_monads_in_pictures.html)
4. [Three Useful Monads - adit.io](https://www.adit.io/posts/2013-06-10-three-useful-monads.html)
4. [Getting started with fp-ts Series](https://dev.to/gcanti)

Other:
1. [If I were starting with fp-ts in TypeScript - why should you do FP](https://www.youtube.com/watch?v=Zbu7flpYnGc)
2. [The Absolute Best Intro to Monads For Software Engineers](https://www.youtube.com/watch?v=C2w45qRc3aU)
3. [fp-ts Tutorial | Chapter 1: pipe and flow](https://www.youtube.com/watch?v=WsKEIFirdVc&list=PLUMXrUa_EuePN94nJ2hAui5nWDj8RO3lH&index=2)
4. [Practical Guide to Fp‑ts 👍👍👍](https://dev.to/ryanleecode/series/7325)
5. [Functional Programming Jargon](https://github.com/hemanth/functional-programming-jargon)
- [Data types in Scala](https://typelevel.org/cats/datatypes/eithert.html)
- [Type classes in Scala](https://typelevel.org/cats/typeclasses/functor.html)
- [Replace lodash with fp-ts](https://github.com/tecklund/lodash-to-fp-ts)
- https://typeclasses.com/contravariance

[Learn you a haskell](http://learnyouahaskell.com/chapters)
https://crocks.dev/docs/monoids/Endo.html
https://dev.to/gcanti/getting-started-with-fp-ts-io-36p6
# Basic Comparison
| BASIS | FP | OOP |
| --------- | ------------------------------------------------------------- | ------------------------------------------------------------- |
| Data | Immutable | Mmutable |
| Model | Declarative programming model. | Imperative programming model. |
| Execution | The statements can be executed in any order. | The statements should be executed in particular order. |
| Iteration | Recursion | Loops |
| Element | Variables and functions. | Objects and methods. |
| Use cases | When there are few things with more operations. | When there are many things with few operations. |
| Creation | Create new variable by composing type classes and functions. | Create new object by inheriting classes. |

# Language
There are many language built for functional programming:
- Elixir
- Scala
- Haskell
- Swift

And many language are actually multi-paradigm. But off course many prefer OOP.

## Python
In Python, `reduce`, `filter`, `map` are featured and grabbed from `LISP`. But `max`, `min`, `all`, `any`, `sum`, list comprehension and generator expressions are viewed as more pythonic.

### `reduce`
Python implemented `reduce` like this:

_initial_missing = object()

def reduce(function, sequence, initial=_initial_missing):
    """
    reduce(function, sequence[, initial]) -> value

    Apply a function of two arguments cumulatively to the items of a sequence,
    from left to right, so as to reduce the sequence to a single value.
    For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
    ((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
    of the sequence in the calculation, and serves as a default when the
    sequence is empty.
    """

    it = iter(sequence)

    if initial is _initial_missing:
        try:
            value = next(it)
        except StopIteration:
            raise TypeError("reduce() of empty sequence with no initial value") from None
    else:
        value = initial

    for element in it:
        value = function(value, element)

    return value

## Javascript / Typescript
Different libraries implemented FP structures (or Monad) in different names. Popular libraries like `rxjs`, `ramda`, `fp-ts`, `ts-purify`, `lodash`, `lodash-fp`.

### Compose
Be careful if it is curried or not.

// compose :: (b -> c) -> (a -> b) -> (a -> c)
const compose = f => g => x => f(g(x))

In typescript:

function compose<T extends any[], R1, R2>(f1: (args: R2) => R1, f2: (...args: T) => R2) {
  return (...x: T) => f1(f2(...x))
}

> from `lodash`'s `flowRight`

### Pipe
`pipe` is just a `compose` with a reverse order.

In `lodash`, `.flow()` is the implementation of `pipe`, while the argument is at the end.
:::success
Using pipe made the functions you use (or dependencies) obvious. If the library is **tree-shakeable**, it can benefit build-time and bundle size. While using a wrapper (basically a functor), would import all the method of the object, such as `_.chain` wrapper in `lodash`. If you using wrapper and map chain, or dynamically `require` a package, would make tree-shaking unavailable when you bundle it up.
:::
:::info
Every function inside a pipe has to be curried. (Just has one argument)
For example:
To time 2 to a list, we have `_.map(list, x => 2*x)`.
The curried one would be `(x => 2*x) => (list) => result`. Which is reversed curry.
We can get it with:

_.curryRight(_.map)(x => x * 2)
// or
_.partial(_.map, _, x => x * 2)

:::
For `lodash/fp`, every function is curried by default, so don't need curry yourself.

_.flow(
    _.curryRight(_.map)(x => x * 2)
)([1, 2, 3])
// [2, 4, 6]

## Head of array and Non-empty array
### Pedantic index signature - index out of bound
In many language, `IndexError` will throw if the index excessesed of the length. But in javascript, you will get a `undefined` instead 👍.

In functional programming, we would just return an `Option` (`Maybe`), which would be `Some` if the index is valid, or `None` if it is not.

`fp-ts` implemented that

import * as A from 'fp-ts/Array'
import { pipe } from 'fp-ts/function'

pipe([1, 2, 3], A.lookup(1)) // Some(2)
pipe([1, 2, 3], A.lookup(3)) // None

But many time we actually know that the indexing must success. Like when we access the first element of a non-empty array. In that case, we wouldn't want an `Option`, the actual result is pretty safe.

`Haskell` and `Scala` actually implemented `NonEmptyList` data type for this. In case of `Scala`, For example, `Validated` (a sum type), if it is a `Invalid`, it must contains at least one error. `NonEmptyList` brings specific information rather than just playing safe everywhere 🤠.

Another example, a function that gives the average of a list, it can go wrong if the list is empty, in stead of `DiviedByZeroError`, we might just use `Option` to wrap it up. By doing so, we just *extended* the inputs of this function. Actually it doesn't make any sense to count the average of an empty list. Forcing the input to be `NonEmptyList` is a better choice 😎.

`fp-ts` has `NonEmptyArray` too:

type NonEmptyArray<T> = [T, T[]]

`NoneEmptyArray<T>` must has a head of type `T`, and a tail that is either an empty list or `T[]` ([] is T[], just saying it specifically).

import * as NEA from "fp-ts/NonEmptyArray";
const foo: NEA.NonEmptyArray<number> = [1, 2, 3];
const head = NEA.head(foo);

# Structure sharing (Persistent Data Structure)

## Persistent Data Structure and Immutable Data Structure
Persistent Data Structures are data structures that keeps old versions of a data. That is it, the old versions may or may change. A *Partial Persistent Data Structure* is that only the latest version is changeable. A *Fully persistent Data Structure* is that all versions are changeable, so a *time travel* is possible on it.

Persistent Data Structures just said the old versions of a data will be kept, and immutability is not guaranteed. *Immutable Persistent Data Structure* is what they combined.

*Immutable Persistent Data Structure* keeps all the versions and all of them are immutable. It uses [*trie*](https://en.wikipedia.org/wiki/Trie) and *structural sharing* to avoid copying and duplicate memory usage.

---

`LinkedList` or `list` are fundamental data structure of functional programming. Different variable can sharing the same structure, and same memory address. It is the opposite of **Ephemeral data structure**.

Common data types like `LinkedList`, `Tree`, `Set`, `Map` can be implemented in persistent way.

> a `Set` implemented from red-black tree

# Lazy Evaluation
A language that support lazy evaluation will not evaluation variables when they create, but when they are referenced. In opposite of strictly evaluation.

x = f(7) # will evaluate f(7) here in python
print(x) # will evaluate f(7) until here if it is lazy evaluation

`Haskell` uses lazy evaluation to make infinite array like `[1..]`, because it knows that you have to call it with finite truncation, otherwise the program will overflow or run forever.
## Haskell
- `<$>` = `map`
- `<*>` = `ap`
- `>>=` = `bind` (flatMap, chain)

# Statement vs Expression
- Statement is how to do something
- Expression is describing what something is

# Referential Transparency
For a function to be referential transparent, it always give the same output given the same input.

If an expression is referentially transparent, we can replace it with its value without changing the program’s behavior.

# Total Functions and Partial Functions
A partial function is a [function](https://github.com/hemanth/functional-programming-jargon?tab=readme-ov-file#function) which is not defined for all arguments - it might return an unexpected result or may never terminate. Partial functions add cognitive overhead, they are harder to reason about and can lead to runtime errors

A total function returns a valid result for all inputs defined in its type. This is as opposed to Partial Functions which may throw an error, return an unexpected result, or fail to terminate.

Some examples of partial functions:

// example 1: sum of the list
// sum :: [Number] -> Number
const sum = arr => arr.reduce((a, b) => a + b)
sum([1, 2, 3]) // 6
sum([]) // TypeError: Reduce of empty array with no initial value

// example 2: get the first item in list
// first :: [A] -> A
const first = a => a[0]
first([42]) // 42
first([]) // undefined
// or even worse:
first([[42]])[0] // 42
first([])[0] // Uncaught TypeError: Cannot read property '0' of undefined

// example 3: repeat function N times
// times :: Number -> (Number -> Number) -> Number
const times = n => fn => n && (fn(n), times(n - 1)(fn))
times(3)(console.log)
// 3
// 2
// 1
times(-1)(console.log)
// RangeError: Maximum call stack size exceeded

### [ ](https://github.com/hemanth/functional-programming-jargon?tab=readme-ov-file#dealing-with-partial-functions)Dealing with partial functions

Partial functions are dangerous as they need to be treated with great caution. You might get an unexpected (wrong) result or run into runtime errors. Sometimes a partial function might not return at all. Being aware of and treating all these edge cases accordingly can become very tedious. Fortunately a partial function can be converted to a regular (or total) one. We can provide default values or use guards to deal with inputs for which the (previously) partial function is undefined. Utilizing the [`Option`](https://github.com/hemanth/functional-programming-jargon?tab=readme-ov-file#Option) type, we can yield either `Some(value)` or `None` where we would otherwise have behaved unexpectedly:

// example 1: sum of the list
// we can provide default value so it will always return result
// sum :: [Number] -> Number
const sum = arr => arr.reduce((a, b) => a + b, 0)
sum([1, 2, 3]) // 6
sum([]) // 0

// example 2: get the first item in list
// change result to Option
// first :: [A] -> Option A
const first = a => a.length ? Some(a[0]) : None()
first([42]).map(a => console.log(a)) // 42
first([]).map(a => console.log(a)) // console.log won't execute at all
// our previous worst case
first([[42]]).map(a => console.log(a[0])) // 42
first([]).map(a => console.log(a[0])) // won't execute, so we won't have error here
// more of that, you will know by function return type (Option)
// that you should use `.map` method to access the data and you will never forget
// to check your input because such check become built-in into the function

// example 3: repeat function N times
// we should make function always terminate by changing conditions:
// times :: Number -> (Number -> Number) -> Number
const times = n => fn => n > 0 && (fn(n), times(n - 1)(fn))
times(3)(console.log)
// 3
// 2
// 1
times(-1)(console.log)
// won't execute anything

Making your partial functions total ones, these kinds of runtime errors can be prevented. Always returning a value will also make for code that is both easier to maintain and to reason about.

# Currying
Currying provided two capabilities, if `g` is a curried function
1. its arguments needn't be provided one at a time
the following are equivalent:
- `g(1)(2)(3)`
- `g(1)(2, 3)`
- `g(1, 2)(3)`
- `g(1, 2, 3)`

3. ([by Ramda implementation](https://ramdajs.com/docs/#curry))
arguments' postitions can be re-arranged:
the special placeholder value [`R.__`](https://ramdajs.com/docs/#__) may be used to specify "gaps", allowing partial application of any combination of arguments, regardless of their positions. If `g` is as above and `_` is [`R.__`](https://ramdajs.com/docs/#__), the following are equivalent:

- `g(1, 2, 3)`
- `g(_, 2, 3)(1)`
- `g(_, _, 3)(1)(2)`
- `g(_, _, 3)(1, 2)`
- `g(_, 2)(1)(3)`
- `g(_, 2)(1, 3)`
- `g(_, 2)(_, 3)(1)`

const curry = <T, TR>(func: (...args: T[]) => TR) => function curried(...args: T[]) {
  return (
    args.length >= func.length
      ? func.apply(this, args)
      : (...nextArgs: T[]) => curried.apply(this, args.concat(nextArgs))
  )
}

But the need of currying in functional programming arises because it is the only way to represent **_binary_ operation** and **morphism** in math.

## Morphism
A morphism is a transformation between objects in a category in category theory. If the object is `Set`, the morphisms are set functions that map one set to another set.

Say we designed a `convert` which can classify the fat you need into 3 levels base on your weight, it is natural to code something like `convert(fat: number, weight: number) => string`. But it may think as we calculate the _standard score_ (or some measure) of fat intake base on

## Arity
The number of arguments a function takes. like nullary, unary, binary, ternary, etc.

In haskell, nullary function is actually variable, because data is immutable in haskell.

A unary function is like:

add1 x = x + 1; 

A nullary function is a variable

something = "abc"

### Unary
`NOT` or *inverse* is a unary operation. Which is represented by `f(a)`. A unary operation is called *idempotent* if `f(f(a)) == f(a)`. For example, `Math.abs(Math.abs(10))` is idempotent.

### Binary operation
`+`, `x` are common examples of binary operations. While in real world we deal with functions that take multiple inputs, like `sum`, `max`, `any`, etc. But how?

`1+2+3` can be parsed as `(1+2)+3`, or `1+(2+3)`. Dont you say, this is called the **_associativity law_** in math. But if we take the first one, it just did `+` twice, `1+2` and `(3)+3`, even if it takes 3 inputs in the first place.

This is called *left-assoicatitive*, that means if we want to apply `+` to a list of arguments, we need to do it from left to right, and that is `foldl`. Being said, a `sum` for a list can be done by `foldl((acc,n) => acc + n, 0)`. And so do other binary operations. We will discuss it more in `Monoid`.

# Point-free (Tacit)
Point-free programming is a programming paradigm that does not identify the arguments (or **points**). Instead it defines actions by composing other functions.
:::info
**Point-free**, or **Pointless**, is a special style that does not care the input.
For example, a specific transformation can be define as:

def get_unique_count_and_sort(data: list[int]) -> list[int]:
    ...

Which require some understanding of the data.
But the transformation itself is actually data-careless, If we can decompose it into smaller functions:

pipline = compose(
    sort,
    get_unique_count
)

:::

# _[ad hoc polymorphism](https://en.wikipedia.org/wiki/Ad_hoc_polymorphism)_
**ad hoc polymorphism** is a kind of [polymorphism](https://en.wikipedia.org/wiki/Polymorphism_(computer_science) "Polymorphism (computer science)") in which polymorphic functions can be applied to arguments of different types.

This is in contrast to [parametric polymorphism](https://en.wikipedia.org/wiki/Parametric_polymorphism "Parametric polymorphism"), in which polymorphic functions are written without mention of any specific type, and can thus apply a single abstract implementation to any number of types in a transparent way.
(parametric polymorphism can support nearly infinite type of parameters, like **duck-typing**: if it sounds like a duck, it is a duck, thus it can be a target for some function of duck.)

When applied to object-oriented or procedural concepts, it is also known as **function overloading** or **operator overloading**.

# Hindley-Milner Type Signatures
Functional programmers have developed a special notation for specifying what types of parameter a function takes, and what it returns. The notation is called Hindley-Milner type signatures. We write them as comments where we define the function.

# Kleisli
_Kleisli_ is a morphism with signature `a => F b`. Hence it does `lifting` and `mapping` at the same time.

# Type Classes
:::info
A type class is the type of a type. Just like a class is an abstraction of variable, and class has its own class. But type class does it without inheritance, but adding laws to generic types.

A generic type (parameterized type) `A` can become a member (instance) of a type class `T` by declaring an *instance* for that type class. Which means implementing all the methods in `T`. In other sense, we called type `A` is an instance of type class `T` if `A` is restricted by `T` (by class methods and conceptual laws).
:::

> A type class is an interface that defines some behavior. More specifically, a type class specifies a bunch of functions, and when we decide to make a type an instance of a type class, we define what those functions mean for that type.
>
> ***[Learn You a Haskell for Great Good!](http://learnyouahaskell.com/making-our-own-types-and-typeclasses#derived-instances)***

A type class is what implemented algebraic structures, in `Haskell`, it is data types, in `Typescript`, it can be `interface`. So it is a language feature to translate the mathematical concepts into program. Despite the conceptual laws like *associativity*, *identity*, are often unable to tell just by program.

In javascript, we dont have built-in type classes at all, so most of the time we would drive them from algebraic structures.

Some common type classes:
- `Eq`: Something that can be equated, with `==` and `\=` .
- `Ord`: Something that can be order, with `qt`, `lt`, `qte` and `lte`. The `Ordering` is often represented by `1`, `0` and `-1`.
- `Bounded`: Something that has `maxBound` and `minBound`. A easier form of `lattice`.
- `Show`: Something that can translate into a string, often for debug and prettier print.
`Show :: a -> String`
- `Read`: Can take a string and return a type, like a reverse of `Show`
`Read :: String -> a`
- `Enum`: has `predecessors` and `successors`
-

# Algebraic Structures
Common type class hierarchy
> [Fantasy Land Specification](https://github.com/fantasyland/fantasy-land)

> [Typeclassopedia - Haskell](https://wiki.haskell.org/Typeclassopedia)

> [Sanctuary](https://github.com/sanctuary-js/sanctuary-type-classes)

> [Type Level](https://typelevel.org/cats/typeclasses.html)

> https://cs.lmu.edu/~ray/notes/introhaskell/

An algebraic structure is **some** set (called the **underlying set**, **carrier set** or **domain**)
with **some** operations (typically [binary operations](https://en.wikipedia.org/wiki/Binary_operation "Binary operation") such as addition and multiplication)

More complicated algebraic structures such as group, ring, field, can be produced by composing more operations, domains and axioms.

> The graph looks like an inheritance or UML in OOP, but it isn't that way. Usually an inheritance has prerequisite, you must have a superclass before the subclass is made, the son must born after his father.
>
> But it is not like that, we can have a monad, but it didn't necessarily (_but usually do_) is a `Applicative` or `Functor` instance. But we can have them for _free_, for example:

// map derived from chain
X.prototype.map = function map(f) {
  return this.chain(a => this.constructor.of(f(a)));
};

// ap derived from chain/map
X.prototype.ap = function ap(other) {
  return this.chain(f => other.map(f));
};

> Because we know that in a mathematical sense, a monad is based on `map` and `join`, so if we have `chain`, we can _reverse_ it to `map`, if we have `map`, we can built it up to `chain`.
>
> Another common case is that if our functor wrapped an instance of a type class `T`, We can just extend that functor to also be a instance of `T`. For example, if we have a `[number]`, as `number` belongs to `Eq`, our list is automatically an `Eq`, so we can do `a==b` where `a` and `b` are both `[number]`.
>
> It is like if we know cos law, we would know Pythagorean theorem for free. If we know Pythagorean theorem first, we can still get cos law for free.

> [Type level - algebra](https://typelevel.org/cats/algebra.html)

## Functor (Covariant Functor)

A functor structure must have a `.map()` method with the following type signature:
`map :: Functor f => f a ~> (a -> b) -> f b`
In typescript:

interface Functor<A> {
    map<B>(f: (a:A) => B) : Functor<B>
}

The `.map()` method takes a function as an argument, the function must take something of type a and return something of type b. Even if a and b are the same. So when `.map()` of a functor of a is called, a functor of b is returned.

If `u` is a functor
1. `u.map(x => x)` return `u` (identity law)
2. given functions `f` and `g`, `u.map(x => f(g(x)))` = `u.map(g).map(f)` (composition law)

In javascript, `Array` has a `.map()` method and it obeys those functor laws, hence we can say `Array` is a functor. Also, `Maybe`, `Either` and `Effect` are functors too.

When we using functors, we bottle up a value and using `map` to get at it. In some fancy words, it gives abstraction of function pplication, when we `map` a function, we ask the container to run it for us, and it is powerful. It give some room to the functor to decide what to do, is it really executing it or doing nothing? is it doing it right away or lazily? is it logging anything along the way?

> Most of the functors are a container (but not all containers are functor, and some functor didn't contain anything, like `None`). Hence, a functor `f a` means something containing `a`, like `Array` of `String`.

> Famously saying, a functor is a **context**, when a function is applied to a functor, different results is provided depending on the context. For example, `Maybe` represents the context of *possibly null*, `Either` is for *possibly failure*, `IO` is for *side effect*. That can be extended to Applicatives, Monads, Arrows, etc.

`.map()` of functors transforms the inner but not the outer container. Like transforming `Array` of `String` into `Array` of `Boolean`.

So a functor **must not care** what it contains.
For example, if we `map` a `Set` into another `Set`, the content may duplicate, the result may not be a `Set`, and so `Set` are not functor.
:::

## Magma
A magma is a algebraic structure (a set and a _(probably binary)_ operation) that satisfies _closure axiom_. It has little practical use as it is not powerful. But closure is essential for `map` chain, and it did play a role.

### Closure
A structure (a set + a operation) obey closure if every element in it after the operation is still in the set. For example, $(\mathbb{N},+)$ obeys closure as every natural number add gother giving another natural number. While $(\mathbb{N},\div)$ does not obey closure, because 1/2 is a result of its set and operation, but 1/2 is not in natural number set.

It is important for programming because, in order to do something like `a+b+c` or `f.map(...).map(...)`, will as least require `+` and `map` return the same type as its input.

## Semigroup
Semigroup is a magma (things with *closure*) that obey **associative law**.
### Associativity
Associativity is a property for a set with a binary operation `+`, the following is true:
`(a+b)+c = a+(b+c)`
In programming:
`concat(concat(a, b), c) = concat(a, concat(b, c))`
`= a.concat(b).concat(c) = a.concat(b.concat(c))`

This said:

1 + 2 + 3 = (1 + 2) + 3 = 1 + (2 + 3)

if that is true, we can parse it from left-to-right or right-to-left.

We have
`concat :: Semigroup a => a -> a -> a`
It takes another value of the same type and return another value of the same type.

### Parallelism
Associativity is the foundation of `parallelism` and `divide and conquer`.

### left/right-associativity and precedence
*Associativity* and *precedence* are 2 properties of an operator.
#### Associativity
If an operator is left-associative, this means it should be read from left to right. Like `1 + 2 + 3` implying `(1 + 2) + 3`, instead of `1 + (2 + 3)`.

*Function application* is an operation to apply function to an argument, and it is an operator in haskell. It is read as `$`, or a just space between. Like `func x` or `$ func x`. It is left-associative, because when we do `func x y`, it is actually `(func x) y`, it first retrieve `func x` that is a function and then the `y`.

While *Function definition* is also an operation, a function may have type `a -> b`, that is defined by the `->` operator, ie. the type-mapping infix operator. And it is right-associative, because when we do `a -> b -> c`, it means `a -> (b -> c)`.

### Example
`Array`, `String` are semigroup,
`[].concat([1]).concat([2]) = [].concat([1].concat([2]))`

`Max`, `Min` are semigroup, as `max(a, max(b, c)) = max(max(a, b), c)`

`Some`, `Every` are semigroup, `some(True, some(True, False)) = some(some(True, True), False)`

Some.prototype.concat = function (that) {
    return Some(this.val || that.val)
}
Every.prototype.concat = function (that) {
    return Every(this.val && that.val)
}

`First` and `Last` are semigroup, `First(a, ...) = a`

`Set` is a semigroup, clear that `Set(a, Set(b, c)) = Set(Set(a, b), c)`
So for `Set`, the concatenation is **union** (or **intersection**), but because of the uniqueness of element of a Set, the content of a Set must be a `Setoid` (so duplication is defined).

### Union and Intersection

### Concatenation and Merging
Given a `Customer` object, and we want it to be `Semigroup`

interface Customer = {
    name: string
    favouriteThings: string[]
    registrationDate: number
    hasMadePurchase: boolean
}

We can have **different strategies** for merging, depending on the situation. :skull:
:thinking_face: We can represent the `Customer` by a `Tuple`. (In fancy words, our `Customer` structure is **isomorphic** to a `Tuple`)

const myStrategy = {
    to: (customer) => Tuple(
        First(customer.name),
        customer.favouriteThings,
        Min(customer.registrationDate),
        Any(customer.hasMadePurchase)
    ),
    from: (tuple) => Customer(tuple[0],tuple[1],tuple[2],tuple[3])
}

Now the `Customer` is no longer important as our `Tuple` is a semigroup

const merge = strategy => (x, y) =>
    strategy.from(
        strategy.to(x)
        .concat(strategy.to(y))
    )
// OR something like
const merge = strategy => (x, y) =>
    pipe(
        strategy.to
        concat(strategy.to(x))
        strategy.from
    )

What if we want to merge a bunch of customers? Just use a `reduce`

const mergeMany = strategy => initialList =>
    customers => customers.reduce(
        merge(strategy), initialList
    )

## Monoid
A `Monoid` is a `Semigroup` that has an **identity** for the `concat` operation. Which stored on the type as a function called `empty`. Which called `empty` _possibly_ because _identity_ often refers to `map` (`x => x`) or `ap` (`x =>M.of(x)`).

`empty :: Monoid m => () -> m`
(This doesn't help much)
:::info
Right identity:
`MyType(x).concat(MyType.empty()) === MyType(x)` (x + 0 = x)
Left identity:
`MyType.empty().concat(MyType(x)) === MyType(x)` (0 + x = x)
:::

| Type | Identity | empty() |
| ------- | --------- | ---------------- |
| String | '' | () => '' |
| Array | [] | () => [] |
| Sum | 0 | () => Sum(0) |
| Product | 1 | () => Product(1) |
| Max | -Infinity | |
| Min | Infinity | |
| All | true | |
| Any | false | |
| First | :x: | |
| Last | :x: | |

:::info
`First` and `Last` are monoids in Haskell. This is done by sneaking in a `Maybe`, where `Nothing` becomes `empty`. This actually works for **any semigroup**.
:::

const fold = M => xs => xs.reduce(
    (acc, x) => acc.concat(M(x)),
    M.empty()
)
fold(Sum)([1,2,3]).val // 6
fold(Max)([9,7,11]).val // 11

## Apply
An `Apply` is also a `Functor`. So it is definitely "container" for other types.
> `ap :: Apply f => f a ~> f (a -> b) -> f b`

In Haskell

> `<*> :: f (a -> b) -> f a -> f b`

If we ignore the `f`, it is `a ~> (a -> b) -> b`. In `map`, we have `f a ~> (a -> b) -> f b`. So `ap` must do the something as `map`, except the mapping `a -> b` is wrapped in a functor.

What it means is, a `.ap` of `f a` takes an argument of `f (a -> b)`, a `Functor` contains a function of `a -> b`, and returns a `Functor` of b, `f b`.

For example (`Maybe.of(5)` means, ... literally a `Maybe` of 5):
`Maybe.of(5).ap(Maybe.of(x => x*2)) === Maybe.of(10)`

//  Composite law
v.ap(u).ap(a) === v.ap(u.ap(a.map(compose))) 

Array.prototype.ap = function ap(other) {
    return other.chain(f => this.map(f))
}
//  OR
ap = (other: M) => this.map(other.join())

`ap` is about putting `functors` into function that takes multiple pure values. In a common sense, we have to _"unwrap"_ functors in order to put it in a function. But`ap` is an approach to **NOT unwrap** anything. For example, let say we have a `Maybe` of id, a `Maybe` of user, and an effect `eff :: id => user => any` that takes both id and user as arguments.

<!-- So, by `Maybe id` `.map(eff)` (let call it `Maybe 😈`) becomes a function wrapped in a `Maybe`, to put user into it, we have to use `.join()` to pull the function out, like `Maybe user` `.map(😈.join())`. -->
In javascript, We have promises, a functor if we think `.then()` as `.map()`, also _closure_ and _associativity_ stuff. We don't _"unwrap"_ promises, there is no such thing.

We can do
1. `user.map(user => id.map(id => eff(id)(user)))` => `Maybe(Maybe(any))`
2. `user.map(id.map(eff).join())` => `Maybe(any)`

By `ap = this => other => this.map(other.join())`, we found `user.ap(id.map(eff))`.

### Let's think about 3-ary function
Let `g` to be a 3-ary function, in order to put 3 `Maybes` into it, we need:

a.ap(b.ap(c.map(g)))

So it is a nested structure, to flatten that, we need something like:

// liftA3 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA3 = g => a => b => c => c.ap(b.ap(a.map(g)))
// liftA3(compose)(f)(g)(x) === x.ap(g).ap(f)

_**Lifting**_ is the processing that _lift_ the value into the right container (a functor). Functions are better off working with normal data types rather than container types. This lead to simpler, more reusable functions to work with any functors on demand.

Frequently it is called `liftA2`, `liftA3` in `Haskell`, meaning _lift to applicative_. Similarly, there is `liftM` meaning _lift to monad_.

function lift(func, functor1, ...functors) {
  functors.reverse().reduce((acc, next) => next.ap(acc), functor1.map(func))
}

## Applicative
An applicative is also a functor but with a `of` method. `of` puts the inputs in _**default minimal context**_, a functor with that is also called _**pointed functor**_.

ES2015 actually implemented a `Array.of`, like `Array.of(5) == [5]`, so `Array` is a pointed functor 😉.

In Haskell

pure :: a -> f a

## Monad
> Monad is a type that can flat the functor

> A monad is just a monoid in the category of endofunctors, what's the problem?
> _Categories for the Working Mathematician_

Functional programming is all about _composition_. Monads are all about _chaining_. Monad can be a program, an operation. If you think monads as a function, chaining monads is chaining operations. If you think monads as a container (more like functors), chaining monads is transforming the value while the monad manages secret work behind the scenes.
- `Writer`: log concatenation
- `Maybe`: possible missing values
- `Future`: values that only available later
### `chain`
`chain :: M a ~> (a -> M b) -> M b`
:::info
Unfortunately, other programming languages use a bunch of different names for this idea. It can get a little bit confusing if you’re trying to read up about it. Sometimes it’s called `flatMap`. This name makes a lot of sense, as we’re doing a regular mapping, then flattening out the result with `.join()`. In Haskell though, it’s given the confusing name of `bind`. So if you’re reading elsewhere, keep in mind that `chain`, `flatMap` and `bind` refer to similar concepts.

:::
In Python

flat_map = lambda f, xs: [y for ys in xs for y in f(ys)]

## `map`, `ap` and `chain`
| Program f | Program g | Composition |
| --------- | ------------- | ---------------- |
| pure | pure | `g ∘ f` |
| effectful | pure, `n`-ary | `liftAn(g) ∘ f` |
| effectful | effectful | `flatMap(g) ∘ f` |

## Comonad

An object that has `extract` and `extend` functions.

const CoIdentity = (v) => ({
  val: v,
  extract () {
    return this.val
  },
  extend (f) {
    return CoIdentity(f(this))
  }
})

`extract` takes a value out of a functor:

CoIdentity(1).extract() // 1

`extend` runs a function on the comonad. The function should return the same type as the comonad:

CoIdentity(1).extend((co) => co.extract() + 1) // CoIdentity(2)

## Setoid (Eq)
A setoid is anything with a notion of **equivalence**, like primitives such as string, boolean, integer.
`equals :: Setoid a => a ~> a -> Boolean`
A setoid must obey 3 laws:
1. `a.equals(a)` (reflexivity)
2. `a.equals(b) === b.equals(a)` (symmetry or commutativity)
3. If `a.equals(b)` and `b.equals(c)`, then `a.equals(c)` (transitivity)
:::info
In javascript, primitive are compared by value and object are compared by reference. So `prototype.equals` doesn't work for primitive. `===` cannot be overrided by `equals`.

:::

## Ord
-1, 0, 1

## Foldable

An object that has a `reduce` function that applies a function against an accumulator and each element in the array (from left to right) to reduce it to a single value.

const sum = (list) => list.reduce((acc, val) => acc + val, 0)
sum([1, 2, 3]) // 6

## Sequences and Traversals
### Sequences
A sequence is just a higher level pattern of `apply`.

Let's say we have a plain function, but we only have some functor inputs.

const inputs = [O.some(1), O.some(2), O.some(3)]
declare function f: (a:number, b:number, c:number) => boolean;

In order to put the wrapped inputs into the function, we probably would do:

pipe(
    O.of(f),
    O.ap(O.some(1)),
    O.ap(O.some(2)),
    O.ap(O.some(3)),
) // O.some(f(1, 2, 3))

> Do-notation is also favored, in that way we would declare the inputs (a, b, c here), and feed into `f` in the end.
> ```typescript!
> pipe(
> O.Do,
> O.bind('a', ()=>O.some(1)),
> O.bind('b', ()=>O.some(2)),
> O.bind('c', ()=>O.some(3)),
> O.map(({a, b, c})=>f(a, b, c))
> ) // O.some(f(1, 2, 3))
> ```

### Traversals
A traversal is actually a `sequenceMap` 😂. Just like `flatMap`, `partitionMap`, etc, it `map`s and then `sequence`.

# Algebraic Data Types
Algebraic Data Types (ADT) are structured types that are formed by composing other types.
- Sum type: `Either`, `Maybe`
- Product type: `Array`, `Object`

## Product Type
The constructors in product type can vary independently, like `Point(x: int, y: int)`. The combination of a product type is usually infinite.

In `Rust`, structs represent product types. You can access the member like `mushroom.price`.

struct Mushroom {
    name: String,
    price: i32,
}

In this example, `name` and `price` can vary independently, hence the total combination is `the combination of name` x `the combination of price`. Therefore, it is a product type.

## Sum Type
In `Rust`, Enums represent sum types. But Rust doesn’t allow accessing a partial field.

enum Fungi {
    Edible { name: String, choice_edible: bool },
    Inedible { name: String },
}

# Higher Kinded Type
A value can be typed, a type can also be typed. The type of a type is called **_kind_**. The most basic type is the **_concrete type_** (or the *proper type*), like `number`, `boolean`. Which can be used to computed **_compound types_**, for example, a array of number is constructed by `number`, something like this called **_higher kinded type_**.

`Array` is like a function of type, it takes a type and return a concrete type, this is called a *type constructor*. `Array<number>` and `number` are both concrete type, but `Array` itself is not. A concrete type will have a kind of `*`, (just called *kind*). So `Array` would have a kind of `* -> *`, as we said, it takes a concrete type and returns one.

We can construct a type `Id<T> = T`, which also has a kind of `* -> *`.

A `Map` has two data type - keys and values, so it has a type signature `Map<A, B>`, and again `Map` is a type constructor and `Map<A, B>` is a concrete type. So `Map` has a kind of `* -> * -> *` (some people may write it like `(*, *) -> *`, this is a bit weird, as the type arguments can be partial filled, like pre-defiing the key to be `string`, say `NewType<T> = Map<string, T>`, it is actually a `Record`).

A *higher kinded type* has a signature of `( * -> * ) -> *`, it takes a `* -> *` (e.g. `List`) as a parameter, and return a concrete type. An example is `Functor`:

trait Functor [F[_]] {
   def map[A,B] (fn: A=>B)(fa: F[A]): F[B]
}

We can see `Functor` abstructs away from an unary type constructor

We can see that `Generic` in Typescript, Python and Java can be type constructors. And it is not a *first-class citizen*, it is not allowed to put a type constructor as a type parameter. Which means higher kinded types can't be implemented at least on a direct way. But for Scala and Haskell, it is supported.

## First-Class Citizen
First-Class Citizen are things that -
- can be passed as parameters of functions
- can be returned by functions
- can be assigned by assignment statements
- can be tested for equality

As a result, a first-class citizen should have the ability to be created at runtime. As this said, `functions` are not first-class citizen in `C++`, as they must be created at compile time. `Array` and `String` are not first-class citizen in `C`, because when they passed as parameters, only the pointer that points to the first element is passed, the size is missed.

## Data Constructors [#](https://stackoverflow.com/questions/18204308/haskell-type-vs-data-constructor)

data Color = Red | Green | Blue

`Color` is a nullary type constructor, and `Red` is a nullary data constructor.
> A data constructor is a "function" that takes 0 or more values and gives you back a new value.

> A type constructor is a "function" that takes 0 or more types and gives you back a new type.

data Bool = True | False

In this case, `Bool` is a nullary type constructor (a concrete type). `True` and `False` are values.

data Maybe a = Nothing | Just a

`Maybe` is an unary type constructor (* -> *). And `Nothing` and `Just` are not types, `Nothing` is a nullary data constructor, and `Just` is an unary data constructor. `Just` has a signature of

Just :: a -> Maybe a

As this said, `Just` and `Nothing` are both function.

# JS Array Method Cheat Sheet
# 

# Common monads
## Maybe
`Maybe` implemented `Functor`, `Applicative` and `Monad`.

`m = Maybe.of(5) // Just(5)`
- Functor: `m.map(x => x) === m`
- Apply a function `f` into a value of a context
- Apply: `m.ap(Maybe.of(x => x)) === m`
- Apply a function that wrapped in a context into a value of a context
- Monad: `m.chain(x => M.of(x)) === m`
- Apply a function that takes a value but returns a context (`f :: a -> m a`) into a value of a context
## Either
> [haskell wiki - Error vs Exception](https://wiki.haskell.org/Error_vs._Exception)
>
The problem with `try/catch` is that:
1. It splits the code into branches
2. You have to do all the stuff in the `try` scope
3. People won't know that your function would throw, if you re-throw the error, which may cause multiple error catching
4. The error caught has `unknown` type, you would need further type guard to find out what type of error it is
5. Throwing error is a side effect
6. Throwing error resulting in a ***partial function***, (which means a function that has no return for some inputs, in opposite of a *total function*, that always return, these are from math conecpt).

You would often end up facing something like this:

try{
    const parsed = parseUrl("...")
    // ...
    // ...
    // ...
} catch {
    return false
}

Here `parseUrl` will throw if the url is invalid, then we would just return `false`. The giant try block must stay and we have to do all the stuff inside it, becuase `parsed` is scoped in it. This is actually annoying.

It would be also nice if the error types are explicit, just like in Python:

catch (e: NetworkError | ValidationError | ...) {
    match({
        NetworkError: e => 'handle network error ...',
        ValidationError: e => 'handle validation error ...'
    })
}

`Either` provide extra information of why the computation failed, which `Maybe` didn't.

## Maybe and Either in Rust

`Maybe` and `Either` called `Option` and `Result` in Rust.

`Option` corresponds to `Maybe`:

// Defined in the standard library
enum Option<T> {
    None,
    Some(T),
}

let head = ["Porcini", "Oyster", "Shiitake"].get(0);
println!("{:?}", head);
// Prints: Some("Porcini")

`Result` corresponds to `Either`:

// Defined in the standard library
enum Result<T, E> {
    Ok(T),
    Err(E),
}

There are no monads and no do-notation. We can use [`unwrap_or()`](https://doc.rust-lang.org/stable/std/option/enum.Option.html#method.unwrap_or) from `Option` or [`unwrap_or()`](https://doc.rust-lang.org/stable/std/result/enum.Result.html#method.unwrap_or) from `Result` to safely unwrap values.

let item = [].get(0).unwrap_or(&"nothing");
println!("I got {item}");
// Prints: I got nothing

let result = Err::<i32, &str>("Out of mushrooms error").unwrap_or(0);
println!("I got {result}");
// Prints: I got 0

Note that there are also [`unwrap_or_else()`](https://doc.rust-lang.org/stable/std/option/enum.Option.html#method.unwrap_or_else) and [`unwrap_or_default()`](https://doc.rust-lang.org/stable/std/option/enum.Option.html#method.unwrap_or_default).

We can also use the [`and_then()`](https://doc.rust-lang.org/stable/std/option/enum.Option.html#method.and_then) method to chain (or bind) multiple effectful functions:

let inventory = vec![
    "Shiitake".to_string(),
    "Porcini".to_string(),
    "Oyster".to_string(),
];

let optional_head = inventory.first().and_then(|i| i.strip_prefix("Shii"));

println!("{:?}", optional_head);
// Prints: Some("take")

Also, Rust provides the question mark operator ([`?`](https://doc.rust-lang.org/std/result/index.html#the-question-mark-operator-)) to deal with sequences of `Result` or `Option`.

use std::collections::HashMap;

fn order_mushrooms(prices: HashMap<&str, i32>) -> Option<i32> {
    let donut_price = prices.get("Porcini")?; // early return if None
    let cake_price = prices.get("Oyster")?; // early return if None
    Some(donut_price + cake_price)
}

let prices = HashMap::from([("Porcini", 75), ("Oyster", 7)]);

let total_price = order_mushrooms(prices);
println!("{:?}", total_price);
// Prints: Some(82)

An expression that ends with [`?`](https://doc.rust-lang.org/std/ops/trait.Try.html) either results in the unwrapped success value or short-circuits on failure.

For example, if looking up one of the mushrooms fails, the whole function fails:

let prices = HashMap::from([("Oyster", 7)]);

let total_price = order_mushrooms(prices);
println!("{:?}", total_price); 
// Prints: None

## Maybe in `Java` [#](https://docs.oracle.com/javase/8/docs/api/java/util/Optional.html)
`Maybe` is called `Optional` in Java. You can wrap something up using `Optional.of` or `Optional.ofNullable`. And it has `.map()` and `.flatMap()` like we do. Use `.orElse()` to deal with the none case.

Ionically java introduce `Optional` to deal with null-pointer, but it desn't help much. Because all non-primitive type in Java can be `null`. So an `Optional` variable can still be `null`, and null pointer will still occur when `optionActuallyNull.orElse(...)` is called.

## [Ior in Scala](https://typelevel.org/cats/datatypes/ior.html)
`Ior`means `inclusive or` if `Either` is representing an exclusive or. As `Either a b` can either be `Left` or `Right`, in contrast, `Ior` *includes* `both`, being `Left` *and* `Right` at the same time.

It is also *right biased*, which means `map` and `chain` all operate on `Right`, while the `Left` can accumulate. For the `Left` to able to accumulate, `Left` should be a `semigroup` instance.

`Either` is binary, white and black. `Ior` is designed for fuzzy logic. We may want to accumulate the *error* (deprecated feature, warning, for example) until we hit a fatal error.

## IO (Effect)
IO is actually a container of a function (the effect). It represents a synchronous effectful computation which _never fails_, which is basically a _thunk**_, ie a function like `()=>A`.

Examples of it can be:
- read / write to `localStorage`
- read current time
- write to the `console`
- read a random number

An example implementation of IO monad

class IO {
    static of(x) {
        return new IO(() => x)
    }
    
    constructor(fn) {
        this._value = fn
    }
    
    map(fn) {
        return new IO(() => compose(fn, this._value))
    }
    
    value() {
        return this._value()
    }
}

const ioWindow = new IO.of(window)
ioWindow
  .map(prop('location'))
  .map(prop('href'))
  .map(split('/'))
// IO(['http:', '', 'localhost:8000', 'blog', 'posts'])

const $ = selector => new IO(() => document.querySelectorAll(selector))
$('#myDiv').map(head).map(div => div.innerHTML).value()
// 'I am some inner html'

It looks familiar, isn't it?

## Future (Task)
A Task is like a `IO` of a callback. The biggest problem of callbacks is that they nested deeper and deeper, like a russian nesting doll with branch of bunch of `try/catch` and `if/else` branches, called _callback hell_. `async/await` is a way of loosing them, but we have our way.

// -- Node readFile example ------------------------------------------

// readFile :: String -> Task Error String
const readFile = filename => new Task((reject, result) => {
  fs.readFile(filename, (err, data) => (err ? reject(err) : result(data)));
});

readFile('metamorphosis').map(split('\n')).map(head)
// Task('One morning, as Gregor Samsa was waking up from anxious dreams, he discovered that in bed he had been changed into a monstrous verminous bug.')

// -- jQuery getJSON example -----------------------------------------

// getJSON :: String -> {} -> Task Error JSON
const getJSON = curry((url, params) => new Task((reject, result) => {
  $.getJSON(url, params, result).fail(reject);
}));

getJSON('/video', { id: 10 }).map(prop('title'));
// Task('Family Matters ep 15')

`Task` is like `Promise`, the only difference is `Task` will patiently wait for running, and `Promise` running it right away.

## Reader
`Reader` is a pattern to do dependency injection.
### `ask()`

const ask: <R>() => Reader<R, R> = () => identity

map :: (a -> b) -> Reader r a -> Reader r b

`r` was never changed for `Reader`'s `map`, this is like `Either`.
## Writer
## State

# Natural Transformation
When multiple types of functor are nested...

Right(Maybe('b'));

IO(Task(IO(1000)));

[Identity('bee thousand')];

## Principled Type Conversions

// idToMaybe :: Identity a -> Maybe a
const idToMaybe = x => Maybe.of(x.$value);

// idToIO :: Identity a -> IO a
const idToIO = x => IO.of(x.$value);

// eitherToTask :: Either a b -> Task a b
const eitherToTask = either(Task.rejected, Task.of);

// ioToTask :: IO a -> Task () a
const ioToTask = x => new Task((reject, resolve) => resolve(x.unsafePerform()));

// maybeToTask :: Maybe a -> Task () a
const maybeToTask = x => (x.isNothing ? Task.rejected() : Task.of(x.$value));

// arrayToMaybe :: [a] -> Maybe a
const arrayToMaybe = x => Maybe.of(x[0]);

The transformation can be no-loss or with data loss. The whole point is `map` must carry on, even we transform the functor in the `map` chain, it can still going on.
## Feature Envy
When we can completely go back and forth without losing any information, that is considered an _isomorphism_. That's just a fancy word for "holds the same data". We say that two types are _isomorphic_ if we can provide the "to" and "from" _natural transformations_ as proof:

// getValue :: Selector -> Task Error (Maybe String)
// postComment :: String -> Task Error Comment
// validate :: String -> Either ValidationError String

// saveComment :: () -> Task Error Comment
const saveComment = compose(
  chain(postComment),
  chain(eitherToTask),
  map(validate),
  chain(maybeToTask),
  getValue('#comment'),
);

# Category Theory
A category is :
1. Objects
2. Morphisms
3. Composition
4. Identities

And obeys:

1. Identity law
7. Associativity law

## Set function
A set function is a function that can map every element in a set into another set. Set functions can be morphisms if the objects are sets. But not all morphisms can be described as set function even it's object is a set.

For example, say there is a category $(\mathbb{R}, \leq)$, its morphism is $f:x\rightarrow y, x\leq y$, its composition can be done by $x\rightarrow y \rightarrow z$ and $x\leq z$, its identity is $x\rightarrow x$. So this is a valid category on a set $\mathbb{R}$, but its morphism is not easy to describe by concrete functions.

## Functors
Functors map the objects from a category to another category, and the morphisms from a category to another category. If a morphism map a object to itself, it is called _**endomorphism**_, where _endo_ means "within inside" in Latin. Similarly, a functor that map a category back to itself is called _**endofunctor**_.

## Isomorphisms
You might have heard of [polymorphism](https://en.wikipedia.org/wiki/Polymorphism_(computer_science)). Which is similar to isomorphism. And also [xenomorph](https://en.wikipedia.org/wiki/Xenomorph). It is all Greek, *morph* means *form* or *shape*, *poly* means *many*, and *iso* means *equal*. So isomorphism means 'being of equal shape'.

In mathematics, and particularly category theory, an isomorphism is a translation with an inverse.

Another way to view this is to say that a lossless translation exists. When a translation is lossless, it means that you don't lose information by performing the translation. Since all information is still present after a translation, you can go back to the original representation.

For example, 2D coordinates could be stored as an array `[2,3]` or object `{x: 2, y: 3}`.

// Providing functions to convert in both directions makes them isomorphic.
const pairToCoords = (pair) => ({x: pair[0], y: pair[1]})

const coordsToPair = (coords) => [coords.x, coords.y]

coordsToPair(pairToCoords([1, 2])) // [1, 2]

pairToCoords(coordsToPair({x: 1, y: 2})) // {x: 1, y: 2}

### Endomorphism[](https://epogrebnyak.github.io/functional-programming-jargon/morphism.html#endomorphism)

A function where the input type is the same as the output.

// uppercase :: String -> String
const uppercase = (str) => str.toUpperCase()

// decrement :: Number -> Number
const decrement = (x) => x - 1

### Homomorphism[](https://epogrebnyak.github.io/functional-programming-jargon/morphism.html#homomorphism)

A homomorphism is just a structure preserving map. In fact, a functor is just a homomorphism between categories as it preserves the original category’s structure under the mapping.

A.of(f).ap(A.of(x)) == A.of(f(x))

Either.of(_.toUpper).ap(Either.of("oreos")) == Either.of(_.toUpper("oreos"))

### Catamorphism[](https://epogrebnyak.github.io/functional-programming-jargon/morphism.html#catamorphism)

A `reduceRight` function that applies a function against an accumulator and each value of the array (from right-to-left) to reduce it to a single value.

const sum = xs => xs.reduceRight((acc, x) => acc + x, 0)

sum([1, 2, 3, 4, 5]) // 15

### Anamorphism[](https://epogrebnyak.github.io/functional-programming-jargon/morphism.html#anamorphism)

An `unfold` function. An `unfold` is the opposite of `fold` (`reduce`). It generates a list from a single value.

const unfold = (f, seed) => {
  function go(f, seed, acc) {
    const res = f(seed);
    return res ? go(f, res[1], acc.concat([res[0]])) : acc;
  }
  return go(f, seed, [])
}

const countDown = n => unfold((n) => {
  return n <= 0 ? undefined : [n, n - 1]
}, n)

countDown(5) // [5, 4, 3, 2, 1]

### Hylomorphism[](https://epogrebnyak.github.io/functional-programming-jargon/morphism.html#hylomorphism)

The combination of anamorphism and catamorphism.

### Paramorphism[](https://epogrebnyak.github.io/functional-programming-jargon/morphism.html#paramorphism)

A function just like `reduceRight`. However, there’s a difference:

In paramorphism, your reducer’s arguments are the current value, the reduction of all previous values, and the list of values that formed that reduction.

// Obviously not safe for lists containing `undefined`,
// but good enough to make the point.
const para = (reducer, accumulator, elements) => {
  if (elements.length === 0)
    return accumulator

  const head = elements[0]
  const tail = elements.slice(1)

  return reducer(head, tail, para(reducer, accumulator, tail))
}

const suffixes = list => para(
  (x, xs, suffxs) => [xs, ... suffxs],
  [],
  list
)

suffixes([1, 2, 3, 4, 5]) // [[2, 3, 4, 5], [3, 4, 5], [4, 5], [5], []]

The third parameter in the reducer (in the above example, `[x, ... xs]`) is kind of like having a history of what got you to your current acc value.

### Apomorphism[](https://epogrebnyak.github.io/functional-programming-jargon/morphism.html#apomorphism)

it’s the opposite of paramorphism, just as anamorphism is the opposite of catamorphism. Whereas with paramorphism, you combine with access to the accumulator and what has been accumulated, apomorphism lets you `unfold` with the potential to return early.