Functional Style Programming Using C

Learning programming and learning programming language are not the same. Most of our textbooks teach us programming languages. In truth, a programming language is just a tool that we use to implement an executable program. We need resources that teach us how to solve problems using a programming language.

As early as elementary school, we learned what is a mathematical function and how to write it. For example, f(x)=x^2 is a simple quadratic function.

A function describes a mathematical statement. The above function maps the relationship between two sets of natural numbers as given at the right in the graph below. Often, it is impossible to show such a mapping graphically when we have a large number of discrete elements in either of the sets. Therefore, for convenience, we express a function by writing it as an inherent relation between the sets.

This is perhaps the simplest way to demonstrate relationships when we deal with sets of numbers (integer, natural number, real numbers, complex numbers, etc.)

We can also think of a function as a machine which has taken in inputs and produces an output by using a mechanism that maps the relationship from input to output. The sets to which the inputs and output belong are also important. A function often has a name that allows us to identify it. Typically a function is deterministic, it can produce only a single output from a unique set of inputs.

Using different mathematical strategies, we can solve problems under various domains.

One philosophical foundation of computer programming was to represent or express all kinds of mathematical problems by a single language and solve them using generalized mathematics. The result was two equivalent systems, the Turing machine and lambda calculus.

The concept of a Turing machine influenced imperative programming paradigm such as those of Assembly, C, C++, Java, Ruby, Python, and other programming languages.

On the other hand, lambda calculus influenced the birth of several functional languages such as LISP, ML, Haskell, and Erlang.

Although we can solve many more problems by using those programming languages than by using high school math, it is often easy to learn programming by solving smaller problems first. In this book (or booklet), we will learn how to solve a problem of known category. In the beginning, we will see how a simple arithmetic function can be converted into a computer program. Later, we will learn to convert more complex functions. We will also learn how to compose a function using other functions. A function can also be built using itself through recursion. We will see how they can be converted using usual pattern matching.

Rather than learning alien text, we will try to use our common sense, simple IQ and pattern matching to convert a mathematical function into a computer program. Although we will write all the code in the language C, any other language can be used instead. If we use other languages, we may need to transform the given programs to that target language. So, if we do not know any other language, it is better to stick to C.

Anyway, instead of coding (writing in a computer to execute it physically) the converted code in this book, we will try to learn the programs by jotting it down independently. Initially, most problems given here are small and easy to write on a notebook (paper) by pen or pencil. In this way, the learner becomes familiar with the relationship between theoretical formulas and the implemented programs.

We will convert some basic functions into programs in this section. First, we will see how to write programs for unary functions. Later, we will learn the same of binary and n-ary function.

The identity function (or a function in which output mirrors the input) looks like this:

Function id(x) = x can be converted into:

Successor functions use the + operator to add 1 to the input and return its successor.

Function suc(x) = x + 1 can be converted to:

This is defined as twice(x) = 2x in arithmetic.

In C, the same function takes the form below.

This function is defined as square(x) = x^2 arithmetically.

In C, it takes the form below.

Here we present a pictorial representation of the above function square where the parameter x is mutiplied with itself to produce and return the result.

In arithmetic, the function is defined as: poly_1(x) = x^2 + 1

It can be converted into a programming function as shown below:

In arithmetic, the function is defined as: poly2(x) = x^4 + x^2 + 1

It can be converted into a programming function as shown below:

This can be simplified:

It can be converted into a programming function as:

Convert the arithmetic functions into programming function:

1. f1(x) = x + 2$ $f2(x) = x^3$ $f3(x) = 2x^2 + 3

2. f4(x) = 3x^3 + 4x^2 + 7$ $_1(m) = m(m+1)(2m+1)/6

3. sumOfSquare_2(m) = m^3/3 + m^2/2 + m/6$ $_1(m) = (m(m+1)/2)^2

4. sumOfSquare_2(m) = m^4/4+m^3/2+m^2/4

5. (y) = y - 1

6. (z) = z / 2

function, such as ‘add’ in arithmetic can be defined as: add(x, y) = x + y

It can be converted into a programming function as:

function in arithmetic – addSquare(x, y) = x^2 + 2xy + y^2

