Reversing list in Haskell

I’m on the 5th problem of 99 haskell problems. The first attempt went something like this

rev :: [a] -> [a]
rev (x:xs) = rev xs ++ x
rev [] = []

Let’s analyze this one. Assume we call the function as

rev [1,2,3]

rev (x:xs) matches 1: [2,3], so we have rev [2,3] ++ 1. Similarly, we’ll have rev[3] ++ 2 ++ 1 and then finally rev [] ++ 3 ++ 2 ++ 1. The whole thing can be shown as

step 1: rev [1,2,3]
step 2: rev [2,3] ++ 1
step 3: rev [3] ++ 2 ++ 1
step 4: rev [] ++ 3 ++ 2 ++ 1

This gives

[] ++ 3 ++ 2 ++ 1

which is

[3, 2, 1]

Okay, moving forward. Next attempt at writing the function involves usage of foldl. So, here we go

rev xs = foldl (\acc x -> x : acc) [] xs

The foldl function takes the accumulator and an element from the list. The element is prepended onto the accumulator. Which goes like

rev [1,2,3]
step 1: acc = [], 1 : acc
step 2: acc = [1], 2 : acc
step 3: acc = [2,1] , 3 : acc
step 4: acc = [3,2,1]

and thus, we get [3,2,1] as result from this.

Now, notice the lambda function. The parameters on left and right are flipped, so why not use the flip function and take advantage of currying?

rev xs = foldl (flip (:)) [] xs

And finally, using point free notation, we can write

rev = foldl (flip (:)) []

Pretty nifty, eh.

Fibonacci series in haskell

So I was tired of doing (boring) stuff, and all – so I decided to take up a new challenge, the Project Euler. To sweeten the deal, I’ve decided that I’d use only Haskell to solve them.

The second question is to generate the sum of even terms of Fibonacci series. I’m going to show how the series is generated , and thus the following is – not – the solution to the problem. I’ve assumed that the highest term generated should be less than 15000, in this snippet.

takeWhile (\(x, y) -> x < 15000) (iterate (\(x, y) -> (x+y, x)) (1, 0))

Let me break it down -

1. \  syntax is used to define a lambda. So we define two lambdas in this snippet, one for incrementing the series, and other for checking

2. Iterate function is used to generate newer terms from existing terms by using a function.

3. takeWhile is used to pick out elements from a list till the condition is satisfied.

Now, the iterate function produces an infinite list, which is bounded by using takeWhile function.

Test run:

Prelude> takeWhile (\(x,y) -> x < 15000) (iterate (\(x, y) -> (x+y, x)) (1, 0))

[(1,0),(1,1),(2,1),(3,2),(5,3),(8,5),(13,8),(21,13),(34,21),(55,34),(89,55),(144,89),(233,144),(377,233),(610,377),(987,610),(1597,987),(2584,1597),(4181,2584),(6765,4181),(10946,6765)]

As you can see, a list of tuples of fibonacci’s series are generated.

That’s it for now. Hopefully I’ve written something that makes sense

PS: Interestingly, wordpress.com’s source highlighting plugin does not support haskell – so if anybody is listening, please add it soon!

Tags Manager – A nifty jquery tagging plugin

I was looking out for a good tagging plugin which could be used along with jQuery. And then I stumbled over tags manager. It’s a nifty tool, works amazingly well, and is very easy to use. As a bonus, it takes the default css from bootstrap, so styling is taken care of – if you are already using bootstrap.

Thank you, Max!

Enabling media url in development server – Django

To make the {{ media_url }} tag work in templates while using development server, you need to do some stuff, listed below.

1. Add the following to your urls.py

if settings.DEBUG:
    urlpatterns += patterns('',
        (r'^media/(?P<path>.*)$', 'django.views.static.serve', {'document_root': settings.MEDIA_ROOT, 'show_indexes':True}),
)

Don’t forget to add from django.conf import settings

2. Add to TEMPLATE_CONTEXT_PROCESSORS in settings.py the following
'django.core.context_processors.media',

3. Edit the MEDIA_ROOT and MEDIA_URL, and set them up.

4. Make sure you are using RequestContext to pass the context to the template, ie

  return render_to_response('template.html', {}, context_instance=RequestContext(request))

That’s it, you should be able to use {{ media_url }} tag in templates using development server now. Thanks to folks at stackoverflow for the information.

Using *args and **kwargs in python

So we’ve been actively working on our latest project in django – and I came across this weird syntax in views
def view_function(request, *args, **kwargs)

Digging in further, I found that *args stands for argument list, and **kwargs stands for keyword argument list ( well, only the asterik and double asterik matters, the names can be anything ). So, why is this useful again?

For example:

def foo(*args):
  for i, arg in enumerate(*args):
    print "Argument ", i, " : ", arg

and call it by

foo("a", "b", "c")

Simply put, we now have a way to call a function with arbitrary number of parameter. The function foo can be passed with any number of arguments.

