Review of Manning's Functional Programming in C++

Last year I reviewed the pre-print manuscript of Manning's Functional Programming in C++ written by Ivan Čukić.

I really enjoyed reading the book. I enthusiastically support that the book

Offers precise, easy-to-understand, and engaging explanations of functional concepts.

Who is this book for

This book expects a reasonable working knowledge of C++, its modern syntax, and semantics from the readers. Therefore, reading this book might require a companion book for C++ beginners. I think that’s fair because FP is an advanced topic. C++ is getting more and more powerful day by day. While there are many FP topics that could be discussed in such a book, I like the practicality of the topics selected in this book.

Here's the table of contents at a glance.

This is a solid coverage of functional programming concepts to get a determined programmer going from zero-to-sixty in a matter of weeks. Others have shared their thoughts on this book as well. See Rangarajan Krishnamoorthy's commentary on this book.

I found 4 chapters in the book really instructive.

Getting Started With Functional Programming (Chapter 2): This is my favorite because this is where your mind start to bend and you feel it! The esoteric idea of passing and returning functions starts to make sense and its power becomes apparent. One also realizes that C++ was never far from that idea anyway. Function Objects, my friends! A specific thing I learned from this chapter was the "generality of fold": First comes recursion; then comes the stack size limitation of recursion; then comes tail-call optimization; then comes incremental updates to the state (mutable or immutable); and finally comes fold. It goes deeper than that though.
Lazy Evaluation (Chapter 6): This is where you find expression templates and generalized memoization. I liked the discussion of computing Fibonacci with a fixed-size (forgetful) cache. I wrote a blogpost on memoization a long time back.
Ranges (chapter 7): The Ranges library is perhaps the largest and the most visible aspect of functional programming in C++. The book describes uses of the ranges library through a number of examples of filter, transform, and even infinite ranges. Ranges are now in C++20.
Monads (Chapter 10): This topic is fascinating. I've bought FP books to read the chapter on monads primarily. This book makes it this difficult topic approachable by dissecting std::optional and chainable futures---libraries that C++ programmers are probably familiar with already.

Having said that there are a number of places I would have done/written something differently. In short, this blogpost is a soft critic of the book. Everything below has been provided as feedback to the editor.

General Thoughts

If there was room for more content in the book, I would have loved to see the following.

A dedicated section on C++ fold expressions. My personal opinion is that this book isn't complete without discussing C++ fold expressions in a dedicated section. fold expression are used in this book. The index at the end does not mention it. I can't imagine this is a pre-requisite!
Discussion of the ideas of entering a monad and existing a monad. The notion that, once a pipeline has begun, the logic is weaved around the same monad as much as possible and only at the end one breaks out of the monad because side-effects must be materialized or one needs a full collection to pass to a non-monadic library. In my experience, I’ve seen rookie engineers to use the monadic api just for one or two steps (like map/filter). I’ve sensed a block against going after much longer monadic chains. The examples in the book are great. But in practice people may stay away from long chains due to very high logical density.
Algebraic API Design. map/filter/reduce/groupBy/flatmap return the same type—the algebraic type—in many cases a monad. It’s not a coincidence. It’s a fundamental aspect of the functional design. It’s a tell-tale sign of a functional api. It’s an algebra and operations on algebra return objects from the same algebra. It is elegantly represented using (1) the fluent api style (2) operator overloading (a sophisticated version of 1). As functional libraries in C++ tend to use operator overloading, one might miss the easier starting point which is the fluent api. I’ve found algebraic api design for random number generators quite instructive.
Notion of monad as higher-ranked typeclass. C++ can model the monad typeclass using template template parameter. I’ve not found any practical uses of such a template but I think it would be fun to discuss. I've discussed it in folding monadic functions.
```
template<template <typename> class M>
struct monad 
{ 
   template <class T, class Func>
   static auto bind(M<T>& m, Func&& func) -> decltype(func(m));
};
```
Algebraic list/tree data structures. Conceptually using cons/cdr lisp primitives and/or with std::variant and std::recursive_wrapper.
Well-known names of accumulate, transform, and mbind, which are reduce, map and flatmap. The entire book does not mention flatmap anywhere! I think minimally, names used in other common libraries/languages would be quite instructive.
Currying functions of arbitrary is not discussed. Interested readers can checkout previous blogpost on currying arbitrary functions (see later half).
The difference between returning a function pointer and returning a function object or a stateful lambda. For many good C programmers returning a function pointer would be familiar but it’s still not functional programming. Bringing the distinction out would clarify a lot of things.
This book explains argument-dependent lookup (static polymorphism) without an example. It’s much easier to understand if there’s an example code to look at. I would suggest to introduce argument-dependent lookup much earlier in the book with an example.

Section-wise

In section 2.4.4, it may be worthwhile to discuss the guarantees std::accumulate makes regarding making copies of the intermediate result in to the user-supplied function. For ints it won’t matter but for std::vector it would. I checked that std::accumulate (before C++20) requires that init value type be copy-assignable and copy-constructible. It looks like pre-C++20 std::accumulate can be used to avoid copies either by returning a reference or by using std::ref and std::reference_wrapper. Full example code on Wandbox.

using Vector = std::vector<int>;
void nocopy_accumulate(Vector &v) {
    Vector init;
    Vector v2 = std::accumulate(v.begin(), v.end(), std::ref(init), 
                    [](std::reference_wrapper<Vector> v, int i) {
                      v.get().push_back(i);
                      return v;
                    });
    std::cout << "size of v2 = " << v2.size() << "\n";
}