It can be converted into a programming function as:

Now we will solve a problem of determining the larger number between two numbers. In this case, we will construct a function that takes two parameters and it will return 1 if the first parameter is larger than the second parameter and 0 otherwise. For that we will introduce a new operator >.

a > b is 1 or (True in meaning) if a is larger than b. Otherwise it is 0 (False in meaning). So, our function is – isLarger(x, y) = x > y

The corresponding program is:

Convert the arithmetic functions into programming function:

1. sub(x,y) = x - y

2. addOfSquare(x,y) = (x times x) + (y times y)

3. subOfSquare(x,y) = (x times x) - (y times y)

4. subOfSquare_1(x,y) = (x+y)(x-y)

5. g(a,b) = a + ab + b

Write functions in arithmetic and programming to – multiply two numbers. calculate average of two numbers. determine if the two given numbers are equal. determine if the two given numbers are not equal.

A ternary function takes three parameter. For example: avgOfThree(x, y, z) = (x + y + z) / 3

It can be converted into a programming function as:

In a n-ary function, number of parameters is n. In this example, square of distance is an useful function to compare two distances.

The squareOfDistance function: squareOfDistance(x_1, y_1, x_2, y_2) = (x_1-x_2)(x_1-x_2) + (y_1-y_2)(y_1-y_2)

Can be converted into a programming function as:

A function can be composed using other functions. It often simplifies the expression. For example, the function, squareOfDistance can be simplified if we use the function square. It is shown here:

Let us write it in a programming language:

Here we can see that the function squareOfDistance1 is using two copies of the function square. It is very important to understand.

The old function was defined as Poly2(x) = x^4 + x^2 + 1.

Now we will re-define it as Poly2_1 using the function square:

In C, we can write it as:

The old function was defined as sumOfQube_1(x) = (x(x+1)/2)^2.

Now we will re-define it as sumOfQube using the function square and sum:

In C, we can write it as:

1. Prove that:
   1. x^3 = x times square(x)
   2. x^8 = square(square(square(x)))
2. Simplify them by composing other functions and write programs accordingly:
   1. qube_c(x) = x^3
   2. toPower8(x) = x^8
   3. toPower4(x) = x^4
3. Write programs for:
   1. parabola(a,b,c,x) = ax^2 + bx + c
   2. square_p(x) = parabola(1,0,0,x)
   3. qube_p(x) = parabola(x,0,0,x)
4. Write program for toPower4_p(x) = parabola(parabola(1,0,0,x),0,0,x) and prove that toPower4_p(x) = x^4.

From this chapter, we will not write same function twice.

In a function, we may get different result based on different conditions on the parameters. For example, the function absolute negates its parameter if it is negative so that it can be turned into positive (negative of negative is positive) to produce the result. Otherwise (when parameter is already positive), it returns back the result exactly same as the parameter. Thus, the function can be written as:

Compute based on conditions of parameters.

The general idea of a conditional function is as follows:

The corresponding code is:

Now we will present some functions those use conditions.

It's code:

Its code:

By composing functions, we can construct many familiar functions. Although they are not always more efficient, for obvious reason, we will do it.

Here the function abs is rewritten as:

In C:

Lets think a problem.

Calculate your total tuition fee due based on the condition that if your due of previous semester tuition fee is more that 1000 currency, your total fee to pay this semester will be double of previous due plus the fee of current semester. We can write a function to describe it mathematically.

If we use the function switcher, we can rewrite it as:

or,

In programming, the functions are:

Well, the parameters p and c does not mean anything. So, often it misleads us if we use meaningless names. It is also important to be able to read them easily. We can take different approaches to avoid confusions and increase readibility. They are shown as the function tftp2 is rewritten as:

Or, in the best style:

Or, in a good style:

Or, we can write a word to keep it small and yet understandable:

In this example, we will solve a problem of determining the grade letter based on the total mark in an examination. The grade distribution is given at the right side.

The function that solves the problem is:

Hence, the code for the above function is:

In the above example, the function gives us a numeric value that in our mind represents a grade. But it is often necessary to give user a direct result instead of a numerical representation. If the function can generate result with letter grades directly, it will be definitely more understandable as shown here:

