# 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`

- which is just 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.

## Inductive proofs

## 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).

**Note:**See TracWiki for help on using the wiki.