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.

Standard

Functional programming using C++ – The haskell style

I had recently read an article which explained how functional programming style can be adopted by using template metaprogramming. The ” hello world ” equivalent for TMP is the factorial computation – which can be described as follows

fc 0 = 0
fc 1 = 1
fc parm = parm * fc (parm-1)

and the c++ equivalent can be expressed as

#include <iostream>

template <int parm>
struct fact {
  static const int val = parm * fact< parm - 1 >::val;
};

template <>
struct fact<1> {
  static const int val = 1;
};

template <>
struct fact<0> {
  static const int val = 0;
};

int main() {
  std::cout << fact<5>::val;
  return 0;
}

Right. So this was already available everywhere. Thus I decided to write a similar kind of program in haskell and then implement it using TMP in C++. The problem I took up was very simple – to find the sum of numbers in a list.

In haskell, this program is trivial –


sumList (x:xs) = x + sumList xs
sumList _ = 0

That was easy. Now looking forward to TMP – we use variadic templates to perform the same thing


#include <iostream>

template<int... Values> struct List;

template<int x1, int x2, int... Values> 
struct List< x1, x2, Values... > {
  static int const value = x1 + x2 + List< Values... >::value;
};

template<int x1>
struct List< x1 > {
  static int const value = x1;
};

template<>
struct List<> {
  static int const value = 0;
}; 

int main() {
  
  std::cout << List<1,2,3,4,5>::value;
  return 0;
  
}

That’s it for now. I’ll try and solve something else using haskell and then try and translate it in terms of TMP. Till then.

Standard

Becoming a haskeller

Well, well – I had decided that I need to know atleast one functional programming paradigm based language. And I selected haskell. It sounds pretty cool, and has a wacky syntax [ well.. I guess that comes from a closeted C programmer].

Haskell needs some getting used to – especially if you don’t have any experience with functional programming style [ I didn’t have any – for one ]. The good news is that Haskell has a lot of good resources out there – I’m currently following the Real World Haskell . It has not been exactly ‘a smooth sailing’ – but I’ve been able to pick up bits and pieces and move along.

I’ll keep updating stuff up here as I learn new stuff. Adios, till then.

Standard

Generating random numbers – C++

Okay, so I was given a task of codifying the genetic algorithm. As genetic algorithm depends a lot on the random numbers, I started searching the internetz for a good method for generating random numbers. Of course, the first hit was the rand() function – the good ole’ tried and tested method. So we have something like this

 #define RANGE 10000

 ...

 srand(time(0));
 int var = rand() % RANGE;

Obviously, using the ‘%’ with the rand() has its own problems, and often more than not, gives a not-so-random distribution. This led me to further searching and I stumbled across Boost.Random .

#include <boost/random/uniform_int.hpp>
#include <boost/random/uniform_real.hpp>
#include <boost/random/mersenne_twister.hpp>
int main() {
  boost::mt19937 gen;
  boost::uniform_int<> int_dist(1,10);  // generate integers from [1,9)
  std::cout << int_dist(gen);

  boost::uniform_real<> real_dist(1.0,10.0);
  std::cout << real_dist(gen);
  return 0;
}

The mt19937 is based on Mersenne Twister – a random number generator. It can be used along with many a distribution, like Bernoulli’s, Binomial, Uniform – to name a few. The above example makes use of the uniform integer distribution, and uniform real number distribution to generate an integer and a real number respectively.

With c++0x, these are already a part of the standard library, so if you are using a newer compiler – then you’re in luck.

#include <iostream>
#include <random>
int main() {
  std::mt19937 gen;
  std::uniform_int_distribution int_dist(0, 19);
  std::cout << int_dist(gen);

  std::uniform_real_distribution real_dist(1.0,10.0);
  std::cout << real_dist(gen);
  return 0;
}

This compiles happily with g++ 4.6.1 with -std=c++0x option.

So well, I was quite happy the way random numbers were generated, and needless to say, the algorithm works pretty good 🙂

Standard