Functional constructs: map & fold

Two standard functional constructs are provided:

• map that promotes a function acting on the array element to an array function, acting element by element.
• fold is the reduction of a function on the array.

map

• Purpose :

  map promotes any function into an array function, acting term by term.

• Synopsis

  template<class F> auto map (F f);
  

  If f is a function, or a function object

  T2 f(T1)
  

  Then map(f) is a function:

  template<ImmutableCuboidArray A> auto map(f) (A const &)
  

  with:

  • A::value_type == T1
  • The returned type of map(f) models the ImmutableCuboidArray concept
    • with the same domain as A
    • with value_type == T2

• Example:

#include <triqs/arrays.hpp>
using namespace triqs;
int main() {
  // declare and init a matrix
  clef::placeholder<0> i_;
  clef::placeholder<1> j_;
  arrays::matrix<int> A(2, 2);
  A(i_, j_) << i_ + j_;

  // the mapped function
  auto F = arrays::map([](int i) { return i * 2.5; });

  std::cout << "A = " << A << std::endl;
  std::cout << "F(A) = " << F(A) << std::endl; // oops no computation done
  std::cout << "F(A) = " << make_matrix(F(A)) << std::endl;
  std::cout << "3*F(2*A) = " << make_matrix(3 * F(2 * A)) << std::endl;
}

fold

• Purpose : fold implements the folding (or reduction) on the array.

• Syntax :

  If f is a function, or a function object of synopsis (T, R being 2 types)

  R f (R , T)
  

  then

  auto F = fold(f);
  

  is a callable object which can fold any array of value_type T.

  So, if

  • A is a type which models the ImmutableCuboidArray concept (e.g. an array , a matrix, a vector, an expression, …)
  • A::value_type is T

  then

  fold (f) ( A, R init = R() ) = f(f(f(f(init, a(0,0)), a(0,1)),a(0,2)),a(0,3), ....)
  

  Note that:

  • The order of traversal is the same as foreach.
  • The precise return type of fold is an implementation detail, depending on the precise type of f, use auto to keep it.
  • The function f will be inlined if possible, leading to efficient algorithms.
  • fold is implemented using a foreach loop, hence it is efficient.

• Example:

  Many algorithms can be written in form of map/fold.

  The function arr_fnt_sum which returns the sum of all the elements of the array is implemented as

  template <class A>
  typename A::value_type sum(A const & a) { return fold ( std::plus<>())  (a); }
  

  or the Frobenius norm of a matrix,

  \[\sum_{i=0}^{N-1} \sum_{j=0}^{N-1} | a_{ij} | ^2\]

  reads :

  #include <triqs/arrays.hpp>
  #include <triqs/arrays/functional/fold.hpp>
  using namespace triqs;
  
  // FIXME change this function for another function that is not implemented?
  
  double frobenius_norm_of_array(arrays::matrix<double> const &a) {
    auto l = [](double r, double x) {
      auto ab = std::abs(x);
      return r + ab * ab;
    };
    return std::sqrt(arrays::fold(l)(a, 0));
  }
  
  int main() {
    // declare and init a matrix
    clef::placeholder<0> i_;
    clef::placeholder<1> j_;
    arrays::matrix<double> A(2, 2);
    A(i_, j_) << i_ + j_ / 2.0;
  
    std::cout << "A = " << A << std::endl;
    std::cout << "||A|| = " << frobenius_norm_of_array(A) << std::endl;
  }
  

  Note in this example:

  • the simplicity of the code
  • the genericity: it is valid for any dimension of array.
  • internally, the library will rewrite it as a series of for loop, ordered in the TraversalOrder of the array and inline the lambda.