Functional programming in C++?

[Husky]

Hello, everyone. First of all, I'm new to C++.
I've only ever been exposed to functional programming languages and the Object Oriented + Procedural approach is a bit new to me.

Right now, I'm trying to mimic what I could do in LISP (The function approach) in C++. (without using for loops that is)

Eg: to produce a summation of a list:

;;;Common Lisp
(defun fold (closure seed sequence)
  (if sequence
    (fold closure (funcall closure seed (car sequence)) (cdr sequence))
    seed))

(defun sum (sequence)
  "Produce summation of SEQUENCE.
E.g., (sum '(1 2 3 4 5)) => 15."
  (fold #'+ (car sequence) (cdr sequence))) 

But, in C++ I'm forced to use for loops introduced by ALGOL.

// return a[0] + a[1] + ... a[n-1]
int sum(int *a, int n) {
  int s = 0;
  for (int x = 0; x < n; ++x)
    s += a[x];
  return s;
}

Is there any way to mimic the functional approach I just displayed an example of? Well, I like writing one line of code instead of three lines of for loop, which takes a while to digest compared to the functional approach.

Any ideas?

[ne555]

http://www.cplusplus.com/reference/std/numeric/accumulate/
Check out numeric, algorithm and functional headers

sum(some_array, array_size); That looks like one line of code to me ;)

[Husky]

Thanks, it took me a while but I think I figured it out. I think the below code does just what I posted in LISP:
(maintaining the generic nature of the fold function.)

#include <iostream>
#include <functional>

/*
  Taking a sequence and producing a single
  value from it is called `folding'.
*/
template <typename T, typename C>
T fold (C closure, T seed, T *begin, T *end)
{
  if (begin != end) fold (closure, closure(seed, *begin), begin+1, end);
  else return seed;
}

// a[0] + a[1] + ... + a[n-1]
int sum (int *a, int n)
{
  return fold<int> (std::plus<int>(), 0, a, a+n);
}

int main()
{
  int a[] = { 1, 2, 3, 4, 5 };
  std::cout << "Summation of 1,2,3,4,5 = " << sum (a, 5) << "\n";
  std::cout << "Randomness, factorial of 5 is " << fold <int> (std::multiplies<int>(), 1, a, a+5) << "\n";
  return 0;
}

That works and spits out 15 and 120 like it should. I'm proud of myself, haha.

But, I wonder if functional approach should at all be used in C++?
Does any of you ever use functional programming with C++ in the real world? I'm curious.

[jsmith]

Yes, and fold() is not returning a value in the case where begin != end.

[Zeillinger]

jsmith wrote:

Yes, and fold() is not returning a value in the case where begin != end.

I don't think there should be a problem since it's recursive and when fold(...) is called again begin is advancing towards end. Correct me if I'm wrong...

Edit: I have now noticed he doesn't actually return the value of the function when called again. Never mind...

[Husky]

Yes, and fold() is not returning a value in the case where begin != end.

Right you are, sir. I only noticed that.

The first call to fold never returns; yet to my surprise it still works:

sun@dhcppc1:~/devf/c++$ head -14 fold.c++
#include <iostream>
#include <functional>

/*
  Taking a sequence and producing a single
  value from it one-by-one is called `folding'.
*/
template <typename T, typename C>
T fold (C closure, T seed, T *begin, T *end)
{
  if (begin != end) fold (closure, closure(seed, *begin), begin+1, end);
  else return seed;
}

sun@dhcppc1:~/devf/c++$ c++ fold.c++ && ./a.out
Summation of 1,2,3,4,5 = 15
Randomness, factorial of 5 is 120

Since the first call never returns any value, it should not return a value at all.
I think the only logical explanation is that the compiler eliminates the tail recursion.
That is understandable, since even LISP standard mandates that all tail recursions be recognized and optimized.
I'm sure this behavior is documented somewhere in the C++ standard also and is not peculiar to my compiler.

OR:

The problem is more low level. I think this must be it.
The last call to fold sets the accumulator to the value of seed.
Since we are not performing further calculations in fold() before returning the value (such as addition or subtraction)
the value of the accumulator register remains unchanged when fold() unfolds and stack is rewinded.

Let me verify the 2nd option. I'll post again in a sec (or edit this post)

[EDIT]

Hmm, I was correct as to why the correct answer was being returned. It was all because int was the return value.
The following experiment had positive results.

sun@dhcppc1:~/devf/c++$ head -18 fold.c++ | tail
[code]
T fold (C closure, T seed, T *begin, T *end)
{
  volatile int r = 0, x = 2;
  if (begin != end) {
    fold (closure, closure(seed, *begin), begin+1, end);
    r += x; // perform some calculation, r = 2 now.
  }
  else
    return seed;
}
[/code]
sun@dhcppc1:~/devf/c++$ c++ fold.c++ && ./a.out
Summation of 1,2,3,4,5 = 2
Randomness, factorial of 5 is 2

Now the return value is 2 -- the value computed in r, which is clearly not what I'm returning.

So, the reason wasn't because my compiler was eliminating tail recursion... it's because the fold function is too simple and the first call to fold wasn't returning anything.

Well, Mr. Smith was right.