So, that’s about *args. Now what is **kwargs? It is the keyword argument list – which means you can pass the keywords as well as their values as a dictionary.

For example:

class Foo(object):
  def __init__(self, value):
    print value

class DerivedFoo(Foo):
  def __init__(self, *args, **kwargs):
    print 'DerivedFoo'
    super(DerivedFoo, self).__init__(*args, **kwargs)

myFoo = DerivedFoo("Calling Foo through DerivedFoo")

The super keyword can be used to call the methods of superclass – in this case the init of class Foo. The parameters which are passed to inherited class can be passed to the base class as shown above. This can be used to extend the behavior of the base class, without knowing anything about base class.

Why smart pointers?

This is about smart pointers in C++. Of course, the first question is, what makes smart pointers “smart” and normal pointers so “dumb”?

Consider the following code

struct foo {
int* bar;
};

int main() {
foo* baz;
baz = new foo();
baz->bar = new int(5);

// do some stuff here

delete baz->bar;
delete baz;
}

That wasn’t too hard. Now consider this

foo* baz, *zap, *paz;
baz = new foo();
zap = new foo();
paz = new foo();
baz->bar = new int(5);
zap->bar = new int(6);
paz->bar = new int(7);

// Do some other stuff

// now call all the deletes
//... or let them just leak memory

...

Clearly, writing delete for each and every piece of memory allocated quickly becomes a pain. Wouldn’t it be wonderful to have a automagick thing which ‘deletes’ everything we allocated (aka a garbage collector like thing)?

Well, be happy, smart pointers can be of help here. What smart pointers does follows the concept of RAII

RAII

So what’s RAII now? Here’s a link to wiki which explains what it is, formally. It is just a technique which assures you that the destructor of the object will be called, even if an exception occurs, and generally, when the object goes out of scope.

Enough with rambling, onto example code

class ExampleClass {
Resource R;
public:
ExampleClass() { } /* Will initialize the resource R */
... do some work here
~ExampleClass() { } /* Destructor reached, R will be destroyed/ released */
};

int main() {
ExampleClass object; // resource R is initialized;
... stuff happens

return 0;
} // object goes out of scope, R will be released, since destructor of object is called.


Easy, isn’t it? The programmer does not have to explicitly manage the resource – lesser bugs and headaches.

Right. How does smart pointers fit in here? Our aim is the same as in the earlier case, let the resource (in this case, memory allocated to pointer) be released when user does not want it anymore, without user having to explicitly do it.

