When one meets for the first time functional programming, the first impression is that some higher order functions are too hard to cope with and to understand the basics is a little tricky. In this post I’ll show that is not tricky at all to think functionally about basic functions – their definitions come from examples that we meet in our programming tasks.

A basic pattern met in programming is to compute values until some condition is satisfied.

For example:

until (> 100) (*2) 1 says the following: starting from the value 1, multiply it with 2 until you get a value greater than 100, and return the first value obtained that is > 100.
In other words: compute the list [1,2,4,8,16,32,64,128,256,…] and see which is the first element > 100. Obviously, it’s 128.

From this example, we can start to generalize step by step:

Step 1. When we multiply by 2, we can think of a function that does this multiplication for us (it takes the argument and multiplies it by 2):
f :: Integer -> Integer
f x = 2*x

Step 2. Reconstruct the example in terms of function f:

We can reconstruct the list in the following way:
[1,f(1),f(f(1)), …] = [1,2,4,…]

Step 3. Construct a function that decides if any of the elements 1,f(1),f(f(1)),… is greather than 100:
p :: Integer -> Bool
p x = x > 100

Step 4. If 1 is greather than 100, then return 1, otherwise take f(1) and test if is greather than 100 and repeat the procedure until the first element >100 in the list [1,f(1),…] is found.

More concrete, step 4 can be given in a recursive definition like this:
until (> 100) (*2) 1 = if p(1)>100 then 1 else until (>100) (*2)(f(1))

Step 5. Generalize the types.

The example given can be generalized in a natural way further. First of all, we can think of function f of being of any type “a” (Real numbers, Float numbers, etc.):

f :: a -> a

Also, because p is applied on the same type as the domain of f (on 1, from our example, which is from Integer), we can generalize it to any type:

p:: a->Bool

Moreover, 1 can be thought of being any fixed element x of the type-domain of f. In this way, x is of type a.

So,we can make general the step 4 and write the until function in this generic way:

until(p,f,x) = if p(x) then x else until(p,f,f(x))

The type of function until can be easily determined, because we know the types of the individual components (p,f,x) and we know it returns a value of type a:

until :: (a->Bool, a->a, a) -> a

The complete definition of function until is now:

until :: (a->Bool, a->a, a) -> a
until(p,f,x) = if p(x) then x else until(p,f,f(x))

But, if you search on internet, the type of the function until is more complicated, without using tuples. It uses only single arguments instead of tuples. Transforming types of functions from tuples to single arguments is the process named Currying.

As strange as it sounds, it is a simple process, which can be understood in the following way:

Let’s say that I’m given a function working on tuples: f::(a,b) -> c.
I can construct a function g :: a->(b->c) naturally from the function f: g(x)(y) = f(x,y).

The function g has single arguments, meaning that g(x) is another function that can take arguments. The function f has a tuple-argument, which makes it a different object than g. The reason for which we transform functions on tuples to work on single arguments is because there are mathematical results that are proved only on single arguments, so to apply them on more arguments leads naturally on conceiving a currying process which transforms tuple arguments functions into single arguments functions.

When we have 3 arguments, the currying process is also simple:

f :: (a,b,c) -> d becomes g :: a->(b->(c->d)), where g(x)(y)(z) = f(x,y,z)

And so, we arrive in a simple manner to the type of function:

until :: (a->Bool, a->a, a) -> a is equivalent with until1 :: (a->Bool) -> ((a->a) -> (a->a)), where we can omit the right parantheses (this is the rule for the types of functions):

until1 :: (a->Bool) ->(a->a) -> a->a
until1 p f x = if p(x) then x else until1 p f (f x)

One of the most interesting applications of the function until is computing the floor using binary search. You can find this in the amazing book of Richard Bird, Thinking functionally with Haskell:

Constantin Liculescu


Share Button