# Recursion, List Manipulation, and Lazy Evaluation

Contents[Show]

The remaining three characteristics of functional programming are told quite quickly: Recursion, manipulation of lists and lazy evaluation.

## Recursion

Pure functional languages support no mutable data. Instead of a loop, they use recursion. The meta-function from Pure Functions showed it already. At compile time I use recursion instead of loops. The factorial function in C++

```template <int N>
struct Fac{
static int const value= N * Fac<N-1>::value;
};

template <>
struct Fac<0>{
static int const value = 1;
};
```

can be written quite easily in Haskell:

fac 0= 1
fac n= n * fac (n-1)

But, there is a small difference between the recursive factorial function in Haskell and C++. To be precise, the C++ version is not recursive. Each invocation of the general class template with the template argument N instantiates a new class template with the template argument N-1. The graphic shows the process.

If you use recursion in combination with lists and pattern matching, you can create powerful functions. But, that only holds partially for C++.

## Manipulation of lists

LISt Processing (LISP) is a characteristic of functional programming languages. The list is the foundation of the extremely powerful function composition in a functional language because it is the general data structure.

The processing of lists follows a simple pattern:

1. Process the first element of the list.
2. Recursively process the rest of the list, reduce in each iteration by the first element.

Because list processing is so idiomatic in functional programming, there exist special names for the first element and the rest of the list: (x,xs), (head,tail) or (car,cdr).

The pattern for processing the list is directly applicable in Haskell and C++.

Firstly, the concise version of C++. The function mySum sums up the numbers from 1 to 5.

```mySum []     = 0
mySum (x:xs) = x + mySum xs
mySum [1,2,3,4,5]  -- 15
```

And here is the C++ version.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14``` ```template struct mySum; template<> struct mySum<>{ static const int value= 0; }; template struct mySum{ static const int value= head + mySum::value; }; int sum= mySum<1,2,3,4,5>::value; // 15 ```

The Haskell version is quite easy to get. Or? But the C++ version is quite heavyweight. The C++ syntax requires that the primary or also called general template must be declared. Line 4 to line 7 is the fully specialised template (meta-metafunction) that is used for the empty argument list. If at least one template argument is used, the partially specialised class template (line 9 - 12) kicks in. Let me say a few words to the three dots, the so-called ellipse. That is the reason that the class in line 14 can take an arbitrary number of arguments. The three dots in line 1 and 9 pack the template parameter pack; the three dots in line 10 and 11 unpack the function parameter pack.

Haskell and C++ apply pattern matching to use the right function.

### Pattern matching

There is a subtle difference between Haskell and C++. Haskell matching strategy is the first match. That's the reason, you have to define the special case first. C++ matching strategy is the best to match. You can use pattern matching to define the multiplication of two numbers by successively applying addition.

For the sake of elegance, C++ first.

 ``` 1 2 3 4 5 6 7 8 9 10``` ```mult n 0 = 0 mult n 1 = n mult n m = (mult n (m - 1)) + n mult 3 2 = (mult 3 (2 - 1)) + 3 = (mult 3 1 ) + 3 = 3 + 3 = 6 ```

Lines 7 - 10 show the enrolled multiplication of the two numbers 3 and 2. Line 1 is applied if m == 0 holds. If m == 1 holds, line 2 is used. The general case is line 3.

C++ applies a similar strategy. The difference is that the C++ version is more verbose and that I have to define the general case at first.

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15``` ```template struct Mult{ static const int value= Mult::value + N; }; template struct Mult { static const int value= N; }; template struct Mult { static const int value= 0; }; std::cout << Mult<3, 2>::value << std::endl; // 6 ```

## Lazy evaluation

The story about lazy evaluation in C++ is quite short. That will change in C++20 with the ranges library from Eric Niebler. Lazy evaluation is the default in Haskell. Lazy evaluation means that an expression is only evaluated when needed. This strategy has two benefits.

1. Lazy evaluation helps you to save time and memory.
2. You can define algorithm on infinite data structures. Of course, you can only ask for a finite number of values at run time.

