In a multithreaded environment, the lack of understanding and the resulting problems are greatly amplified, almost to the point of panic if you are paying attention. Programming in a functional style makes the state presented to your code explicit, which makes it much easier to reason about, and, in a completely pure system, makes thread race conditions impossible. - John Carmack

OO makes code understandable by encapsulating moving parts. FP makes code understandable by minimizing moving parts. - Michael Feathers

Characteristics of functional programming (from dev perspective)

First-class functions are typical for functional programming languages, that means, they behave like data. There have to be functions that can accept functions as an argument or return 'em. Therefore, they are called higher-order functions. Pure functions always return the same result when given the same arguments and can not have a side effect. They are the reason that Haskell is called a pure functional language. A pure functional language has only immutable data. That means, they can not have a while or for loop which is based on a counter. Instead of the loops, they use recursion. The key characteristic of functional programming is that you can easy compose functions. This is because of their bread and butter data structure list. If an expression evaluates its arguments immediately, it's called greedy or eager evaluation. If the expression evaluates the arguments only, if needed, it's called lazy evaluation. Lazy evaluation will reduce time and memory if the evaluated expression is not needed.The classical programming languages are greedy. They evaluate their expressions immediately.

Immutable data

functional programming means to separate the code and the data and have mostly immutable data that is transformed by a sequence of functions using techniques like passing functions to other functions for polymorphic-type behaviour, usig variants and data types like optional
the object state does not change once the object has been created
const params passed by value, not ref
const/constexpr fields and variables
const member functions
constexpr functions

First-class functions

it is like data, you can return or pass 'em around
- lambdas [](){}()
- polymorphic function wrapper - std::function<signature(args)> f
- function objects
it can be an argument of a function: std::accumulate(vec.begin(), vec.end(), 1, []{ int a, int b}{ return a * b; })

it can be returned from a function:

auto makeAdd() -> std::function<int(int, int)> {
  return [](int a, int b){ return a + b; };
}

it can be stored in a variable:

auto myAdd = makeAdd();
myAdd(2000, 11);  // 2011

those are C++14 generic lambda functions

Higher-order function

functions that take other functions as parameters or return 'em
enables IoC: pass an action/predicate to a function which deals with the control flow
- separates what happens from how it happens
- decouples control flow from desired action
many of the algorithms of the STL are so called higher order functions
- std::transform modifies the elements of its container with the help of a function, which needs exactly one argument.
- std::remove_if remove all elements from the container fulfilling the property. The condition is defined by a predicate. A predicate is a function, which returns a boolean.
- std::accumulate applies on all elements of the container a binary operation. The algorithm successively reduces the container to a final value.
- std::bind allows forward call wrapping or partial function application, aka currying
  - count_if(v.begin(), v.end(), bind(less<>(), _1, 50))
  - myDivBind1St= std::bind(divMe, _1, 2.0)
  - same with lambda - auto myDivBind1St= [](int a){ return divMe(a, 2.0); };
  - std::ref, std::cref
- for_each allows to run operation on each element
- copy_if + back_inserter

Pure functions

follows referential transparency principle - will always give the same result when given the same parameters no matter when it is called
- never mutate params
- like const member function: U DoSomething(const T& input1, int input2) const;
it doesn't look at or update global state so it can't write to the console or into a file
it doesn't maintain internal state so it cannotbuild one
it doesn't perform any IO so it can't get user input or read from files
it doesn't mutate any of the input parameters
it doesn't return random numbers or time, because the return values are different
it is thread safe coz it miss a necessary condition for a data race, aka shared data
- condition where at least two threads access a shared data at the same time, and at least one of the threads is a writer

Functor - function object?

is a function from a set of values to another set of values: int -> string
auto functor = [](const std::string& text) -> int { ... };
is a box for a value (or no value or multiple values)
list functor takes a function and applies it to every element inside the list
- like a map for lists/arrays
function functor composes or glues two functions together returning a new function
promise functor applies a function to its fulfilled input and returns a new promise that will contain the output of the function
examples:
- std::transform(vec.cbegin(), vec.cend(), std::back_inserter(transformed), some_functor);
- auto transformed = future.then([&f](aut fut){ return f(fut.get()); }); where then() has a functor
- sort(vec.cbegin(), vec.cend(), greater<>()); where greater<>() is a functor
std::vector is a function if you use foreach loop over it
std::optional is a function if you use if statement to check if it is null or not, before mapping over the contained value

Closure

reference/store the state of outside variable (i.e param) in the function and continue to hold its value even when the parent function containing the variable goes out of scope
lambda captures

