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
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
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.
1 2 3
Does that works ? With the previously defined functions:
- 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.
1 2 3 4 5 6 7 8 9 10 11 12
Sooo… can I derivate twice ?
Yup. Simply get the derivative of the derivative :
1 2 3
Sooooooo… can I derivate n times ?
Yup. Although we don’t want to create thousands of
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
Shall we do it recursively ?
1 2 3
- 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 :
1 2 3
nth_derivator will take
n as an argument, and derivate n times whatever we decide to pass to it.
Let’s play with it!
1 2 3 4 5 6 7
That’s cool ! but those are approximations, right ? we never actually calculated the limit
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:
1 2 3 4 5 6 7 8 9 10 11 12
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
- Evaluate y = ||f(x + epsilon/2) – f(x + epsilon) ||
- if y < tres, then we are converged, and lowering epsilon wouldn’t change the result much. Return f(x+epsilon).
- 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Now we’re getting close ! Let’s refactor our derivative operator in a more appropriate way and get our final derivative operator:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Here’s a full code of what we implemented (download it)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
Well that’s all, hope you enjoyed reading this (at least) as much as I enjoyed writing it. Feel free to drop some comments, suggest anything, c orrect some code (or my english ) :)