The following code snippet shows three impressive examples in Haskell:

 ```1 2 3 4 5 6 7 8``` ```length [2+1, 3*2, 1/0, 5-4] -- 4 successor i= i: (successor (i+1)) take 5 ( successor 1 ) -- [1,2,3,4,5] odds= takeWhile (< 1000) . filter odd . map (^2) [1..]= [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 ... Control-C odds [1..] -- [1,9,25, ... , 841,961] ```

I can calculate in the first line the length of a list including the argument 1/0.  successor in line 3 defines an infinite sequence of integers. But I only request five of them (take 5) in line 4. Therefore, all is fine. If I want to have all integers such as in line 7, I have to hit Control-C to stop the recursion.  I can use the same expression  [1..] as an argument for the function odds. Line 6 shows the power off function composition in Haskell. The dot (.) is the symbol for function composition. With a little exercise, you can read the function composition in line 6 from right to left: Apply to each argument the square function; let the odd elements pass and continue as long as the resulting numbers are smaller than 1000. You can the result of the application in the last list.

C++ uses by default eager evaluation. The means that, contrary to Haskell, expressions are evaluated from the inside to the outside. C++ has short circuit evaluation. So, C++ is a little bit lazy. If the result of a logical expression is given before the whole expression was evaluated, C++ stops to evaluate the expression. Therefore, the following code snippet is valid in C++, although 1/0 is not defined.

`if ( true or (1/0) ) std::cout << "short circuit evaluation" << std::endl;`

## What's next?

With the next post, I step into the future of C++. Fold expression in C++17 are based on variadic templates and can be used to apply the fold algorithm at compile time.

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, Marko, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, espkk, Wolfgang Gärtner, Louis St-Amour, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Neil Wang, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Tobi Heideman, Daniel Hufschläger, Red Trip, Alexander Schwarz, Tornike Porchxidze, Alessandro Pezzato, and Evangelos Denaxas.

Thanks in particular to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, and Richard Sargeant.

My special thanks to Embarcadero

## Seminars

I'm happy to give online-seminars or face-to-face seminars world-wide. Please call me if you have any questions.

### Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

### Modernes C++,

0 #1 Mary 2017-02-05 16:27
constantly i used to read smaller articles which as well clear their motive, and
that is also happening with this post which I am reading at this time.
0 #2 Paulina 2017-03-06 19:44
What's Taking place i am new to this, I stumbled upon this I have found
It absolutely helpful and it has helped me out loads.

I'm hoping to give a contribution & assist other customers like itss helped me.
Great job.
0 #3 Sonia 2017-03-07 05:51
Some eally interesting points you have written.Aided me a
lot, jut what I was llooking for :D.
0 #4 Jacqueline 2017-03-10 10:59
WOW just what I wass searching for. Came here by searching for click here
0 #5 Winnie 2017-03-12 02:41
Excellent post. I was checking constantly this blog and I
am impressed! Extremely helpvul info specifically the last part :
) I care for such info much. Iwas seeking this particujlar informattion for a long time.
Thank you and good luck.
0 #6 Chet 2017-03-21 18:39
Hi there, I enjoy reading all off your article.

I like to write a little comment to support you.
0 #7 Florentina 2017-04-09 05:11
Hi, I do think this is an excellent site. I stumbledupon it ;
) I am going to come back yet again since i hace book-marked it.
Money and freedom is the best way tto change, may
you be rich and continue to guide other people.

### Subscribe to the newsletter (+ pdf bundle)

 Name Email Please enable the javascript to submit this form

### Visitors

Today 3427

Yesterday 8041

Week 19051

Month 78680

All 6307152

Currently are 339 guests and no members online

• #### Templates - First Steps

Thanks for putting it so clear and detailed way Eagerly waiting for next post in this series

• #### And The Winner is: Templates

typo: "Template metaprogramming is turning complete. "

• #### Lazy Futures with Coroutines

I tried the example in eagerFutureWithComments.cpp and in the output, MyFuture::MyFuture immediately ...

• #### std::format in C++20

Also, C++20 doesn't support the 'print' function of {fmt}. Hopefully it will appear in C++23 (there is ...

• #### Automatically Resuming a Job with Coroutines on a Separate Thread

The thread is started automatically if the job is not done.