# What Is a Function?

There are various contexts in which the notion of a mathematical function could be considered.

## A table

One of the canonical ways of (operationally) defining what a function is to consider it as a table.

A fixed set of pairs form inputs to outputs.

```((1 1)
(2 4)
(3 9)
(4 16)
...)
```

From this we could consider a set of inputs

```{1, 2, 3, 4, ...}
```

and set of outputs

```{1, 4, 9, 16, ...}
```

The set of inputs is traditionally called domain. The set of outputs is called range of a function.

These sets could (and should) be viewed as Types. It the simplest form a type is a named set of all possible values.

A function, then, maps values from one type, lets say `A` to another type `B`, which may or may not be the same type `A = B`.

```f :: A -> B
```

Notice that it is still a table lookup. We may say that it is a set of one-to-one mappings or pairs.

## Multiplication

There is a multiplication table

```((0 1 2 3 4 ...)
(1 1 2 3 4 ...)
(2 2 4 6 8 ...)
(3 3 6 9 12 ...)
(4 4 8 12 16 ...)
...)
```

Multiplication Table is abstracted as `(*)` - an infix binary operator (a function of arity 2).

It takes two numbers (in this case `Integers`) and returns a number.

```(*) :: Integer -> Integer -> Integer
```

## Function abstraction

A function `f :: a -> b` may be conceptually viewed as:

• a fixed lookup table
• a truth-table in Logic
• a mapping between two sets of values
• a set of arrows (morphisms) between pairs of values from `a` to `b`
• which is just a `Set` of unique pairs in a Cartesian Product
• whose number is precisely `b^a`
• a black-box abstraction (same input - same output)
• an enzyme (the basic building block of Life Itself)

A constant (a number or a symbol) could be viewed as a function of arity 0

• a "table" with just one element in it.
• its domain is an empty set `()` or a unit.
• its range is a set of just one element - a singleton.

No input, same output. Always.

If symbols and numbers are (could be viewed as) functions, then they may be overloaded (to have a different meaning depending on current context). This is what Haskell does.

## Connection to logic

When we have a function of type `a -> b` and apply it to a value of type `a` it will yield a value of type `b`. Same input - same output. Always.

If we have a proof that `A => B` and a proof of `A` we could conclude `B`

```(a ⇒ b) × a ⇒ b
```

Where `×` is operator for Cartesian product (which gives us a `Pair` or `Set` of `Pair`s).

## Partial functions

For a function defined by pattern-matching (on a sum-type) each clause is a partial-function (a function that accepts a subset of the domain).

```fmap :: (a -> b) -> Maybe a -> Maybe b
fmap _ Nothing = Nothing
fmap f (Just x) = Just (f x)
```

## Equational reasoning

In most of functional languages functions are defined by equations.

Each side could be mechanically substituted for another.

```fmap f Nothing
```

could be substituted to `Nothing` in the context of the `Maybe` Monad.

## Substitution

Substitution of equal for equal is the most fundamental proof technique in mathematics.

Each substitution is justified by some prior result (and can be mechanically proof-checked).

## Recursion

A recursive process is an abstraction of a universal spiral-shaped process.

It is a process of convergence to a base case by calling itself on a smaller (improved) case - reduced version of a problem.

A spiral-shaped process embodies an advancement instead of repetition (an endless loop) - an expansion (following by a contraction) instead of mere osculations.

## Partial application (using Currying)

Applying a multi-arity function to a fewer arguments (and therefore creating a closure) defines a partial application.

Partially applied function returns another function (this is what Currying is) thus lifting the resulting function into a different domain.

A higher-order `map` function of a function (and a List):

```map :: (a -> b) -> [a] -> [b]
```

Partially applied map is a function on `List`s:

```(map (+1)) :: Num b => [b] -> [b]
```

## Container

A function could be viewed as a container. Well, sort of.

A function call can be memoized (cached) so a function execution can be turned into a table lookup.

This is actually an important and deep concept, but by no means an obvious one. A function, applied to some value, returns a new value. This value is always the same when the same argument is given.

So, a function could be mapped over such "container" - another function, given that the types are correct.

```fmap f g = f . g
```

Notice than function composition operator `(.)` is just nesting

```(.) f g = \x -> f(g x)
```

Which is one of the most fundamental principles in whole Nature.

Nesting of functions (which forms a pipeline) is the only way to explicitly define a particular order of evaluation is lazy (call-by-need) languages such as Haskell.

Everything is orthogonal but fits together perfectly. Remember, that `Lambda Calculus` and math are call-by-need.

## Implementation

An infinite table cannot serve as an implementation of multiplication.

So, it is just a repeated addition. How many times to take something (add to itself).