Chapter 3: Lambdas and function objects are introduced here. The chapter does not discuss what we can not do with lambdas. I.e., We can pass them around, make copies, but we can't assign them. This causes pain in writing ListMonad::flatMap in C++, which may have to cache and update the nested function (lambda) returned by the inner function. That's not a problem with function objects. C++20 likely not have this restriction on lambdas anymore.

Section 4.1.2 A Rudimentary bind implementation. I always thought std::bind is too much magic. It will be quite rewarding to the reader to understand some C++ mechanics that can implement a simple bind function. In this case, I referring to static polymorphism (bind_helper below). It's worth learning to see how lambdas make std::bind nearly irrelevant. So here's an example of implementing a rudimentary std::bind. This implementation calls the function right-away when both arguments are provided. Unlike std::bind. These semantics are closer to functional languages. A true variadic bind could be an exercise for the reader. Live code on Wandbox.

#include <iostream>
#include <utility>

struct Arg1 {} _1;
struct Arg2 {} _2;

template <class Func, class A1, class A2>
auto bind_helper(Func f, A1 a1, A2 a2) {
  return f(a1,a2);
}

template <class Func>
auto bind_helper(Func f, Arg2, Arg1) {
  return [f](auto first_arg, auto second_arg) {
    return f(second_arg, first_arg);
  };
}

template <class Func>
auto bind_helper(Func f, Arg1, Arg2) {
  return [f](auto first_arg, auto second_arg) {
    return f(first_arg, second_arg);
  };
}

template <class Func, class A2>
auto bind_helper(Func f, Arg1, A2 a2) {
 return [f, a2](auto first_arg) {
    return f(first_arg, a2);
  };
}

template <class Func, class A1>
auto bind_helper(Func f, A1 a1, Arg1) {
  return [f,a1](auto second_arg) {
    return f(a1, second_arg);
  };
}

template <class Func, class A1, class A2>
auto bind(Func&& f, A1&& a1, A2&&a2) {
  return bind_helper(std::forward<Func>(f), std::forward<A1>(a1), std::forward<A2>(a2));
}

int main()
{
  std::cout << std::boolalpha << bind(std::greater<int>(), _1, 42)(43) << "\n"; // true
  std::cout << std::boolalpha << bind(std::greater<int>(), 42, _1)(43) << "\n"; // false 
  std::cout << std::boolalpha << bind(std::greater<int>(), _1, _2)(43, 42) << "\n"; // true
  std::cout << std::boolalpha << bind(std::greater<int>(), _2, _1)(43, 42) << "\n"; // false
}

Section 7.3. Mixing left and right associative operators. The code like "words |= action::sort | action::unique" is too much magic. I think it’s worth talking the operator associativity magic going on here. |= is right-to-left associative and | is left-to-right associative. Because of that what’s really happening here is more like words |= (action::sort | action::unique);.
Section 10.6 Handling State with Monads: Looking at the title and the text underneath one would think that State monad is discussed. For instance, the following two lines
1. "The simplest way is to pass each function the current state along with its regular arguments: the function should return the new state."
2. "This log is the state you want to change"
Changing state (not just appending) is hallmark of the State monad. However, the monad discussed in this section is the Writer monad. I did some reading on stackoverflow. I think this section should not confuse with state monad as the computation is NOT dependent on existence of a state. Usage of empty std::string in the constructor of with_log confirms that a monoid is used (as necessary in the Writer monad). There's a note at the bottom of the page though, which calls out Writer monad.
Listing 11.7, Using fold expressions without a prior introduction. Chapter 2 discussed folds but never the fold expressions.
Section 12.6 and listing 12.11: What kind of monad is with_client? Is there a well-known counter-part in other languages/libraries. It looks like a product type to me and that’s it. It’s generic on MessageType but that alone does not make it a monad. The closest I can think of is the Writer monad because it's a tuple. A transform can be defined on it so it’s may be a Functor. But how about mbind? Any given with_client<with_client<std::string>> has two tcp::sockets in them. Which one would survive when mbind flattens them?
Independent of whether it’s a monad or not, I don’t agree with the suggestion here that one should try to find a monad in every generic type. That seems to be the tone of the paragraph. When you have a hammer, everything starts looking like a nail. IMO, construction and usage of a monad should be given a very deep thought. Once an application is coded in a monad, in reality, it’s going be very hard to change to a different monad or a different stack of monads.
Section 13.1 mentions "some people say that once you successfully compile a functional program, it is bound to work correctly". I think this was said in the context of Haskell only and not other less pure functional languages. It may be much more true in case of Idris etc languages.
Section 13.4 Testing monad-based Systems: There are two claims/suggestions made in this section.
1. Page 283, "freely switch between different monads"
2. Page 285, "just change the definitions of transform and filter"
I’m not a fan of the above two arguments. In my experience, changing monads is significantly hard.
- The examples in the book suggest changing (reimplementing) transform and filter for collections while moving away from production reactive streams to testing the same pipeline. In practice, one would use something like RxCPP or something equally sophisticated to implement reactive streams. It might be std::future with .then chaining. As these are specialized monads, there are api functions that would make sense only in them. For example, Consider operators in Rx combine_latest, debounce, subscribe_on, produce_on, delay, timeout. They don’t appear to have an obvious replacement in other monads. How would one go about testing a pipeline that has used these operators?
- I’ll try to answer my own question here. I think it might work out in case of reactive streams and collections because they are duals of each other. That’s a theoretical argument. In practice, one would drive the reactive stream directly by using Subjects from Rx. From the book it would be a replacement of boost::asio::server with a predefined array of input data. However, in general, it is probably harder than it looks.
- Rewriting large swatch of operators for two or more monads would be a big deterrent to the adoption of this paradigm.

Nit Picks

Collections vs. Containers: I think collection is a Java concept. In C++ we’ve containers. So container<T> might be a better choice here.

C++ Truths

Search This Blog