## Nov 09, 2012

# Lazy Evaluation in C++11

*EDIT:* Thanks to Bret for the idea with std::unique_ptr

In a recent conversation at work, I was attempting to explain some of the new features added by the C++11 Standard. While discussing, I eventually started bringing up other development concepts I'd recently discovered while learning some new languages. So I thought why not put them together. Here is some Lazy Evaluation using Lambda Functions in C++11.

## Lazy you say...

Lazy Evaluation, for those of you unfamiliar, is a strategy for processing information in a way that delays the system from doing work until it is actually needed. In many cases of software development, you may be tasked to perform a set of actions on a set of data at numerous times that induce an...extreme load on the system. If the process allows, the load is acceptable because all of the output generated is usable by the process. But sometimes you have to do a lot of work to generate results that you may have to consider "the cost of doing business."

## Some non-lazy examples

For a simple example, lets say we need an array containing `N`

number of
values in the Fibonacci Sequence. The user can ask for the
m_{th} number in the list as long as

```
0 <= m <= N
```

To make this program we either need to

- Generate the list of a
**huge**value`N`

up front - Wait for the user to input
`m`

and then make an array where`m == N`

### One big N

So lets try out the first example.

```
#include <iostream>
#include <vector>
using namespace std;
vector<int> PreCalc;
void fillPreCalc (int n)
{
PreCalc = vector<int>(n);
PreCalc[0] = 0;
PreCalc[1] = 1;
for (int i = 2; i <= n; i++)
{
PreCalc[i] = PreCalc[i-1] + PreCalc[i-2];
}
}
int main (void)
{
int m;
fillPreCalc(100);
cout << "Enter a value for m: ";
cin >> m;
cout << "The " << m << " number in the Fibonacci Sequence is "
<< PreCalc[m] << endl;
cout << "Enter another value for m: ";
cin >> m;
cout << "The " << m << " number in the Fibonacci Sequence is "
<< PreCalc[m] << endl;
return 0;
}
```

First thing we do is calculate our Fibonacci Numbers and store them into
a vector. All the work is done up front and the results can be used many
times without having to do the work again. Sounds great. The only problem
is we have to decide the size of `N`

to calculate. If calculate for
`N == 100`

but we only want to know the first three numbers, the other
97 we just calculated ate up time we could have saved if our `N`

was 3.

### Calculate in place

If we don't want to waste any time then we need to set `m == N`

.

```
#include <iostream>
using namespace std;
int InCalc (int m, int x = 0, int y = 1)
{
if (m == 0)
return x;
else
return InCalc(--m, y, x+y);
}
int main (void)
{
int m;
cout << "Enter a value for m: ";
cin >> m;
cout << "The " << m << " number in the Fibonacci Sequence is "
<< InCalc(m) << endl;
cout << "Enter another value for m: ";
cin >> m;
cout << "The " << m << " number in the Fibonacci Sequence is "
<< InCalc(m) << endl;
return 0;
}
```

Now when we call `InCalc()`

we calculate up to the m_{th} number
and no more. The only problem is if we want to find another `m`

we have
to generate another sequence of values.

## Be efficient, be lazy

If only there was a way to get the Pros of both examples without the Cons. We would have a system that:

- Stores all calculated values for future use
- Only calculates up to the largest value
`m`

input

We can start by creating a structure that allows for storing sequential data.
Each time we calculate a new Fibonacci Number we can stick it to the end of
the list. If we need a value less than `N`

we won't need to do any
redundant calculations. So the first requirement is done.

The second requirement is a little more difficult. Calculating for a case
where `m == N`

, our previous example used recursion to quickly and
efficiently get the job done. Each step through the recursion contains state
information from the previous step (i.e. the value of the previous two
Fibonacci Numbers). So we need to make our structure save the state of
our recursion to get the second requirement.

### Drum roll please!

Here we go...

```
#include <iostream>
#include <functional>
#include <memory>
using namespace std;
struct fib
{
int value;
function<fib* ()> genNext;
unique_ptr<fib> next = nullptr;
fib(int m, int n) :
value(m),
genNext([=] () -> fib* { return new fib(n, m + n); })
{}
fib() : fib(0, 1) {}
int& operator[] (int x)
{
if (x == 0)
return value;
else
{
if (next == nullptr)
next = unique_ptr<fib>(genNext());
return (*next)[--x];
}
}
};
int main (void)
{
fib f = fib();
for (int i = 0; i < 10; i++)
cout << f[i] << endl;
return 0;
}
```

Starting with our structure `fib`

we are able to store our value and a
pointer to the next structure. Using the overloaded `[]`

operator we can
step through our list of values. Requirement 1...check!

Now for the fun part. C++11 standard has replaced the horrible function
pointers of C with `std::function`

. We can store a function
call as an object, in our case `function<fib* ()> genNext;`

What
function do we store in this object? The constructor of our next
structure in the Fibonacci Sequence of course.

```
[=] () -> fib* { return new fib(n, m + n); }
```

Using a Lambda Function we are able to store our state, the previous two
Fibonacci Numbers, which is called if our next number is requested. If the
request never comes then no need to calculate. If we request a case where
`m > N`

we call the Lambda Function to generate the next number until
`m == N`

. All cases where the user requests `m < N`

we cycle through
our list and never perform a redundant calculation.

Being lazy is pretty cool.

<perm> | /coding/c++ | 2012.11.09-16:20.00 | <comments> | <reddit> | <digg> | <stumbleupon> | <tweet>