wiki:FunctionalProgramming/WhatIsFunction

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

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 Lists:

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

Last modified 6 months ago Last modified on May 29, 2020, 11:09:56 AM
Note: See TracWiki for help on using the wiki.