There are a number of smart pointers, in which we see one of them right now – the std::shared_ptr.
The shared pointer is a reference counted pointer, which increments its count every time a copy is made. Once the reference count comes down to 0, the resource gets released. [ Come to think of it, isn't it pure genius? These are things that make me feel as if I know nothing. ]

The declaration part is very easy, it goes like this
std::shared_ptr ptr;

A simple example follows

int main() {
std::shared_ptr ptr(new int(5));
std::cout << *ptr;
ptr.reset(new int(6));
std::cout << *ptr;
return 0;
}


Its mostly self explanatory, ptr is declared. Later on we replace it with another value by resetting it. [ As a fun exercise, you could try running this program through valgrind, to actually check if it is really free of memory leaks. ]

cppreference gives a good overview of all the details of shared_ptr.

SPOJ – Prime Generator

This is a neat question. The trick lies in the fact that primes are to be generated only within a particular range. I used a Eratosthenes sieve to generate primes <= sqrt(a limit), and stored it in a vector.

Now, there are three cases

1. The range is within the generated primes, ie the upper limit of range <= greatest prime already generated

2. The range is completely above the generated primes, ie the lower limit of range >= greatest prime already generated

3. Combination of 1 & 2

For case 1, simply loop through the vector and check if the number is there in the vector. For case 2, check divisibility by looping through all the generated primes.

Selecting the limit is the tricky part, depending on the range select a limit such that the execution time is minimal for a particular range provided.

As a optimization , notice that other than 2, all primes are odd, so every alternate number can be skipped if we start from 3. Similarly, multiples of 3, 5 and 7 occur in large numbers,so they can be rejected in the beginning itself [ of course, after initially marking them as prime].

Have fun!

Openbve : An amazing train simulator

Having an incredibly morbid fascination with the trains – I’ve always wanted a train simulator. Unfortunately, there were none that would work on linux. And that’s when I stumbled over OpenBve. The software is amazing – has a good game engine, and lots of maps and trains – not to mention the fact that it’s pretty realistic and detailed.

The game is written in C# and requires mono [ and some other dependencies, which they have listed here]. I’ve had a good time playing it. And I wish someone would design routes for India

Higher order functions in C++

Overview:

In C++, functions are not considered as first class citizens – meaning that they cannot be passed to other functions as it is. For example – the following is perfectly valid in a functional language like Haskell, where functions are already first class citizens.

predicate t | t > 0 = True
predicate t = False

addn x y = x+y
subn x y = x-y

The code is mostly self explanatory – there is a predicate function which returns True if value greater than 0, and False otherwise. Then there is a addn and a subn function for adding and subtracting two numbers.

 predicate (addn 5 6)
 predicate (subn 5 6)

We call the predicate function while passing a function as its parameters – the passed function gets evaluated and the corresponding value is checked by predicate which returns True or False.

Right – that was easy.

Passing functions to other functions in C++: The old way

In good old days – the best way to do this was by using function pointers. Define a function pointer, and then pass it into another function where you can execute them.

#include <iostream>

typedef int (*type1)(char);
typedef int (*type2)(int);

int bar(int x) {
  std::cout << "\nthis is " << x;
}

int bar1(char ch) {
  std::cout << "\nthis is " << ch;
  return ch;
}
int foo1(type1 x, char a) {
  x(a);
}

int foo2(type2 x, int a) {
  x(a);
}
int main() {
  
type1 x = bar1;
type2 y = bar;
  
foo1(x, 'a');
foo2(y,5);

return 0;
}

We typedef the signature of the function pointer, and then pointer is assigned a function. Then it can be freely passed around to any other function. In the above example, we typedef the signature of functions bar and bar1 as type1 and type2. They are then passed around to foo1 and foo2 functions, where they are executed.

One big disadvantage with the function pointers is that they require runtime lookup – so the runtime is increased [ unless - of course - the compiler somehow magically manages to inline it ]. And yet another problem with them is that branch prediction does not work well when there are a lot of function pointers.

So we move on.

Passing functions to other functions in C++: The new way

Actually – I lied – there isn’t a ‘new way’ – instead there are many new ways now. One of these methods is to simply create a functor and pass it over to a function.

Another method is to use boost::bind [ std::bind, if you have C++0x ]. bind can be used to bind arguments to a function – and create a function object from it. So, the above example can be rewritten using boost::bind as

#include <iostream>
#include <boost/bind.hpp>
#include <boost/function.hpp>


int bar(int x) {
  std::cout << "\nthis is " << x;
}

int bar1(char ch) {
  std::cout << "\nthis is " << ch;
  return ch;
}

int foo1(boost::function<int (char)> x, char a) {
  x(a);
}

int foo2(boost::function<int (int)> x, int a) {
  x(a);
}

int main() {

foo2(boost::bind(bar, _1) , 1);
foo1(boost::bind(bar1, _1) , 'b');
std::cout << "\n";

return 0;
}

That’s it for now.

Why Functors?

I was looking around stackoverflow when I came across the term ‘Functor’. Digging in further, and after an hour of googling – I’ve come to the conclusion that it’s a “more flexible” way of functions.

We’ll start off with a definition – taken from here

What are Functors ?

Functors are functions with a state. In C++ you can realize them as a class with one or more private members to store the state and with an overloaded operator () to execute the function.

Right – time for a small example

struct Add {
  int operator()(int a, int b) {
      return a+b;
  }
};

Simply put, the struct Add overloads the () operator, and returns the sum of two input parameters. This can be called as follows

 
Add inst;
std::cout << inst(4,5);

That was easy – but then why do all that nonsense, when we can simply define a function to add two numbers?!

The answer lies in the fact that, functors can hold state. This can be illustrated by the following example to find average of numbers using stdlib.

struct Avg {
  std::size_t num; 
  double sum;
  Avg() : num(0), sum(0) { }
  void operator()(int a) {
      sum+=(double)a;
      ++num;
  }
  double operator()() {
    return sum/(double)num;
  }
  
};

int main() {
  Avg inst;
  std::vector<int> x = {1,2,3,4,5,6,7,8,9,10,11};
  inst = std::for_each(x.begin(), x.end(), Avg());
  std::cout << inst();
  return 0;
}

Obviously, you need variable sum and num to keep track of number of variables ( if its not known earlier ). So by using a functor, we keep state – storing values of sum and num. The stdlib algorithm for_each iterates through the vector and returns the functor.

Boost provides a boost::function – which can be used to create functors from normal functions – or wrap functors around.

void display(int x) {
  std::cout << "Call function with" << x;
}

int main() {
  boost::function<void (int)> fctr = &display; 
  return 0;
}

or use boost::bind to bind to boost::function as follows

#include <boost/function.hpp>
#include <boost/bind.hpp>

void display(int x) {
  std::cout << "Call function with" << x;
}

int main() {
  boost::function<void ()> fctr = boost::bind(&display, 1);
  
  return 0;
}

From what I was able to gather.

Advantages of functors:
1. Functors can be inlined by the compiler, since the compiler can see it – unlike function pointers which carry a runtime cost(that’s the case usually – but there are exceptions).

2. It can have state, something that normal functions cannot have.

Disadvantages of functors:
1. Complex and longer to code – of course many might disagree on the ‘complex’ part – but longer for sure

2. Takes up more space – compared to a simple function.