Composition

type composition - power of composition applied to type system
- AND via struct/class
- OR via enum class
function composition
- piping - composition from one input to one output
  - is when you use the value of one function as input to the value of the next: fa(fb(x))
- currying/partial application
  - currying: convert function that has multiple inputs into a function with one input by returning a function
  - auto composition = [](auto callable) { return callable(...) };
- monads - composition from one input type to multiple types using bind() function
  - monad is a data type with a bind function (and some other stuff)
  - monadic function is a switch/point function that bind composes
- Kleisli composition

Currying

technique to construct functions that allows for partial application of the function’s arguments
you can either call a curried function with all its parameters, or you could call the function with limited parameters and it would return a function which accepts the rest of the parameters
std::bind allows forward call wrapping or partial function application
examples:
- count_if(v.begin(), v.end(), bind(less<>(), _1, 50))
- myDivBind1St= std::bind(divMe, _1, 2.0)
- auto myDivBind1St = [](int a){ return divMe(a, 2.0); }; myDivBind1St(10);
- auto myDivBind1St = [](int a){ return [](a){ return divMe(a, 2.0) }; }; myDivBind1St()(10);

Monoid

is a set of objects, and a method of combining them, i.e:
- numbers you can add
- lists you can concatenate
- sets you can union
every monoid has an identity, which is that "no-op" element that has no effect when you combine it with something else:
- 0 + 7 == 7 + 0 == 7
- [] ++ [1,2,3] == [1,2,3] ++ [] == [1,2,3]
- {} union {apple} == {apple} union {} == {apple}

Monad

A monad is like a burito...

encapsulates a simple type in an enriched type and supports the compositions of functions on these enriched types
is a functor that uses composition
- like a bind for functors
represend a sequence of steps of computation
do-notation = monadic bind
auto monad = [](const string& text) -> std::pair<int, string> { ... };
maybe monad from Haskell is almost like std::optional but better
classical monads encapsulate one side effect:
- I/O monad for calculations that deal with input and output
- maybe monad for calculations that maybe return a result
- error monad for calculations that can fail
- list monad for calculations that can have an arbitrary number of results.
- state monad for calculations that build a state
- reader monad for calculations that read from the environment
a monad consists of three components:
- type constructor that defines how the simple data type becomes a monadic data type
- functions:
  - identity function that introduces the simple value into the monad
  - bind operator that defines how a function is applied to a monadic value to get a new monadic value
- rules for the functions:
  - the identity function has to be the left and the right identity element
  - the composition of functions has to be associative
  - the composition respects the special structure of a monad, i.e the error monad will interrupt its calculation, if an error occur or the state monad builds its state
examples: tl::optional<T>, std::optional<T> (no pattern matching yet, comes with c++20), std::future<T> (C++20 has binding like .then(...), when_any(), when_all()), std::variant<T> (with pattern matching for types)

(Tail) Recursion

instead of a loop we need recursion to achieve data immutability
it can incur performance losses, since the results of every recursion are stored on a stack
- compilers optimized for tail recursion, it performs on par with looping
there has to be only a single recursive call and it has to be the last statement in the function
- no operation can be applied to the function's return value before it's tail-returned: return n*fact(n-1); // wrong

Lazy evaluation

expressions are only evaluated when needed
expressions are evaluated if only and when necessary and not at the time of declaration

C++20 ranges lib achieve this together with function composition:

auto odds= view::transform( [](int i){ return i*i;} ) |
           view::remove_if( [](int i){ return i % 2 == 0; } ) |
           view::take_while( [](int i){ return i < 1000;} );
auto oddNumbers= view::ints(1) | odds;
ranges::for_each(oddNumbers, [](int i){ std::cout << i << " "; });

auto total = ranges::accumulate(view::ints(100, 1000) |
                               view::transform([](int x){ return x*x; }) |
                               view::take(100), 0);

generic lazy evaluation

Techniques

C++ doesn't encourage functional programming, but it doesn't prevent you from doing it

make method signature honest, avoid primitive obsession and do not behave unexpectedly for any values from the input range
```
static int Divide(int x, NonZeroInteger y)
{
    return x / y.Value;
}
```
std::exception and std::nullptr_t makes your code dishonest, avoid 'em
FP promotes type-erasure (via passing lambdas), which leads to no need for inheritance, hence less coupling
use FTL

dispatch tables - tables of pointers to functions

std::map< const char , std::function<double(double,double)> > dispTable{
  {'+',[](double a, double b){ return a + b;} },
  {'-',[](double a, double b){ return a - b;} },
  {'*',[](double a, double b){ return a * b;} },
  {'/',[](double a, double b){ return a / b;} } };
