Skip to content

Search through a monotonic function.

July 13, 2012

I have just been doing some mental exercises, from the draft book of J. Hickey, Introduction to Objective Caml on monotonic functions. These functions maintain their trend. So f(x) is either increasing or decreasing as x moves from 0 to n. For the case when the function is increasing, we have f(i) < f(i+1) for 0 \leq i \leq n. Furthermore, for this case, f(0) < 0 and f(n) > 0. We are asked to write a search program such that given a function f and n, the program returns the smallest argument i \ni f(i) \geq 0. One’s initial impression might lead to thinking that the solution is complex but see the code below on how it turned out to be much simpler than expected. The elegance of this language is addicting.

let rec search f n =
if   (f (n – 1))  <  (f (n)) &&  f (n) > 0 then
search f (n – 1)
else
n + 1;;

Test functions:
# let f x = x + 1;;
# search f 4;;
- : int = 0
# let f x = x * 2;;
# search f 4;;
- : int = 1
# let f x = x * x;;
# search f 4;;
- : int = 1
# let f x = 3 * x + 2;;
# search f 4;;
- : int = 0

If you are not surprised how concise you can be using this language then,  my wish is for you to realise one day what I am talking about! 😉

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: