A key to purely functional languages is that their data are immutable. Therefore, assignments such as x= x+1 or ++x are not possible in the purely functional language Haskell. The consequence is that Haskell supports no loops like for, while, or until. They are based on the modification of a loop variable. Haskell does not modify existing data; Haskell creates new data when needed and reuses the old ones.
Immutable data
Immutable data has a nice property. They are implicit threadsafe because they miss a necessary condition for a data race. A data race is a state, in which at least two threads access a shared data at the same time, and at least one of the threads is a writer.
Quicksort in Haskell
The quicksort algorithm in Haskell shows very nice the immutability of data.
qsort [] = []
qsort (x:xs) = qsort [y  y < xs, y < x] ++ [x] ++ qsort [y  y < xs, y >= x]
The quicksort algorithm qsort consists of two function definitions. In the first line, the quicksort will be applied to the empty list. Of course, the result is an empty list. In the second line, there is the general case in which the list consists of at least one element: x:xs. x is the first element in the list and xs the reminder by convention.
The strategy of the quicksort algorithm can be directly applied in Haskell.
 Use the first element of the list x, the socalled pivot element and make a list with one element out of it: ... [x] ...
 Add (++) all elements before the list [x] that are smaller than x: qsort [y  y < xs, y < x]) ++ [x] ...
 Add (++) all elements after the list [x] that are equal or bigger than x: ...[x] ++ (qsort [y  y < xs, y >= x])
 The recursion will end if quicksort will be applied to the empty list.
Admittedly, the imperative eye is not used to the conciseness of Haskell.
The key point of the algorithm is that each recursion creates a new list. How does implementation in C or C++ look like?
Modernes C++ Mentoring
Stay informed about my mentoring programs. Subscribe for the news.
Thank you! Please check your email and confirm the newsletter subscription.
Your subscription was updated
Quicksort in C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[abs((left + right) / 2)];
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++; j;
}
}
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}

No worries. I will not try to explain the algorithm. A simple observation is enough for me. The elements are overwritten in line 9  11. The algorithm works in place and needs, therefore, mutable data. There exist a nice term in the functional programming for this overwriting: destructive assignment.
To be honest that was an implementation of the quicksort algorithm in C. With C++ we can do better if I use the std::partition.
template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
But once more. The key point is that I use also destructive assignment in std::partition. If you look very carefully, the strategy of the C++ version is not so different from the Haskell version.
What is the story about immutability in C++?
Immutable data in C++
The usage of immutable data in C++ is based on the discipline of the programmer. You have with constant data, template metaprogramming, and constant expressions three ways to express the immutability. Options one and two are quite easy to present but constant expressions deserve more attention.
Constant data
By using the instruction const int value= 1; value becomes immutable data.
Template metaprogramming takes place at compile time. At compile time there is no mutation. Therefore all values that are calculated at compile time are immutable. Of course, that holds true for the calculation of Factorial::5 at compile time.
template <int N>
struct Factorial{
static int const value= N * Factorial<N1>::value;
};
template <>
struct Factorial<1>{
static int const value = 1;
};
std::cout << Factorial<5>::value << std::endl;
std::cout << 120 << std::endl;
If the short notice to template programming was too short for you, please read the post Functional in C++98.
But now back into the future of C++: constant expressions.
Constant expressions
C++11 supports constant expressions. With C++14 you can declare functions as constant expressions that behave almost as usual functions.
C++ supports constant expressions in three variations: variables, userdefined types, and functions. The special about constant expressions is that they can be evaluated at compile time.
 By using constexpr double pi= 3.14 pi becomes a constant expression. pi is, therefore, implicit const and has to be initialized by a constant expression: 3.14.
 There a few restrictions for a userdefined type so that the instances of the userdefined type become constant expressions. For example, the constructor has to be empty and a constant expression. The instance can only use methods that are constant expressions. Of course, you can not invoke a virtual method at compile time. If a userdefined type fulfils all requirements, you can instantiate and use its objects at compile time.
 To execute functions in C++14 at compiletime, they have to follow a few rules. Firstly, their arguments have to be constant expressions. Secondly, they can not use static or threadlocal data.
The following example shows what power lies in constant expressions. I use userdefined literals to calculate all distances at compile time.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

// userdefinedLiteralsConstexpr.cpp
#include <iostream>
namespace Distance{
class MyDistance{
public:
constexpr MyDistance(double i):m(i){}
friend constexpr MyDistance operator+(const MyDistance& a, const MyDistance& b){
return MyDistance(a.m + b.m);
}
friend constexpr MyDistance operator(const MyDistance& a,const MyDistance& b){
return MyDistance(a.m  b.m);
}
friend constexpr MyDistance operator*(double m, const MyDistance& a){
return MyDistance(m*a.m);
}
friend constexpr MyDistance operator/(const MyDistance& a, int n){
return MyDistance(a.m/n);
}
friend std::ostream& operator<< (std::ostream &out, const MyDistance& myDist){
out << myDist.m << " m";
return out;
}
private: double m;
};
namespace Unit{
constexpr MyDistance operator "" _km(long double d){
return MyDistance(1000*d);
}
constexpr MyDistance operator "" _m(long double m){
return MyDistance(m);
}
constexpr MyDistance operator "" _dm(long double d){
return MyDistance(d/10);
}
constexpr MyDistance operator "" _cm(long double c){
return MyDistance(c/100);
}
}
}
constexpr Distance::MyDistance getAverageDistance(std::initializer_list<Distance::MyDistance> inList){
auto sum= Distance::MyDistance{0.0};
for (auto i: inList) sum = sum + i ;
return sum/inList.size();
}
using namespace Distance::Unit;
int main(){
std:: cout << std::endl;
constexpr auto work= 63.0_km;
constexpr auto workPerDay= 2 * work;
constexpr auto abbrevationToWork= 5400.0_m;
constexpr auto workout= 2 * 1600.0_m;
constexpr auto shopping= 2 * 1200.0_m;
constexpr auto distPerWeek1= 4*workPerDay3*abbrevationToWork+ workout+ shopping;
constexpr auto distPerWeek2= 4*workPerDay3*abbrevationToWork+ 2*workout;
constexpr auto distPerWeek3= 4*workout + 2*shopping;
constexpr auto distPerWeek4= 5*workout + shopping;
constexpr auto averageDistance= getAverageDistance({distPerWeek1,distPerWeek2,distPerWeek3,distPerWeek4});
std::cout << "averageDistance: " << averageDistance << std::endl; // 255900 m
std::cout << std::endl;
}

I will not repeat myself by explaining constant expressions and userdefined literals in detail. I have already done it in the posts to constexpr and userdefined literals. I want to make only two observations:
 By the declaration constexpr all variables, instances of the class MyDistance and functions become constant expressions. The compiler performs, therefore, the necessary operations at compile time.
 All variables, instances, and functions  excluding std::cout  are constant expressions. That means the entire program will be executed at compile time. Therefore, all used variables and instances are immutable. Only the output of the program 255900 m in line 77 is performed at run time.
What's next?
Pure functions are quite similar to mathematical functions. They are the reason why Haskell and template metaprogramming is called pure functional languages. But what are the restrictions that a purely functional language has to fight with? These will be my topic for the next post.
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, Louis StAmour, 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, Daniel Hufschläger, Alessandro Pezzato, Evangelos Denaxas, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob CohenArazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, and Wolfgang Fütterer.
Thanks in particular to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, Ralf Abramowitsch, John Nebel, Mipko, Alicja Kaminska, and Matthias Grün.
My special thanks to Embarcadero
My special thanks to PVSStudio
Seminars
I'm happy to give online seminars or facetoface seminars worldwide. Please call me if you have any questions.
Bookable (Online)
German
Standard Seminars (English/German)
Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.
New
Contact Me
Modernes C++,
Comments
RSS feed for comments to this post