std::cout << "3.5+4.5= " << dispTable['+'](3.5,4.5) << std::endl;

enforce single assignment

const T F(int input) const;
const auto retVal = F(5);

error handling without exceptions: using Error = std::string; + template<typename T> using Result = std::variant<T, Error> + std::visit()
```
std::optional<U> F(const T& input);
if (auto output = F(input)) {
```

multiple return types

std::tuple<U1, U2> F(const T& input);

Output1 output1;
Output2 output2;
std::tie(output1, output2) = F(inputs); // or...

auto [output3, output4] = F(input); // using Structured Bindings

calling callable objects with args via invoke()

template <typename Range, typename Callable>
void transform_print(const Range& r, Callable c) {
  for (const auto& e : r) cout << invoke(c, e) << endl;
}
transform_print( v, [](const auto &p) { return p.first * p.first; });
transform_print( v, &pair<int, int>::second);

using variadic templates and C++17 fold expressions
using C++20 concepts as interfaces for similar types is like using type classes in Haskell
- type classes in generic programming play a similar role as interfaces in object-oriented programming
```
template<typename Cont>
  requires Sortable<Cont>()
void sort(Cont& container){...}
```
C++20 ranges library allows LINQ like declarations
C++20 coroutines are a generalisation of functions - they can be suspended and resumed
result_of_t<T> like vector<decay_t<result_of_t<Callable&(const T&)>>> ret; but use decltype(T) or decltype(auto) instead

lambdas for rng:

auto d20 = [urng = mt19937(1729), dist = unifirm_int_distribution<int>(1, 20)]() mutable { return dist(urng); };
generate(v.begin(), v.end(), d20); // each suc call will reset counter since lambda as value gets discarded
generate(v.begin(), v.end(), ref(d20)); // passing by ref will continue sequential generation

composition and channeling:

template<typename T> using sink = std::function<void(const T&)>;
template<typename T> using source = std::function<void(sink<T>)>;
template<typename T> void connect( source<T> so, sink<T> si) { so(si); }

source<char> consoleInput = [](sink<char> s) { int inCh; while((inCh == std::cin.get()) != EOF) s(inCh); };
sink<char> consoleOutput = [](char c){ std::cout.out(c); };

connect(consoleInput, consoleOuput);

REST-based web api:

auto version = to_path("v1);
auto foos = version / "foos";
auto api = router(
  GET(foos, list_all_foos),
  GET(foos/param<int>(), get_foo_by_id),
  POST(foos/body<foo>(), insert_new_foo),
  GET(version/"bars", list_all_bars)
);

Response post_new_foo(const Request& rq, const foo& foo) {
  all_foos.push_back(foo);
  return {foo, Created};
}

Declarative style is about avoiding statements

expression statements
selection statements: if, switch
iteration statements: for, while, do
jump statements: break, continue, return, goto
declaration statements

Refactoring to higher-order function

benefit: avoid repetition, ioc flow
pass an action/predicate to a function which deals with control flow
separate what happens from how it happens

decouple contro flow from the desired action

template<typename T> 
void print(const std::vector<T>& v) {
  if(std::empty(v)){ return; }
  std::cout << *v.begin();
  for(auto it = std::next(v.begin()); i != v.end(); ++ it){ 
    std::cout<< ", "; 
    std::cout<< *it; 
  }
}

identify the structure

template<typename T> 
void print(const std::vector<T>& v) {
  if(std::empty(v)){ return; }
  /* action type 1 */
  for(auto it = std::next(v.begin()); i != v.end(); ++ it){ 
    /* action type 2 */
    /* action type 1 */
  }
}

create an abstraction

template<typename Range, typename F, typename Sep> 
void for_separated(Range&& r, F&& act, F&& sep) { /* is reusable and provides control flow */
  if(std::empty(r)){ return; }
  act(*r.begin());
  for(auto it = std::next(r.begin()); i != r.end(); ++ it){ 
    sep();
    act(*it);
  }
}

redefine print, define another function wide_print

template<typename T> 
void print(const std::vector<T>& v) { /* here we provide the action */
  for_separated(v, [](const auto& x){ std::cout << x; }, []{ std::cout << ", "; } );
}
const auto wide_print = [](const auto& sentence) { /* here we provide another action */
  for_separated(v, [](const auto& x){ std::cout << x; }, []{ std::cout << ` `; } );
}
wide_print("bazinga!"s); // > "b a z i n g a !"

wi7a1ian/functional-cpp-notes.md