Science Loves Declarative Style [2]
… and why not for loops?
It is the second chapter of Science Loves Declarative Style, and you can navigate to the previous chapter clicking here.
Real-Life Use-Cases Of Functional Programming
Now that we know what a relation / function / universal set is and understand some of the most basic functional programming patterns. In the next section, we will learn more about 3 main fields, for which functional programming fits better:
- Probability Theory
- Relational Databases
- Math Language
#1: Probability Theory
Notations:
- Ω is the set of all possible values for an experiment, it can be Ω = ℝ or Ω = ℕ. We assume that n = |Ω| is the number of elements in Ω.
- X : Ω → ℝ is a random variable mapping each value of Ω to another set of real numbers. A shorthand set notation for X(w_i) = x_i ∀ i ∈ {1, …, n} is: X(Ω) = {x_1, …, x_n}.
- A ⊆ Ω is an event set filtering each value based on a condition, it can be {w ∈ Ω | w ≥ 4}, {w ∈ Ω | X(w) ≥ 40}, {w ∈ Ω | ∃ x ∈ X(Ω) : X(w)= x}. Alternatively, we can define a characteristic function: I_A(w_i) = 1 if w_i ∈ A else 0, which marks the values that A contains as 1 and others as 0.
- ℙ : Ω → [0, 1] is the probability function reducing the given set to its probability of happening.
For example if we wanted to calculate ℙ(X(A) = x) for any x ∈ ℝ, we would start from the bottom and:
- select A ⊆ Ω from the universal set Ω,
- then map each element a ∈ A to x ∈ X(A),
- then select a for which X(a) = x,
- and finally summarize the resulted {X(A) = x} to a probability by counting the number of elements inside and dividing it by n.
In this special case: Coding in functional style is easier.
#2: Relational Databases
In SQL, relations are the key data structure.
Every answer is a relation.
If you have read my previous article on Logic is Built On Relations, you can find some hidden connections.
I found this online database here. Let’s look at the results of a few SQL queries:
- Getting all records from the table
- Getting all records of customers living in Germany but not in Berlin
- Counting the number of records grouped by countries without customers living in Berlin
- Counting the number of records in Germany without customers living in Berlin
As you may have noticed, every answer is a set of tuples, a collection of records, even if it is just a cell (see the 4th example).
Operations fit very well for MapReduce pattern.
#3: Math Language
In my opinion: If math language was written in a programming language, it would be more likely in Haskell than C.
I think you’ve read so far, so you have an idea of how does MapReduce pattern looks like in real-life use cases.
In this section, we will rather talk about the very little details that lead to the biggest conclusions.
Statelessness: The defined functions (and variables) hold the same values regardless of the current line we are reading. That means, if we would debug a program written in an universal math programming language:
- We would not see a change in values of already defined variables jumping from line A to B.
- The number of variables would increase continuously till we reach the end of the program.
- The number of variables would not decrease at any time point.
Statements using “”: Note that the default notation for functions is prefix, e.g. f(a, b), but we can also use the infix notation for functions with 0, 1 or 2 arguments, e.g.:
- a “f” b ≙ f(a, b): 2 arguments
- a “f b” ≙ f_{b}(a): 1 argument
- “a f” b ≙ f_{a}(b): 1 argument
- “a f b” ≙ f_{a, b}(): 0 argument (no variable outside the “” double quotes)
With this in mind, every statement like “x is a number greater than 9” or “8 is greater than 80” are also functions with no arguments.
Very basic example of fibonacci numbers, showing the functionality of “”:
- We assume fib(n) calculates the n-th fibonacci number.
- isFib : ℝ → {0, 1} is a function which identifies the fibonacci numbers.
- It is defined as isFib(x) = ∃ i ∈ ℕ, i ≥ 2: x = fib(i-1) + fib(i-2).
- Normally, we write in prefix notation: {x ∈ ℝ | isFib(x)}.
- Converting it to infix notation, it looks like: {x ∈ ℝ | “isFib” x }.
- If x is assigned e.g. 5, isFib(x) = isFib(5) becomes a variable.
- Since isFib(5) is a variable, it does not have any extra variables outside the “” double quotes.
- So isFib(5) becomes “5 is a fibonacci number” in human language.
- So it makes sense to write {x ∈ ℝ | “x is a fibonacci number” }.
No pseudocode: In maths, it is a very rare case that an imperative pseudocode is written. There is no defined FOR or WHILE construct totally written in symbolic language. That’s why WHILE language is created.
A WHILE program for calculating the average of given set A:
- Arguments: a_1, …, a_n (Elements), n (Number of elements in the set)
- Returns: m
Now let’s look at the mathematical definition: Let n = |A| and a_1, …, a_n ∈ A, then m := (a_1 + a_2 + … + a_n) / n.
- a_1 + a_2 + … + a_n is a recursively defined function with start index = 1, step size = 2–1 = 1 and stop index = n.
- If we would write it in prefix form, it would look like: +(a_1, +(a_2, …+(…, a_n))).
- The prefix version could be executed in functional programming using reduce().
- In this case, some function like →reduce(i ∈ ℕ, i≤ n, acc = 0 | a_i + acc) could perform very well.
Is-an-Element-of Relationship:
n ∈ ℕ is not an objection to my conclusion. It means that n doesn’t really actually exist at all! When we define {i ∈ ℕ | “i is an even number”}, actually no such variable i exists. It is an abstraction for each number {2, 4, …}, and not a counter variable.
Likewise, in a statement like “Let n ∈ ℕ any natural number. Then P(n).” outside of a set, it is not a variable, it is an abstraction.
Inductive Definitions: Recursion rather than iteration.
Defining a general boolean formula using an infinitely large WHILE-loop is possible, but most likely not a good idea. Instead, boolean formulas are defined using inductive definitions.
Let’s say that P(n) is a valid boolean formula, given n ∈ ℕ is any number.
Recursion start — P(0) is a variable or truth constant, so it is a boolean formula.
Recursion step — If P(n) is a valid formula, then P(n+1) is a valid formula, for each n ∈ ℕ, n ≥ 0:
- Assuming P(n) is a valid formula.
- If P(n+1) is defined as NOT P(n), it is still a boolean formula.
- If P(n+1) is defined as P(n) logically linked to a variable X by junctors such as AND, OR etc, it is a boolean formula.
Recursion end — {no end if the set in the recursion step is infinitely large}
Beyond this Article
Firstly, we made a brief introduction to declarative (and functional) programming.
Then we learned more about math concepts such as functions, relations and universal set, which are most heavily used in logic, and then the most important functionals in functional programming (map, filter, reduce).
After we grasped the basics of the functional programming and useful notations, we analyzed the language structures and formats of 3 main fields from the perspective of a functional programmer, such as Probability Theory and Relational Databases.
Finally, we challenged ourselves to find a few basic styling rules in math which is easily associated with functional programming.
Declarative programming rules the world :)
It is the second chapter of Science Loves Declarative Style, and you can navigate to the previous chapter clicking here.
