Project Inquiry

Glossary

Applicative Laws. Valid implementation of the Applicative type-class must satisfy all of the following laws:

  1. pure id <*> pure x == pure x (Identity)
  2. pure f <*> pure x == pure (f x) (Homomorphism)
  3. pure f <*> pure x == pure (\h -> h x) <*> pure f (Interchange)
  4. pure (.) <*> pure g <*> pure f <*> pure x == pure g <*> (pure f <*> pure x) (Composition)

where

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.

Bijective Function

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, and therefore the function is also involutory.

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. Chars 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:

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:

  1. fmap id == id (Identity). If the values are mapped onto themselves, the result must be an unmodified Functor.
  2. fmap (g . f) == fmap g . fmap f (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

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.

Injective Function

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.

Involutory Function. An Involutory Function is a function, that is it’s own inverse.

One typical example for such a function in Haskell is reverse :: [a] -> [a] to reverse the order of the elments in a list.

reverse . reverse == id

Note that Involutory Functions must be bijective. Furthermore, this also imply’s that function’s domain and codomain must be identical.

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

  1. m >>= return == m (Right Unit)
  2. return x >>= f == f x (Left Unit)
  3. (m >>= f) >>= g == m >>= (\x -> f x >>= g) (Associativity)

where

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.

Point-Free Style. Point-Free Style is a way of defining a function without reference to its parameters by calling a function that returns a function. Therefore, Point-Free Style depends on support for [higher-order functions][Higher-Order Functions].

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.

Property-Based Testing. With Property-Based Testing, you make use of “properties” that functions ful-fill. For example, take the follow function:

double :: Integer -> Integer
double x = x * 2

What can you say about this function, that is true for all possible parameters? Well, the values returned must alwasy be even numbers, don’t they? We can make use of this as follows: Apply double to a random integer and check that the result is even. In this way, we can automatically generate as many Integers as we need and test our function as many time as we want.

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 Chars. Haskell defines Strings as a simple type alias:

type String = [Char]

Strings 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.

Surjective Function

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.