**Applicative Laws**. Valid implementation of the `Applicative`

type-class must satisfy all of the following laws:

`pure id <*> pure x`

$\equiv$`pure x`

$\Rightarrow$ Identity.`pure f <*> pure x`

$\equiv$`pure (f x)`

$\Rightarrow$ Homomorphism.`pure f <*> pure x`

$\equiv$`pure (\h -> h x) <*> pure f`

$\Rightarrow$ Interchange.`pure (.) <*> pure g <*> pure f <*> pure x`

$\equiv$`pure g <*> (pure f <*> pure x)`

$\Rightarrow$ Composition.

where

`id`

is the identity function of type`a -> a`

,`f`

is a function of type`a -> b`

,`g`

is a function of type`b -> c`

,`x`

is a value of type`a`

, and`(.)`

is the function composition operator of type`(b -> c) -> (a -> b) -> a -> c`

.

**Applicative**. The `Applicative`

type-class represents an applicative `Functor`

.

```
class Functor f => Applicative (f :: * -> *) where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f a
```

A minimal complete definition requires only the implementation of `pure`

and `<*>`

(or `liftA2`

), but it must comply with the Applicative Laws.

**Bijective Function**. A function is *bijective* if it is both injective and surjective. In other words, there’s a one-to-one correspondence between the function’s domain and codomain. Consequently, the cardinalities of the domain and codomain must be same. Also, there must exist an inverse function for all *bijective* functions.

For example, the boolean function `not`

is *bijective*:

```
not :: Bool -> Bool
not True = False
not False = True
```

In this case, it also happens to be its own inverse function.

**Binary Operator**. A *Binary Operator* is a function with exactly two parameters. For instance, the mathematical `+`

takes two numerical values as parameters and returns their sum (i.e., another numerical value). Usually, *Binary Operators* appear “infix” (i.e., between the parameters) in expressions (e.g., `a + b`

).

**Cabal**. *Cabal* is Haskell’s package manager. See also Stack.

**Char**. `Char`

s are one of Haskell’s the basic built-in types, representing a single letter.

**Commutativity**. A *commutative* binary operator produces the same result, regardless of the order of its parameters. For instance, mathematical addition is *commutative* (i.e., `1 + 2 == 2 + 1`

), but mathematical substraction is not (i.e., `1 - 2 /= 2 - 1`

).

**Constant**. A *constant* is a pure function without parameters. Due to being pure, it can only ever return a single value. Example:

```
pi :: Double
pi = 3.14156209
```

**Elm**. *Elm* is a Functional Programming language, targeting the web. The compiler produces JavaScript for execution in a web browser. The language is syntactically very similar to Haskell, but semantically less powerful (e.g., no support for type-classes).

**Endomorphism**. An *endomorphism* is a homomorphism whose domain and codomain are the same.

**Expression**. An expression is a value constructed from the application of functions or operators to other values. The parameters of the functions or operators are called the terms of the expression. For example, `a + b`

is an expression, which computes the sum of the terms `a`

and `b`

.

**Function Application**. Function Application is a term for the call/invocation of a function. For instance, the function `doubleIncrement`

applies the function `increment`

two times:

```
doubleIncrement :: Integer -> Integer
doubleIncrement = increment . increment
where increment :: Integer -> Integer
increment x = x + 1
```

**Function Composition**. *Function Composition* is the definition of a new function by combining two existing ones. In Haskell, the Binary Operator to *compose* two functions is called `.`

and is defined as follows:

```
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(.) g f = \x -> g (f x)
```

Needless to say, *composition* requires the type of the return value of `f`

to be compatible with the type of the parameter of `g`

. Example:

```
f :: a -> b
f = undefined -- placeholder
g :: b -> c
g = undefined -- placeholder
h = a -> c
h = g . f
```

**Function**. *Functions* are the elementary building block in functional programming. All *functions* have a domain (zero or more parameters) and a codomain (return value) and can be characterized in various ways:

- Pure or impure.
- Total or partial.
- Injective, surjective, or bijective.
- Higher-order or not.
- Homomorphism, endomorphism, or isomorphism?

**Functional Programming**. *Functional programming* is a paradigm, in which the programmer defines a set of mathematical functions and composes these functions to form the overall system. Functions are first-class citizens, meaning they can be passed around just like other values, enabling higher-order functions. Usually, programs are partly functional and partly imperative.

**Functor Laws**. Valid implementations of the `Functor`

type-class must satisfy all of the following laws:

`fmap id`

$\equiv$`id`

$\Rightarrow$ Identity. If the values are mapped onto themselves, the result must be an unmodified Functor.`fmap (g . f)`

$\equiv$`fmap g . fmap f`

$\Rightarrow$ Composition. If two sequential mappings are performed using two functions, the result must be the same as a single mapping using the composition of the two functions.

where

`id`

is the identity function of type`a -> a`

,`f`

is a function of type`a -> b`

