Today we’re going to play around with functional programming. Yay !

• Ok, what’s that exactly ?

Wikipedia says it pretty much:

functional programming is a programming paradigm, a style of building the structure and elements of computer programs, that treats computation as the evaluation of mathematical functions and avoids state and mutable data.

• Alright, now let’s have some fun with functional programming style, and of course, let’s do that with ruby :)

In this post we’re going to manipulate some (high order) functions, and build a derivative operator in a functional style.

### Level 1 : some basic functions

In ruby you can define a lambda operator, that is an anonymous function that reads exactly as a mathematician would define it. For instance,

defines a function that, when given an argument `x`, returns `x*x`.

We can call it and see the result :

More interestingly, higher order function can be defined, whose purpose is to manipulate other functions.

For instance, let’s define some basic operators `minus`,`mult`,`div` that can respectively add, subtract, multiply or divide functions altogether.

Note that we want `new_function = minus.(f,g)` to return a function. Rather than describing how to subtract two values, we want to define what `f -g` means when both f and g are functions.

Does that works ? With the previously defined functions:

Sweet.

• Allright, but how is that really fancy?

Well, let’s take our trip to a next step:

### Level 2 : I can haz derivative ?

Hey, I know an operator that works on functions : the derivative operator. How about we build one ?

Alright. Let’s build a derivative operator. That is, a function that takes a function as an argument, and return another function: its derivate.

The derivative of a function at some point x can be obtained by evaluating , i.e. the limit when epsilon –> 0 of a derivative scheme based on f at point x.

Here’s the plan :

• Define a limit operator
• define a derivative scheme
• define the derivative operator as the limit of the derivative scheme of a function
• Since we’re at it, define any nth derivative operator : We should be able to derivate n times any function.
• Profit and use it on any function

For the sake of clarity, let’s begin with a simplified version, and assume that `epsilon = 1e-3` is low enough to approximate the limit of our derivative scheme.

Once we’re more comfortable with the concepts, we’ll get rid of this assumption and implement a true derivative operator.

Sooo… can I derivate twice ?

Yup. Simply get the derivative of the derivative :

Sooooooo… can I derivate n times ?

Yup. Although we don’t want to create thousands of `third_derivative`,`forth_derivative`…etc, right ?

Let’s go one order higher and define the nth derivative operator

Since we can derivate a function, and we want to do it n times, what we miss is simply a `n-times combinator`. For example, `n_times.(f).(2)` should return `x -> f(f(x))` regardless of what `f` and `x` are.

Shall we do it recursively ?

Explanation :

• if n = 1 then we want f. so return f. So far so good, `n_times(1,f) = f`
• If n = 2, then we want f(f) = f( n_times.(1,f) )
• If n = 3, then we want f(f(f)) = f( n_times.(2,f) )

…etc. Get it ?

Wait… that’s all ? Where’s my nth derivative ?

Now it’s quite easy to derivate n times :

This `nth_derivator` will take `n` as an argument, and derivate n times whatever we decide to pass to it.

Let’s play with it!

That’s cool ! but those are approximations, right ? we never actually calculated the limit

Yet.

### Level 3 : More functional, and a true limit operator

Now that we have a better feel for it (have we?), let’s refactor our derivative operator so that it is actually defined as a limit. And hey, let’s parametrize the precision that we want since we’re at it.

First, let’s write a bunch of tools that are going to be useful:

Now the limit function. Here we are going to define a function, that actually implement the following (naive) algorithm:

• variables : a function `f`, a starting epsilon `eps`, and a threshold `tres`
1. Evaluate y = ||f(x + epsilon/2) – f(x + epsilon) ||
1. if y < tres, then we are converged, and lowering epsilon wouldn’t change the result much. Return f(x+epsilon).
1. else, reduce epsilon and try again (i.e. go to 1.)

Obviously, this algorithm is quite simple, and will only work when dealing with smooth, continuous, and gracious functions.