Since the letter grades are actually letters or characters, we need to change the data type of the function to ‘char’. ‘char’ type corresponds to the characters. In other words, ‘char’ is the set of all characters or visible symbols a computer can show.

The code for the above function is:

In this example, we will solve a problem of getting prices of different items in an restaurant. We will determine an item by its item no. The prices for different item numbers are given at the right.

The function that solves the problem is:

Hence, the code for the above function is:

Note: 2^{31}=2,147,483,648 and 2^{63}=9,223,372,036,854,775,808

For a realistic approach, we can add a simple function with it that calculates total price of an item for a quantity:

The code:

Recursion is a technique that enhances capabilities of programs very much. For example, if we want to write an exponential function exp(x,k)=x^k, we understand that x have to be multiplied to itself k times. We can understand x^k operation from our childhood mathematics. But unfortunately C programming language does not have operator for exponential operation. We can also understand k times and we can repeat this multiplication by counting 1 to k.

But how to write the function using multiplication only? We can write exp(x,k)=x times x times dots times x (k times). If we knew k is 2, the expression becomes exp(x,2) = x times x, if it is 3, the expression is exp(x, 3) = x times x times x and so on. But when k is unknown, then it is difficult to write in very clear way. Most importantly, C programming does not support any expression like ‘x times x times dots times x (k times)’.

We use recursion to express such functions or programs. Recursion is a special kinds of composition where the definable function itself is composed with something else to define itself. It may heard weird or twisted at the first time. We will see some analogous definition in our society to understand its power.

But just imagine a simple definition of human (according to Quran and Bible):

‘Adam and Eve were human and any living mammal that borns from another human is a > human’.

This definition certainly covers all the humans. Here human is defined from the definition of another human and it is called recursion or induction. In recursive (or inductive) defintion, there must be at least one base point for example ‘Adam was human and Eve was human’.

Let us take another example, the definition of natural numbers. Suppose we have all kinds of numbers on our knowledge including real numbers, complex numbers, etc.. We need to define natural number. Here is the plain definition - 0 is a natural number and n+1 is a natural number if n is a natural number. We can use it to write a function to know whether a number is natural

Similarly we can write another function to distinguish an animal as human:

It says, x is a human if x is Adam or Eve. x is not human if x is Amiba. Besides x is also human if and only if mother of x is also human. Well, in the real process, to justify an animal as human, we need to know the total family tree from Adam and Eve which is very unrealistic. But the definition itself is very intuitive.

In mathematics and computer science, this recursive style of definition often expresses a fact in a very simple and intuitive way, which helps to formalize an algorithm or program in very effective way.

To create a recursive definition of a function, we need to forget how it really works. We simply need to know if the definition is correct mathematically.

For an easy construction of the definition, here we would like to present a tips. We have to remember that the function has one (or more) driving parameter(s).

1. Base cases part

   Need to determine the value of the function for the base case(s) of the driving parameter(s). For example, exp(n,x)=1 when x=0.

2. Recursion part

   The function itself will be appeared with smaller (typically 1 step) value or size of the driving parameter(s). For example, exp(x-1). This is called induction hypothesis (HI).

   • The induction hypothesis often needs to be computed with something else to be equal to the original definition. For example, exp(x)=x times exp(x-1).

   • Other parameters remain the same in recursion call inside the body.

If we follow the above steps, it will help us to construct recursive definition. We will explore some examples soon. In some examples, we will see how the function is constructed from the above tips. We will also see whether definition is correct.

We will define exp(x,k). Here x is the base and k is the power. So, k is the driving parameter. Now we know the base case when k=0 - exp(x,0) = 1. Next, we will have to construct the recursion part. First, we know that the expression exp(x,k-1) exists in this part because the 1 step smaller value of k is k-1. x will remain same. Now it is necessary to multiply it to x to be equal to exp(x,k). Therefore, the full expression becomes exp(x,k) = x times exp(x,k-1). Now together the function is looks like:

Obviously, the code for the above function is:

Proof of correctness

Let us see whether the above function, exp(x,k) is really x^k. We can prove it by using induction on k.

Case 1. k=0.