,`g`

is a function of type`b -> c`

, and`(.)`

is the function composition operator of type`(b -> c) -> (a -> b) -> a -> c`

.

**Functor**. The `Functor`

type-class represents a value that can be mapped over. In Haskell, the definition of the type-class looks as follows:

```
class Functor (f :: * -> *) where
fmap :: (a -> b) -> f a -> f b
(<$) :: a -> f b -> f a
```

A minimal complete definition requires only the implementation of `fmap`

, but it must comply with the Functor Laws.

In real-world programs, you often see the binary `<$>`

operator, which is defined as an alias of `fmap`

.

**GHC**. The Glasgow Haskell Compiler is the de-facto standard implementation of Haskell. It’s by far the most popular and most advanced compiler in the marketplace.

**Haskell 2010**. The latest version of the Haskell standard and successor of Haskell 98.

**Haskell 98**. The first version of the Haskell standard and predecessor of Haskell 2010.

**Haskell**. *Haskell* is a general-purpose functional programming language. A committee designed the language and produced an official standard, defining the core language. In practice, it’s very rare to see projects using standard *Haskell*, since there are numerous widely-used language extensions, provided via GHC.

**Higher-Order Function**. *Higher-Order Functions* receive a function as a parameter, return a function, or both. For instance, `fmap`

as defined in the `Functor`

type-class is a *higher-order function* because its first parameter is itself a function.

**Homomorphism**. A *homomorphism* is a map between two algebraic structures, that preserves the operations of the structures. In mathematical terms, it means that a function $f$ is a *homomorphism* if the following statement holds for a binary operation `@`

:

**Identity Function**. The *identity function* or `id`

is a pure function with a single parameter, that returns the aforementioned parameter. In other words, it’s a function that does nothing.

```
id :: a -> a
id x = x
```

**Imperative Programming**. *Imperative Programming* is a paradigm in which the programmer specifies an ordered sequence of steps to be processed by the computer. This includes both object-oriented languages like JavaScript as well as procedural languages.

**Impure Function**. An impure function, by definition, interacts with the outside world not only through its domain and codomain. Instead, it also reads/mutates global state or performs `IO`

operations. `IO`

is pretty broad because it also includes generating random numbers, getting the current date/time, and so on.

**Injective Function**. A function is *injective* if it maps distinct values of its domain to distinct values of its codomain. If a function is both injective and surjective, it’s called bijective.

**Integer**. *Integers* are the set of whole numbers. This includes all natural as well as negative numbers. The Haskell type to represent arbitrary precision *integers* is called `Integer`

and defined in the `GHC.Num`

/`Prelude`

modules.

**Inverse Function**. Given a function `f`

such that `f x == y`

, the inverse function `g`

is defined such that `g y == x`

. Many functions are not reversible. Specifically, the function must be bijective to be reversible.

**Isomorphism**. A special kind of homomorphism.

**JavaScript**. *JavaScript* is the imperative language of the web. There are functional languages such as Elm available that compile to *JavaScript*.

**Lambda Function**. A Lambda is an anonymous (i.e., has no assigned identifier) function. Example:

```
squares :: [Integer]
squares = fmap (\x -> x * x) [0..]
```

**Laziness**. *Laziness* and strictness are evaluation strategies. A programming language is *lazy* if it never computes more than it needs to at a particular time. For example, the list comprehension `[0..]`

denotes an infinite list and, therefore, would take an infinite amount of time and memory to compute fully. A *lazy* language, however, allows for partial evaluation on demand and then stops. So, expressions like `take 5 [0..]`

are no problem for languages with *lazy* evaluation, but would never terminate in languages with strict evaluation. For instance, Haskell is a *lazy* language.

**List Comprehension**. *List comprehension*s are short-hand expressions to construct certain kinds of lists. The created lists can be finite or infinite.

```
minusTenToPlusTen :: [Integer]
minusTenToPlusTen = [-10 .. 10]
evenNaturalNumbers :: [Natural]
evenNaturalNumbers = [n | n <- [0 .. ], n `mod` 2 == 0]
```

**Literal**. A *literal* is the simplest expression possible: It’s just a plain value like `123`

, `3.1415`

, `"foobar"`

, and so on. Depending on the language, there are different types of *literals* supported.

**Monad Laws**. Valid implementation of the `Monad`

type-class must satisfy all of the following laws:

`m >>= return`

$\equiv$`m`

$\Rightarrow$ Right Unit.`return x >>= f`

$\equiv$`f x`

$\Rightarrow$ Left Unit.`(m >>= f) >>= g`

$\equiv$`m >>= (\x -> f x >>= g)`

$\Rightarrow$ Associativity.

where

`f`

is a function of type`a -> m b`

,`g`

is a function of type`b -> m c`

,`x`

is a value of type`a`

, and`m`

is a value of type`m a`

.

**Monad**. The `Monad`

type-class represents a computation that is sensitive with regards to the order of the operations within it.

```
class Applicative m => Monad (m :: * -> *) where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
fail :: String -> m a
```

A minimal complete definition requires only the implementation of `>>=`

, but it must comply with the monad laws.

**Natural Number**. A *natural number* is a non-negative integer (including `0`

). The Haskell type to represent arbitrary precision *natural numbers* is called `Natural`

and defined in the `Numeric.Natural`

module. The set of all *natural numbers* can easily be written as a list comprehension: `[0..] :: [Natural]`

.

**NoImplicitPrelude**. `NoImplicitPrelude`

is a GHC language extension to disable the automatic import of the `Prelude`

module.

**Operator Associativity**. Operator Associativity defines, together with Operator Precedence, the order in which expressions are evaluated. For instance, the expression `2 @@ 3 @@ 4`

is equivalent to `(2 @@ 3) @@ 4`

, if `@@`

is left-associative. If `@@`

were right-associative, it would be equivalent to `2 @@ (3 @@ 4)`

.

**Operator Precedence**. Operator Precedence defines, together with Operator Associativity, the order in which expressions are evaluated. For instance, the expression `2 * 3 + 4`

evaluates to `10`

, because `*`

has higher precedence than `+`

(i.e., `7`

vs. `6`

).

**Partial Function Application**. Partial Function Application happens if an `n`

-parameter function is applied with fewer than `m < n`

parameters. This application returns another function with `n - m`

paramters.

**Partial Function**. A *partial function*, as opposed to a total function, returns a result for only a subset of the values of its domain. Example:

```
head :: [a] -> a
head [] = undefined -- first element of an empty list?
head (x:_) = x
```

Using *partial functions* is considered to be bad practice in functional programming. It’s much better to use total functions as much as possible.

**Phantom Type**. A *phantom type* is a parameterized type whose parameters do not appear on the right-hand side of its definition.

```
data Validated
data Unvalidated
data FormData a = FormData String -- phantom type
validate :: FormData Unvalidated -> Maybe (FormData Validated)
validate (FormData string) = undefined -- placeholder
```

The purpose of *phantom types* is to provide additional type-information to the compiler. Specifically, if two types are data-wise identical, *phantom types* can be used to empower the compiler with type-only differences.

**Prelude**. `Prelude`

is a Haskell module, consisting of basic functions and types, that is imported by default. Many people like to use more modern alternatives, which is why GHC has a language extension called `NoImplicitPrelude`

to disable the automatic import of `Prelude`

.

**Pure Function**. A pure function, by definition, interacts with the outside world only through its domain and codomain. It cannot read or mutate global state or perform any `IO`

operations. `IO`

is pretty broad because it also includes generating random numbers, getting the current date/time, and so on.

**Recursion**. Recursion is a technique where a function calls itself. This is very common in Functional Programming because languages like Haskell and Elm lack loop constructs like `for`

, `while`

, or `do ... while`

.

**Section**. Let’s say you have a binary operator like numerical `+`

with the following type:

```
(+) :: Num a => a -> a -> a
```

In this situation, you use a so-called section to partially apply the operator:

```
(+) 3 :: Num a => a -> a
```

**Stack**. Cabal has many problems and is not particularly easy to use. For this reason, the community created another tool: Stack - a wrapper around Cabal with additional features like automatic installation of the appropriate version GHC.

**Strictness**. *Strictness* and laziness are evaluation strategies. A programming language is *strict* if it fully computes the current expression before proceeding to the next expression. For example, the list comprehension `[0..]`

denotes an infinite list and, therefore, makes no sense in a *strict* language. A lazy language, however, allows for partial evaluation on demand and then stops. So, expressions like `take 5 [0..]`

are no problem for lazy languages, but would never terminate in *strict* languages. For instance, Elm and JavaScript are *strict* languages.

**String**. A `String`

is a sequence of `Char`

s. Haskell defines `String`

s as a simple type alias:

```
type String = [Char]
```

`String`

s can be written as literals.

**Surjective Function**. A function is *surjective* if, for every element `y`

of its codomain, there is at least one element `x`

of its domain such that `f x = y`

. If a function is both surjective and injective, it’s called bijective.

**Total Function**. A *total function*, as opposed to a partial function, returns a result for all values of its domain. Example:

```
head :: [a] -> Maybe a
head [] = Nothing
head (x:_) = Just x
```

**Unary Operator**. A Unary Operator is a function with exactly one parameter. For instance, JavaScript’s `!`

operator takes a single boolean value as a parameter and returns its negation (i.e., another boolean value). Usually, Unary Operators appear “prefix” (i.e., before the parameter) in expressions (e.g., `!true`

). Both Haskell and Elm don’t have any Unary Operators.

**Unit**. Unit or `()`

is a special type with a single value that’s also referred to as `()`

. The purpose of this type is to represent “nothing”. Many Imperative Programming languages use the keyword `void`

to express this idea.