| ---------------|-------------- exp(x,0) = 1 |…(1) from the function x^0=1 | …(2) naturally herefore exp(x,0) = x^0 | from (1) and (2)

Case 2. k eq 0.

We want to prove that exp(x,k)=x^k. So, naturally exp(x,k-1) supposed to be x^{k-1}. We will take this as the induction hypothesis.

| ------------------|------------------ exp(x,k-1) = x^{k-1} | …(1) by induction hypothesis so, x times x^{k-1} = x^{k-1+1} | we know from arithmatic so, x times x^{k-1} = x^k | k-1+1=k so, x times exp(x,k-1) = x^k | from (1) herefore exp(x,k) = x^k | from the function

Factorial is another arithmetic function that is informally, x! = x times (x-1) times ... times 1 . We can define it recursively. First, it has the only parameter, x. We know that x can be at least 0 and factorial(0)=1. This is our base part. Now in the recursion part it must contain factorial(x-1). Finally, we can multiply it with x to make it equal to factorial(x). See the proof later for a better understanding.

Now our function looks like:

Obviously, the code for the above function is:

Proof of correctness

Let us see whether the above function, factorial(x) is really x!. We can prove it by using induction on x.

Case 1. x=0.

factorial(0) = 1 by definition, 0! = 1

Case 2. x eq 0.

We want to prove that factorial(x)=x!. So, naturally factorial(x-1) supposed to be (x-1)!. We will take this as the induction hypothesis.

| -------------|---------------------------------------------------------------- factorial(x-1) = (x-1)! | …(1) by induction hypothesis (x-1)! = (x-1) times (x-2) times ... times 1 | expanded form so, x times (x-1)! = x times (x-1) times (x-2) times ldots imes 1 | multiplying both side by x so, x times factorial(x-1) = x! | from (1) herefore factorial(x) = x! | from the function

Now our function looks like:

Obviously, the code for the above function is:

Obviously, the code for the above function is:

Write a recursive function to represent multiplication of two numbers by using only addition. Write a recursive function to represent integer division of two numbers by using only subtraction.

Can be rewritten as:

In C:

A similar, in fact, more generalized series is:

It can be rewritten as:

It is converted into the program:

A general product series can be rewritten as:

See how we can get a product series from the previous series by only changing the base case result and by replacing + by times in the recursion part. Obviously, we should change the name of the function.

Here is the code:

In this example, we will calculate the natural square root of a number n. A natural square root is a natural number that is an integer and also positive. We will examine a very easy function to do that. In this function, 0 will first be tested if it is the square root of n. If the square root of n is not a natural number, the smallest larger value (sqrt{n}+1) will be accepted as an approximation. For each test fails, the next natural number will be tested similarly.

The logic behind the condition square(k) >= n is that sqrt{n} = k if and only if k^2 = n and sqrt n+1 = k+1 and then (k+1)^2 > n. Since the value of k is increasing from 0 one by one, either sqrt n of sqrt n+1 will be accepted as the natural square root of n.

Can you explain how the code below determines a number as a prime?

Problem: Suppose we have a two-dimensional grid of N columns and M rows. We name a cell of it in terms of its vertical and horizontal index (x,y). We have a robot that can move either to one cell left or one cell below. It cannot cross the border of the grid indeed. Let’s place the robot at any cell in the grid and our current challenge is to know the number of ways it can reach to the bottom-left most corner, cell (0,0).

Solution: Lets imagine a grid of N=9 columns and M=5 rows where the robot is placed at the cell (6,3). The goal of its move is to reach the cell (0,0). It can move only downward or left.

If the robot is placed in the cell (0,0), it needs 0 move to reach the goal and hence trivially there is only one way to reach the goal. From all the cells in the left-most column ((0,1), (0,2), ldots), the robot can move only downward. So, from each of these positions (where x is 0), the robot has only one way to reach the goal. Similarly, from all the cells at bottom-most row (where y is 0), it has only one way to reach the goal. From any other cell, the path to reach the goal depends on its left and below adjacent cells. So, the number of possible ways to reach the goal can be determined by adding that of those two cells. So, our function is as follows:

Now we can write our function in C very easily: