BEJOCAMA - Category Theory and C++

A programming language consists on a bunch of elements - variables, functions, objects, structures - which behave like it is defined by this language. But there is perhaps a motivation to work with self defined elements, which behaves in a certain way. We can talk about constructing a domain specific language or constructing a theory or an idea, which needs to be proved or which should be shown to be reasonable.

It's difficult to argue, that there is a need of a new language, because there are not so much people, who solved the same complex programming problem in two different languages and finally came to the result, that the first one was more suitable than the second one.

Most programmers are interested in structural problems - but most programmers must also produce solutions for existing problems. So an interesting task could be, to move step by step to more powerful working - directly usable - concepts.

So I want to use existing features of a programming lanuguage and give them an appropriate meaning. In constrast to object oriented programming, where the Liskov principle is most important - a circle is a shape - I want to give things an interpretation, which may vary from context to context. So a circle can be interpreted as a shape, but other interpretations are also possible.

Such considerations lead to a very different programming style and new constructions to work with.

Sure, this approach is motivated by category theory. There, some authors are fascinated about functions. But is this fascination justified? Let's see if it slops over. Because programming is totally constructive, all ideas should here be representable by constructions - by code examples. Perhaps new for most interested readers is the interpretation aspect in contrast to an object oriented point of view.

For this I'm using C++ to express some ideas. The result is not a C++ programm - even if it seems to be - in a tradtional sense. The most important feature of C++ I'm using is the template system, which allows generic programming. This is the connection to category theory, which has a generic nature.

Let's start to find out, if a new language can avoid loops. Because loops are connected to container data, a loop is a way to deal with container data.

Why loops are a problem? Loops are a problem because of the body, which may contain portential programming errors. But if we consequently replace the loop body by a separated body function (perhaps a lambda), the problem is still in that function and the code may become perhaps worse to read

std::list<int> test_function(std::list<int> l)
{
  std::list<int> rl;

  for(auto& e: l) {
    rl.emplace_back(e*e);
  }
}

can be transformed to

std::list<double> test_function(std::list<int> l)
{
  std::list<double> rl;

  auto one_third = [&rl] (int e) {
    rl.emplace_back(e*0.33333);
  };

  for(auto& e: l) {
    one_third(e);
  }

  return rl;
}

In the C++ standard we will find functional structures for avoiding explicitely looping

std::list<double> test_function(std::list<int> l)
{
  std::list<double> rl;

  auto one_third = [&rl] (int e) {
    rl.emplace_back(e*0.33333);
  };

  std::for_each(l.cbegin(), l.cend(), one_third); 

  return rl;
}

After a look at the code, can I deliver an argument, why we should do this? My answer is - at the moment it makes no sense. Because I want to create a new language and we need some words of this language to construct something we can compare with the old language. This is an journey of construction experiments. So proclaiming a problem avoiding loops is at first a pseudo motivation and finally an introduction drug.

Let's now go a different direction and let's look on the functor concept

namespace cat
{
  template<typename T>
  struct functor;

  template<typename T>
  struct functor<std::list<T>>
  {
    template<typename F, typename A>
    decltype(auto) operator()(F&& f, const std::list<A>& l)
    {
      using type = decltype(fwd(f)(std::declval<A>()));

      std::list<type> rl;

      auto x = [&rl,ff=fwd(f)](const auto& e) {
        rl.emplace_back(ff(e));
      };

      std::for_each(l.cbegin(), l.cend(), x);

      return rl;
    }
  };
}

The template functor is said here to be an interpretation and especially in this case an interpretation of a list. The macro fwd helps to shorten forwardings in the area of universal references. For the moment lets state

An interpretaton is a mapping of a type to another interpretation type.

Next take a look on the code

std::list<double> test_list_functor(std::list<int> l)
{
  auto one_third = [] (int e) {
    return e*0.33333;
  };

  return cat::functor<decltype(l)>()(one_third,l);
}

The functor selector decltype(l) is not a perfect selector, because l stands for a value category - const or reference or both together. Later I define an additional helper clear_type to extract the type from the value category.

It's perhaps clear, that such container iterations can be generalized, so that the looping mechanism we only need to implement at one place.

But this is not enough. Important seems to me, to express the relation to an arithmetic calculation by an operator. First take a look on the wish

std::list<double> test_list_functor(std::list<int> l)
{
  auto one_third = [] (int e) {
    return e*0.33333;
  };

  return one_third <<fa>> l;
}

In functional languages we can find a \(\lt{}$\gt{}\) operator. In C++ our possiblities to define operators are limited. I'm trying to circumvent this by using an approach found on different sites in the web, looking for "custom operators in C++". But what would the \(\ll{}a\gg{}\) operator express - in contrast to \(\ll{}fa\gg{}\) - simply

std::list<double> test_function(int i)
{
  auto one_third = [] (int e) {
    return e*0.33333;
  };

  return one_third <<a>> i;
}

So

\(one\_third \ll{}a\gg{} i\)

is simply

\(one\_third(i)\).

Using an operator instead of a parenthesis is a very important method to express the application of a function to a value in functional languages. So let's apply the function one_third two times, using the application operator

std::list<double> test_function(int i)
{
  auto one_third = [] (int e) {
    return e*0.33333;
  };

  return one_third <<a>> one_third <<a>> i;
}

This looks much more elegent and readable than

std::list<double> test_function(int i)
{
  auto one_third = [] (int e) {
    return e*0.33333;
  };

  return one_third(one_third(i));
}

I think functional programmers wouldn't like so much these languages without having these operators.

We can see, that the operator \(\ll{}fa\gg{}\) is an extension of an ordinary function application, where the function is applied to a functorial value. And functorial means, that for a given value type exists a functor interpretation.

If we would generate a new function via the functor operator instead of directly applying the function to the value, we would get the following situation

std::list<double> test_list_functor(std::list<int> l)
{
  auto one_third = [] (int e) {
    return e*0.33333;
  };

  return cat::functor<decltype(l)>()(one_third) <<a>> l;
}

We can directly apply the value to the new generated function. This approach of the functor implementation looks like

namespace cat
{
  template<typename T>
  struct functor<std::list<T>>
  {
    template<typename F>
    constexpr decltype(auto) operator()(F&& f) const
    {
      return [ff=fwd(f)] (auto&& l) {
        using type = decltype(ff(std::declval<decltype(*l.begin())>()));

        std::list<type> rl;

        for(auto& e: l) { rl.emplace_back(ff <<a>> e); }

        return rl;
      };
    }
  };
}

Function generation code can always declared as constexpr. Perhaps it is surprising - because of the auto in the lambda declaration - it is possible to do the following

std::list<double> test_function(std::list<int> l)
{
  auto one_third = [] (int e) {
    return e*0.33333;
  };

  auto list_one_third = cat::functor<std::list<int>>()(one_third);

  return list_one_third <<a>> l;
}

The lambda is a shortcut to an object with one call operator, list_one_third represents the object, not directly the operator method. The template resolution is done only at application time. Instead of using a lambda, we can make it more explicit, using a fun object

namespace cat
{
  template<typename...>
  struct fun;

  template<typename T, typename F>
  struct fun<std::list<T>,F>
  {
    template<typename A>
    decltype(auto) operator()(A&& a)
    {
      using type = decltype(f(std::declval<decltype(*a.begin())>()));

      std::list<type> rl;

      for(auto& e: fwd(a)) { rl.emplace_back(f <<a>> e); }

      return rl;
    }

    const F f; 
  };

  template<typename T>
  struct functor<std::list<T>>
  {
    template<typename F>
    constexpr decltype(auto) operator()(F&& f) const
    {
      return fun<std::list<T>,F>{fwd(f)};
    }
  };
}

The lambda replacement captures the function object in a member variable. The fun interpretation or longer function is another interpretation, which is more fundamental then the functor interpretation. The next section will take a closer look on functions.

Like a functor interprets a type - a function introduced in this section will also interpret types.

namespace cat
{
  template<typename...>
  struct fun;
}

To specify a function we must introduce a name as a type

namespace cat::name
{
  struct sum;
}

Now we can give the term sum an interpretation

namespace cat
{
  template<>
  struct fun<name::sum>
  {
    template<typename A>
    A operator()(A&& x, A&& y)
    {
      return fwd(x) + fwd(y);
    }
  };
}

In this context name introduction is perhaps the better term than type forwarding. As a name a type is fully specified.

This interpretation of a function is closely related to a lambda, which isn't different from such a function with one call operator. Our function definition is more flexible, because we can build polymorphic functions

namespace cat
{
  template<>
  struct fun<name::perimeter>
  {
    double operator()(const circle& c)
    {
      return 2 * pi * c.r;
    }

    double operator()(const rectangle& r)
    {
      return 2 * (r.a + r.b);
    }
  };
}

We need these functions to introduce the next language element - the polimorphic data type. This is done in one of the following sections.

Let's use the fun concept to introduce a lambda using a deduction guide

namespace cat
{
  namespace name
  {
    struct lambda {};
  }

  template<typename F>
  struct fun<name::lambda,F>
  {
    fun(F&& f, name::lambda) : m_f(fwd(f)) {}

    F m_f;
  };

  template<typename F> fun(F&&) -> fun<name::lambda,F>;
}

Now we can write

auto f = fun{[](){}};

If it is really a good idea, we will see later. For the moment I want to provide a helper operator - the plus sign, to make the lambda transformation easier

namespace cat
{
  template<typename F>
  decltype(auto) operator+(F&& f)
  {
    return fun(fwd(f));
  }
}

Another thing we can do with a function, we can look on a functor as a special function

namespace cat
{
  namespace name
  {
    struct functor;
  }

  template<typename... T>
  struct fun<name::functor,T...>;

  template<typename... T>
  using functor = fun<name::functor,T...>;
}

At this point we can also make the code more general, if we look on a function as special object

namespace cat
{
  namespace name
  {
    struct function;
  }

  template<typename... T>
  struct cat_object;

  template<typename... T>
  using fun = cat_object<name::function,T...>;
}

In principle such an approach is possible, but at this stage it would be perhaps over structured. So we can take it if we need it.

To make generic programming more powerful universal references and perfect forwarding were invented. This mechanism allows us to provided one implementation of a function for several purposes - in the context of value categories. Very important to make universal references working is to use the general form

template<typename T>
MyReturnType MyFunction(T&& t)
{
  ...
}

Sometimes this general form is too general in certain situations. With C++20 we can now call on concepts to specify additional constraints. Before C++20 it was not so handy by using sfinae - espacially if variadic templates are used.

So I'm using C++20 concepts and perfect forwarding very systematically. And this is very important, because the problems, which may occur in providing fundamental solutions of functional programming with generic C++ code, are sometimes very difficult to understand and to solve.

Beside the problem of forwarding simple data, forwarding of container data - like the elements of a list, must be regarded. Because such data is always bound to a variable, we get always lvalue references to these data elements. The interpretation of container elements depends on the value category of the container itself. So if a container has the value category of a rvalue, the value category of a container element should also be interpreted as such. This consideration leads to the following helper construction

namespace name
{
  struct forward_like;
}

template<ttypename T>
struct fun<name::forward_like>
{
  template<typename U>
  constexpr auto&& operator()(U&& u)
  {
    constexpr bool is_adding_const = std::is_const_v<std::remove_reference_t<T>>;

    if constexpr (std::is_lvalue_reference_v<T&&>)
    {
        if constexpr (is_adding_const)
            return std::as_const(x);
        else
            return static_cast<U&>(x);
    }
    else
    {
        if constexpr (is_adding_const)
            return std::move(std::as_const(x));
        else
            return std::move(x);
    }
  }
};

template<typename T>
using forward_like = fun<name::forward_like,T>;

The forward_like function is part of the c++23 standard. The code above is simply an aligned copy of the "a possible implementation" in the C++ reference pages.

The whole theory on avoiding loops can be express in an abstract diagram

The meaning of the different arrow types is - they cannot be composed. The function f transforms a value of type A to a value of type B. The type transformation T maps a type value A to the type value X and the type value B to the type value Y. If we use value declarations, f can be defined as

\(f: (x:X) \rightarrow (y:Y)\)

and the type mapping T we can define as

\(T: (A:Type) \rightarrow (X:Type)\)

In our template language C++ we may write

\(X = T\langle{}A\rangle\)

But a language like Idris, where types are first class objects, we can write down this relation as a normal function

\(X = T(A)\)

An alternative way to describe a function is the exponential style

\(f: B^A\)

The superscript A denotes the type of the function argument - B represents the return type of the function.

This is what we have in the functor picture \(F_T(f)\), that is

\(F_T: B^A \rightarrow T\langle{}B\rangle{}^{T\langle{}A\rangle{}}\)

Every binary function

\(f: A \otimes B \rightarrow C\)

can be expressed by two unary function calls

\(f(a,b) = \overline{f}(a)(b)\)

Here is \(\overline{f}\) the exponential transpose

\(\overline{f}: A \rightarrow C^B\)

With an application \($\) operator we can also write

\(f \ $\ (a,b) = \overline{f} \ $\ a \ $\ b\)

But what happens if we try to extrapolate this situation to an unary function

\(f \ $\ a = (\overline{f} \ $\ a)()\)

The exponential transpose takes a parameter and returns a function, which needs no argument to be executed. We can say

\(\overline{f} \ $\ a = \hat{f}_{f(a)} \qquad with \qquad \hat{f}_{f(a)}() = f(a)\)

In books on category theory the relation between a binary function and its exponential transpose is expressed by an evaluation function

\(eval: C^B \otimes B \rightarrow C\)

with

\(f = eval \cdot (\overline{f},\identity{})\)

We can now apply on both sides a value \((a,b):A \otimes B\)

\(f(a,b) = eval \cdot (\overline{f},\identity{})(a,b) = eval(\overline{f}(a),b)\)

which can be reduced to the already known formula

\(f(a,b) = \overline{f}(a)(b)\)

Our type based category seems to support exponentials obviously, because we can always construct them. Such a category is a cartesian closed category (CCC).

Details can be read in books on category theory. Now, first a sidestep follows - custom operators.

The idea is to contruct a new operator using the existing operator pair \(\ll\) - \(\gg\). This will only work if we use a capture object between.

So first we need a strategy object and then a the capture object:

namespace cat::op
{
  const struct a_t {} a;
  const struct ta_t {} a;
  const struct fa_t {} a;
  const struct fta_t {} a;

  template<typename C, typename V>
  struct capture
  {
    V v;
  };
}

The \(\ll\) operator captures the function object v and also the capture strategy type - the type C. Beside the application operator I also want to provide transpose operators, which apply a value and returns the transpose of a function. Dependend on the capture strategy type the behaviour can be controlled:

namespace cat
{
  template <typename F, typename O>
  decltype(auto) operator<<(F&& f, const O&)
  {
    return op::capture<O,F>{fwd(f)};
  }

  template<typename F, typename G>
  decltype(auto) operator>>(F&& f, G&& g)
  {
    if constexpr (is_op<op::a_t,F>) {
       return fwd(f).v(fwd(g));
    }
    if constexpr (is_op<op::ta_t,F>) {
       return ~fwd(f) <<op::a>> fwd(g);
    }
    if constexpr (is_op<op::fa_t,F>) {
      return functor<util::clear_type<G>,
                     name::application>()(fwd(f).v)(fwd(g));
    }
    if constexpr (is_op<op::fta_t,F>) {
      return functor<util::clear_type<G>,
                     name::transpose()(fwd(f).v)(fwd(g));
    }
    //This case should never happen - taking first simply a throw
    throw 1;
  }
}

The operator strategy detection is implemented in the following way

namespace detail
{
  template<typename A, typename C>
  struct is_op : std::false_type {};

  template<typename A, typename X>
  struct is_op<A, op::capture<A,X>> : std::true_type {};
}

template<typename A, typename C>
static constexpr bool is_op =
  detail::is_op<A,util::clear_type<C>>::value;

The helper construction clear_type, which reduces the *value category" to a type expression is implemented this way

namespace cat::util
{
  template<typename T>
  struct clear_type_decl
  {
    using T1 = typename std::remove_reference<T>::type;
    using T2 = typename std::remove_pointer<T1>::type;
    using type = typename std::remove_const<T2>::type;
  };

  template<typename T>
  using clear_type = typename clear_type_decl<T>::type;
}

Finally a test function shows how to use all of it

double test_list_functor(int i)
{
  auto one_third = +[] (int e) {
    return e*0.33333;
  };

  return one_third <<op::a>> i;
}

The + sign generates a lambda into a fun<lambda> - see the introduction of the lambda function in the functions as interpretation section.

In the case of a binary function, we need the transpose of this function. If we provide the transpose generator as the operator ~, the example code could look like this

int test_list_functor(int a, int b)
{
  auto multi = +[] (int e, int f) {
    return e*f;
  };

  return ~multi <a> e <<op::a>> f;
}

The transpose operator ~ returns a transpose function, which is defined as

namespace cat
{
  namespace name
  {
    struct transpose {};
  }

  template<typename F, typename A>
  struct fun<name::transpose, F, A>
  {
    template<typename... X>
    constexpr decltype(auto) operator()(X&&... x) const
    {
      return f(a,fwd(x)...);
    }

    const F f;
    const A a;
  };

  template<typename F>
  struct fun<name::transpose,F>
  {
    const F f;

    fun(F&& _f, name::transpose)
      : f(fwd(_f)) {}

    template<typename A>
    constexpr decltype(auto) operator()(A&& a) const
    {
      return fun<name::transpose,F,A>{f,fwd(a)};
    }
  };

  template<typename F> fun(F&&,name::transpose)
    -> fun<name::transpose,F>;

}

With the transpose application operator we can save an operator call

int test_list_functor(int a, int b)
{
  auto multi = +[] (int e, int f) {
    return e*f;
  };

  return multi <<ta>> e <<a>> f;
}

Every step of this evolution can be tested via the sourcecode from the git repo.

Instead of writing loops we want to apply a function on the container elements

decltype(auto) my_fun()
{
  auto f = [](int i) { return double(i/2); };
  std::list l{1,2,3,4,5};

  return f <<fa>> l;
}

and get back a container with elements of the result type of that function. This is what the concept of a functor means to be. But a functor isn't restricted to container types. Type encapsulation is the main aspect which can be handled in general by a functor.

For the practical application of functor operations, the availability of operators is important. The operator allows to plugin new functor definitions without changing the general usage via the operator.

Function application in the functor context is an extension of normal function application, which also can be expressed via an operator.

Beside values, function application may return the transpose of the function, where the applyed value is captured. The different application strategies can be chosen by appropriate operators.

The next goal is to develop the concept of polymorphic datatypes. Again the interpretation aspect plays the main role in this area.

In an object oriented programming style distinguishing between functions and data makes not so much sense, because the struct or the class represents both. My position here is similar but not the same. Structs and classes represent types and both functions and data are types. Because we can recognize a function by an interpreted fun template, we can do the same with data. Asking how functional languages are dealing with data, I give data structures the interpreter name ctr, which should be the shortcut for data constructor.

If we would say

struct circle
{
  double r;
};

We could say, that anything, which isn't a fun specialization is data. Better it seems for me to make it explicit by introducing data and data constructor interpretations

namespace cat
{
  template<typename T>
  struct ctr;

  namespace name
  {
    struct circle;
  }
}

using namespace cat;

template<>
struct ctr<name::circle>
{
  double r;
};

Now it's clear – it's data. Perhaps it makes sense at this point to introduce also a context

namespace cat
{
  namespace name
  {
    struct shape;
    struct circle;
  }

  template<typename, typename>
  struct ctr;
}

using namespace cat;

template<>
struct ctr<name::shape,name::circle>
{
  double r;
};

This looks a little bit like inheritance - but only a little bit. We can now also use the name circle in different contexts

namespace cat
{
  namespace name
  {
    struct grouping;
  }
}

using namespace cat;

template<>
struct ctr<name::grouping,name::circle>
{
  std::list<std::string> names;
};

The first application of these data structures may be a perimeter function

namespace cat::name
{
  struct perimeter;
}

using namespace cat;

template<>
struct fun<name::perimeter>
{
  double operator()(const ctr<name::circle>& c)
  {
    return 2 * pi * c.r;
  }

  double operator()(const ctr<name::rectangle>& r)
  {
    return 2 * (r.a + r.b);
  }
};

Comparing this situation with pattern matching of constructors in functional languages we can also write

using namespace cat;

template<>
struct fun<name::perimeter>
{
  template<typename T>
  double operator()(const ctr<name::shape,T>& t)
  {
     if constexpr (std::is_same<T,name::circle>::value) {
        return 2 * pi * t.r;

     } else if constexpr (std::is_same<T,name::rectangle>::value) {
        return 2 * (t.a + t.b);
     } else {
        std::runtime_error("Missing implementation");
     }
  }
};

At this point we can do a little bit more. We can associate a list of types to a context type and then we allow the construction of data types only for the defined typelist

namespace cat
{
  namespace type
  {
    template<typename... T>
    struct list;
  }

  namespace name
  {
    struct rectangle;
    struct cuircle;

    struct shape
    {
      using types = type::list<circle,rectangle>;
    };
  }
}

Again I must be consequent. The structure shape should be a context as a new language element

namespace cat
{
  template<typename>
  struct ctx
  {
    using types = type::list<>;
  };

  namespace name
  {
    struct shape;
  }
}

using namespace cat;

template<>
struct ctx<name::shape>
{
  using types = type::list<name::circle,name::rectangle>;
};

In the next step I want to check, if the data constructor type is valid. This means, that the data subtype must be in the typelist specification of the context.

namespace cat
{
  template<typename T>
  using ctx_types = typename ctx<T>::types;

  template<typename T,typename D, typename... A>
  requires (*fun<name::type::is_element_of,D,ctx_types<T>>())
  struct ctr;
}

using namespace cat;

template<>
struct ctr<ctx<name::shape>,name::circle>
{
  double m_r;
};

So, how does the is_element_of looks like. Some insights into typelists are necessary.

A typelist simply represents a list of types. A ctr::list will be provided later as a polymorphic data type. To avoid the introduction of a new language element the typelist will be defined here as a data specialization

namespace cat
{
  namespace name
  {
    struct typelist;
  }

  template<typename... A>
  struct data<name::typelist,A...>
  {};

  template<typename... A>
  using typelist = data<name::typelist,A...>;
}

This typelist is a data type without any constructor. If this really makes sense, or if this is a too pedantic approach to do this - I don't know. But it is possible to do it.

For tagging purposes it's allowed to instantiate a typelist, without the risk of any resource allocation.

A typelist, as any list, has two fundamental parts - the first element

namespace cat
{
  namespace detail
  {
    template<typename L>
    struct first;

    template<typename T, typename... TT>
    struct first<typelist<T,TT...>>
    {
      using type = T;
    };
  }

  template<Typelist L>
  using first = typename detail::first<L>::type;
}

and the tail

namespace cat
{
  namespace detail
  {
    template<typename L>
    struct tail;

    template<typename T, typename... TT>
    struct tail<typelist<T,TT...>>
    {
      using type = typelist<TT...>;
    };
  }

  template<Typelist L>
  using tail = typename detail::tail<L>::type;
}

Type aliases are helping to avoid to write always typename-type constructions, and they give us the feeling of a type function.

The concept Typelist allows us to restrict this definition of the first and the tail type functions to typelists. It's defined as

namespace name
{
  struct is_list;
}

template<typename L>
struct fun<name::is_list,L>
{
  constexpr bool operator()() const
  {
    return false;
  }
};

template<typename... T>
struct fun<name::is_list,typelist<T...>>
{
  constexpr bool operator()() const
  {
    return true;
  }
};

template<typename L>
concept Typelist = fun<name::is_list,L>()();

Instead of producing a static value I'm using here a constexpr call operator and also the fun template language element. I'm doing so, to increase the impression, that all is about functions, which reflects the spirit of category theory (take a look on Awodeys Book on Category Theory as an example - listed in the references - the online available version).

The size of a typelist may also be of interest

namespace cat
{
  namespace name
  {
    struct size;
  }

  template<typename... T>
  struct fun<name::size,typelist<T...>>
  {
    constexpr std::size_t operator()() const
    {
      return sizeof...(T);
    }
  };
}

Again, this is also a fun specialization together with a constexpr call operator.

For the desired is_element_of function let's first calculate the index of a type in the list – if available

namespace cat
{
  namespace name
  {
    struct index_of;
  }

  template<typename T, std::size_t I>
  struct fun<name::index_of,T,typelist<>,std::integral_constant<std::size_t,I>>
  {
    constexpr std::size_t operator()() const
    {
      return I;
    }
  };

  template<typename T, typename L, std::size_t I>
  struct fun<name::index_of,T,L,std::integral_constant<std::size_t,I>>
  {
    constexpr std::size_t operator()() const
    {
      return fun<name::util::is_same,T,first<L>>()()
        ? I
        : fun<name::index_of,T,tail<L>,std::integral_constant<std::size_t,I+1>>()();
    }
  };

  template<typename T, typename L>
  struct fun<name::index_of,T,L>
  {
    constexpr std::size_t operator()() const
    {
      return fun<name::index_of,T,L,std::integral_constant<std::size_t,0>>()();
    }
  };
}

If no match is found, the empty list must be handled, here by setting the result to an exceptional value, which is the size of the typelist, which is equal to the max index plus one.

Now it's time to provide the tl_is_element_of function, which translates the numeric index value into a boolean one.

namespace cat
{
  namespace name
  {
    struct is_element_of;
  }

  template<typename T, typename L>
  struct fun<name::is_element_of,T,L>
  {
    constexpr bool operator()()
    {
      return fun<name::size,L>()() > fun<name::index_of,T,L>()();
    }
  };
}

The quint essence of this work is an universal quantifier, which tells us, that for any type, which exists in the typelist of the context, a data constructor is allowed. The data constructor definition looks now like this

namespace cat
{
  template<typename>
  struct ctx
  {
    using types = typelist<>;
  };

  template<typename T>
  using ctx_types = typename ctx<T>::types;

  template<typename T,typename D, typename... A>
  requires (fun<name::is_element_of,D,ctx_types<T>>()())
  struct ctr;
}

The introduction of the term universal quantifier as a property of a data constructor element is nice. Perhaps it is a good opportunity to make some simple notes on logic.

What is logic? A very fundamental question. I'm not the person who should give a definition of logic here. But I know, that logic has to do with the underlying language. Within this language we describe first basic objects and then some construction principles, which describe how to construct more complex objects using these basic objects. Because the more complex objects behave like the basic objects, we can apply the construction principles also to this more complex objects. This way a recursive language definition is developed.

Combining things to more complex things is the area of operators. In classical logic we have operators like \( \land{}, \lor{}, \neg{}, \implies \).

First, the mathematicians started with a language, which was derived from a natural language like english. Then formal languages became of interest, like the lambda calculus or the combinator logic. Today we speak about homotopy type theory or quantitative type theory and perhaps there are other approaches.

The motivation behind the wish, to use a formal language for logical purposes, is to construct proves by programs. Because logical proves may be very complex and thus difficult to manage by persons without a high risk of making mistakes.

Types - in constrast to sets - seem to play an important role in such newer approaches to make logic. In our case a type is simply a name, which can be make known to the compiler. And the generic template engine of C++ allows to do things with these types - especially types may be templated, or type functions.

So we have a relation beween propositions and types and type functions (templated types) and predicates. A resolved predicate is then a proposition - or here a type. Using predicates we have the problem, that not all input parameters (also types) are producing valid result types. A result type is valid if we can produce a value of this type - or a type is valid if a value is constructible.

On the specification side we define now a set of types to be valid as input types. This restriction to a set of usable types can be interpreted as an universal quantifier in mathematics. In C++ it looks like

template<typename R, typename T>
requires "T-is-an-element-of-a-certain-set-of-types"
          &&
         "R-is-in principle-constructible"
R do_something(T&& t);

What we can see is, that functions (rather function specifications) are promising constructions (values) of a certain type. At this specification stage, we cannot be sure, that this is really the case. At the end we must also take a look on the implementation. The final question is - what can the compiler do for us also in the implementation area. But one after the other.

In C++-20 this construction allows us to work with universal references in a better way than before. But even this is an improvment, C++ is still not very educational with regards to mathematics. By using C++ a developer learns programming but not mathematics. I don't think that this is a must. I think this is a bad strategy.

All these things have to do with logic. With types and their interpretations together with a framework, which describes the relation between these basic objects, we make logic or something similar to logic. But the logical aspect should become more and more important.

So this is a vague description of what we are doing - or trying to do - here.

Polymorphic datatypes are closely related to the concept of a sum in category theory. But let's first take a look on the idea of a product.

A product is related to other objects, which also have projections. An object P has perhaps the projections

\(P_a: P \rightarrow A \qquad \hat{=} \qquad A^P \\ P_b: P \rightarrow B \qquad \hat{=} \qquad B^P\)

Our product has the projections

\((A \otimes B)_a: (A \otimes B) \rightarrow A \qquad \hat{=} \qquad A^{A \otimes B} \\ (A \otimes B)_b: (A \otimes B) \rightarrow B \qquad \hat{=} \qquad B^{A \otimes B}\)

If we have many of such objects P, our product is characterized by the property, that every P_a can be written as

\(P_a = (A \otimes B)_a \circ C_p\)

where

\(C_p: P \rightarrow (A \otimes B) \qquad \hat{=} \qquad (A \otimes B)^P\)

So the idea of all this is to say, that a product is a best representiation of the conecpt of projections. Th is allows us to say, that a product is a limit, which means exactly - something very good.

Now let's go the opposite direction, by reversing the arrows.

The opposite of an projection is an injection. Now we have two injections

\((A \oplus B)_a: A \rightarrow (A \oplus B) \qquad \hat{=} \qquad (A \oplus B)^A \\ (A \oplus B)_b: B \rightarrow (A \oplus B) \qquad \hat{=} \qquad (A \oplus B)^B\)

In analogy to the product every structure, which provides injections should be related to a sum via

\(I_a = C_s \circ (A \oplus B)_a\)

where

\(C_s: (A \oplus B) \rightarrow S \qquad \hat{=} \qquad S^{A \oplus B}\)

A sum is also called a coproduct because of the reverse arrow construction. As a coproduct, the limit property is also called colimit.

The main advantage of such a sum is that it represents many aspects by one aspect only. Comming back to the world of programming, such a common type is very useful as return type of a function. We can return a shape and this shape encapsulates perhaps a rectangle or a circle. We may automatically think on the object oriented programming feature inheritance. But I want to avoid the base class dependency. The base construction looks like

template<typename T>
struct data
{
   template<typename X>
   data(X&& x) : m_p(&x), m_i(tl_index_of<X,T>::value) {}

   template<typename F>
   decltype(auto) apply(F&& f)
   {
       return helper(fwd(f),T{},m_i);
   }

   template<typename F, typename L>
   decltype(auto) helper(F&& f, L l, std::size_t i)
   {
      if constexpr (std::is_same<L,typelist<>>::value) {
         throw 1;
      } else {
         if (i == 0) {
            auto p = static_cast<tl_first<L>*>(m_p)
            return f(p);
         }
         return helper(fwd(f),tl_tail<L>, i-1);
      }
   }

   void* m_p;
   const std::size_t m_i;
};

The sum type is represented by a typelist. The constructor saves the index of the injected type into a member. With this index we can reconstruct the real type and are able to apply the real type to the polymorphic function.

A little bit of test code demonstrates the principle.

template<typename>
struct obj
{
};

using objs = typelist<obj<circle>,obj<square>,obj<rectangle>>;

struct print;

template<>
struct fun<print>
{
   void operator()(obj<circle>*)
   {
      std::cout << "circle" << std::endl;
   }

   void operator()(obj<rectangle>*)
   {
      std::cout << "rectangle" << std::endl;
   }

   void operator()(obj<square>*)
   {
      std::cout << "square" << std::endl;
   }
};

int main()
{
   auto s = std::make_unique<obj<square>>();

   data<objs> o(s.get());

   o.apply(fun<print>());

   auto c = ctr<shape,circle>{3.5};
   return 0;
}

The next step is to connect the polymorphic data structure with the data constructors ctr in a more flexibel fashion. From the coding perspective this all looks very similar to the structures we find in the visitor pattern area. This is the one and only place I mention this pattern.

So let's improve this initial example of a polymorphic data type. A very flexible approach is to create a data carrier class together with a base class

namespace base
{
   struct carrier
   {
     carrier(std::size_t i) : index(i) {}
     const std::size_t index;
   };
}

namespace detail
{
   template<typename T>
   struct carrier : base::carrier
   {
     carrier(T&& _t) :
       base::carrier(ctr_index<clear_type<T>>),
       t(fwd(_t)) {}
     T t;
   };
}

Now let's align our first example

template<typename T, UQ_CTX(T)>
struct data
{
  template<typename X, UQ_CTX_CTR(T,X), UQ_CTX_COMPLETE(T)>
  data(X&& x) : c(new detail::carrier<X>{fwd(x)}) {}

  template<typename F>
  decltype(auto) apply(F&& f) const
  {
    return fwd(f) <op::d> *this;
  }

  template<typename F>
  decltype(auto) apply(F&& f)
  {
    return fwd(f) <op::d> *this;
  }

  std::unique_ptr<base::carrier> c;
};

I anticipated the introduction of an application operator op::d and I added three universal qualifiers. First, the data type parameter should reference a context

#define UQ_CTX(A_T) typename = ctx_types<A_T>

Second, the constructor parameter should represent a data constructor stucture, which references to the same context as the data parameter

template<typename C, typename T>
struct same_context : std::false_type {};

template<typename C, typename T>
struct same_context<C,ctr<C,T>> : std::true_type {};

template<typename C, typename T>
struct fun<same_context<C,T>>
{
  constexpr bool operator*()
  {
    return same_context<C,T>::value;
  }
};

#define UQ_CTX_CTR(A_T,A_X) typename = \
    typename std::enable_if<*fun<same_context<A_T,A_X>>()>::type

The last qualifier checks if all contructor objects can be constructed

namespace detail
{
  template<typename C, typename T>
  struct is_constructible;

  template<typename C, typename... T>
  struct is_constructible<C, typelist<T...>>
  {
    static constexpr bool value =
      (std::is_constructible<ctr<C,T>>::value && ...);
  };
}

template<typename C>
struct ctx_constructible
{
  static constexpr bool value =
    detail::is_constructible<C,ctx_types<C>>::value;
};

template<typename C>
struct fun<ctx_constructible<C>>
{
  constexpr bool operator*()
  {
    return ctx_constructible<C>::value;
  }
};

#define UQ_CTX_COMPLETE(A_T) typename = \
    typename std::enable_if<*fun<ctx_constructible<A_T>>()>::type

The cooresponding testcode is

int main()
{
  data<shape> o(ctr<shape,circle>{1.0});

  o.apply(fun<print>());

  return 0;
}

Bit isn't this polymorphic data type also a functor - better, can we deliver anfunctor interpretation for the function application?

Indeed, we can simply align the list functor code to

template<typename T, typename F>
struct fun<functor<data<T>>,F>
{
  F f; 

  using GL = ctx_types<T>;
  using GC = detail::carrier<ctr<T,util::tl_first<GL>,P...>>;
  using GR = decltype(f(std::declval<GC>().t));

  template<typename A>
  GR operator()(A&& a)
  {
    return apply(fwd(a),ctx_types<T>{},fwd(a).c->index);
  }

  template<typename A, typename L>
  GR apply(A&& a, L l, std::size_t i)
  {
    if constexpr (std::is_same<L,util::typelist<>>::value) {
      throw 1;
    } else {
      if (i == 0) {
        auto p =
          static_cast<carrier<ctr<T,util::tl_first<L>>>*>
          (fwd(a).c.get());
        return f(p->t);
      }
      return apply(fwd(a), util::tl_tail<L>{}, i-1);
    }
  }
};

Now the test code looks like this

int main()
{
  using namespace cat;

  data<shape> o(ctr<shape,circle>{1.0});

  fun<print>() <<op::fa>> o;

  return 0;
}

This application works, but is it really functorial? The problem is the return value. The return value is not of the type data<void>. The function fun<print> should translate the type data<shape> to a datatype data<void>. But the return value is simply void. Another function could be fun<perimeter>. Then the return value should be data<double>, but we will get simply double as the return value.

Actually, we can say, that the application mechanism for the data objects is similar to functorial data, but not exactly the same. One measure to distinguish this situation from functorial data, could be to introduce a new operator.

namespace op
{
    const struct a_t {} a;
    const struct fa_t {} fa;
    const struct da_t {} da;

    template<typename C, typename V>
    struct capture
    {
       V v;
    };
}

The operator definitions must be aware of this type

template<typename F, typename G>
decltype(auto) operator>>(F&& f, G&& g)
{
  if constexpr (is_op<op::a_t,F>) {
    return fwd(f).v(fwd(g));
  }
  if constexpr (is_op<op::fa_t,F>) {
     return functor<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  if constexpr (is_op<op::da_t,F>) {
     return data_application<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  throw 1;
}

Missing is the new concept data_application. Again, technically it's something like the functor concept

template<typename T>
struct functor
{
  template<typename F>
  constexpr decltype(auto) operator()(F&& f) const
  {
    return fun<functor<util::clear_type<T>>,F>{fwd(f)};
  }
};

template<typename T>
struct data_application
{
  template<typename F>
  constexpr decltype(auto) operator()(F&& f) const
  {
    return fun<data_application<util::clear_type<T>,F>{fwd(f)};
  }
};

The plugin code needs now only a new creation strategy

template<typename T, typename F>
struct fun<data_application<data<T>>,F>
{
  F f;

  using GL = ctx_types<T>;
  using GC = detail::carrier<ctr<T,util::tl_first<GL>,P...>>;
  using GR = decltype(f(std::declval<GC>().t));

  template<typename A>
  GR operator()(A&& a)
  {
    return apply(fwd(a),ctx_types<T>{},fwd(a).c->index);
  }

  template<typename A, typename L>
  GR apply(A&& a, L l, std::size_t i)
  {
    if constexpr (std::is_same<L,util::typelist<>>::value) {
      throw 1;
    } else {
      if (i == 0) {
        auto p =
          static_cast<carrier<ctr<T,util::tl_first<L>>>*>
          (fwd(a).c.get());
        return f(p->t);
      }
      return apply(fwd(a), util::tl_tail<L>{}, i-1);
    }
  }
};

We can now apply a polymorphic function directly to the data object

auto data<shape> o(ctr<shape,circle>{2.2});

auto value = fun<perimeter>() <<op::da>> o;

With a small extension of the perimeter function

template<>
struct fun<perimeter>
{
  double operator()(const data<shape>& d)
  {
    return (*this) <<op::da>> d;
  }
  ...
};  

we can directly apply the function to the data

auto data<shape> o(ctr<shape,circle>{2.2});

auto value = fun<perimeter>() <<op::a>> o;

A further concept comes now, which is widely used in the area of operations with side effects. A operation may return something or nothing dependent on the behaviour of the technical behaviour of the environment. Of interest is especially the chaining of such operations.

Monads are often mentioned in functional programming in the area of side-effect-ful operations. They are useful for it, but the meaning behind hasn't anything to do with side-effects. In the same sense a std::optional can be used to handle side-effects but that's not the nature of a std::optional. A std::optional may have one value or not. If it has a value, we can take this value as input for a function, which itself returns a std::optional - containing a value or not. In the context of operations with side effects this behaviour may be useful.

Containing a value or not is like a list, which can contain at most 1 element. So it is not a surprise, that there must exist a functor interpretation for a std::optional - only the capture helper must be implemented

template<typename T, typename F>
struct fun<functor<std::optional<T>>,F>
{
  template<typename A>
  decltype(auto) operator()(A&& a)
  {
    using type =
      decltype(f(std::declval<decltype(*a)>()));

    if constexpr (std::is_same<type,void>::value) {

      if (fwd(a)) {
        f(*fwd(a));
      }

    } else {

      std::optional<type> ro;

      if (fwd(a)) {
        ro = f(*fwd(a));
      }

      return ro;
    }
  }

  F f; 
};

In contrast to a normal functor situation, let's consider another function type:

\( f: A \rightarrow std::optional \langle B \rangle \)

If we take for \(A\) an \(int\) and for \(B\) a \(double\) the functor way would deliver

std::optional<std::optional<double>>
test(std::optional<int> o,
     std::function<std::optional<double>(int)> f)
{
   std::optional<std::optional<double>> r;

   if (o) {
      r = f(*o);
   } 
   return r;
}

The functor operation would return an std::optional<std::optional<double>>. It's clear, a std::optional<double> would carry enough information. But before we start now to implement a sophisticated template deduction algorithm, to solve this problem, it's worth to show, that the nested std::optional construction represents a binary product. This is a nice example, which tells something about abstraction in category theory. Let's take a look on the following pattern sequence

\( optional \langle optional \langle int \rangle \rangle \qquad \hat{=} \qquad optional(optional(int)) \)

Here I'm replacing angle brackets by round brackets. Now it looks now like a composition

\( optional(optional(int)) \qquad \hat{=} \qquad (optional \circ optional)(int) \)

And as a shortcut we can write

\( (optional \circ optional)(int) \qquad \hat{=} \qquad optional^2(int) \)

Now take a look on a list and a optional or more in general on a G and on a H

\( G \circ H \)

Next we can define the projections

\( first(G \circ H) = G \)

and

\( second(G \circ H) = H \)

Because of the projections we can say \( G \circ H \) is a binary product. But the \(\circ\) is perhaps distracting. We can also write

\( (G,H) \qquad \hat{=} \qquad G(H(type)) \qquad \hat{=} \qquad G \langle H \langle type \rangle \rangle \)

Now let's again consider the composition of the identical type constructors or type functions

\( G \circ G \)

The question is now, if there exists an operation \(\mu\), which holds

\( \mu: G \circ G \rightarrow G \)

Such a μ we can find on values very often

\( (string, string) \rightarrow string \)

is just a string concatenation and

\( (int,int) \rightarrow int \)

can be expressed by an addition or a multiplication.

The μ is the essence of a structure, which is called a monoid.

In the case, such a μ exists for type constructors or type functions like an optional or a list, we can define the monadic binding

\( G \langle A \rangle \rightarrow ( A \rightarrow G \langle B \rangle ) \rightarrow G \langle B \rangle \)

Such a G can be regarded as a monad, which itself can be regarded in a certain context as a monoid.

From the programmer perspective the task is now to deliver a new operator and the monadic binding. For the structurs optional and list we have already functor interpretations. For both structures also an interpretation of a monad is possible.

The monad interpretation looks identical compared to the functor one

template<typename T>
struct functor
{
  template<typename F>
  constexpr decltype(auto) operator()(F&& f) const
  {
    return fun<functor<util::clear_type<T>>,F>{fwd(f)};
  }
};

template<typename T>
struct monad
{
  template<typename F>
  constexpr decltype(auto) operator()(F&& f) const
  {
    return fun<monad<util::clear_type<T>>,F>{fwd(f)};
  }
};

Next we can introduce a monadic operator type

namespace op
{
   const struct a_t {} a;
   const struct fa_t {} fa;
   const struct da_t {} da;
   const struct ma_t {} ma;

   template<typename C, typename V>
   struct capture
   {
      V v;
   };
}

The closing part of the operator can now be written as

template<typename F, typename G>
decltype(auto) operator>>(F&& f, G&& g)
{
  if constexpr (is_op<op::a_t,F>) {
    return fwd(f).v(fwd(g));
  }
  if constexpr (is_op<op::fa_t,F>) {
     return functor<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  if constexpr (is_op<op::da_t,F>) {
     return data_application<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  if constexpr (is_op<op::ma_t,F>) {
     return monad<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  throw 1;
}

An example for a monad function can be that of an optional

template<typename T, typename F>
struct fun<monad<std::optional<T>>,F>
{
  template<typename A>
  decltype(auto) operator()(A&& a)
  {
    using type =
      decltype(f(std::declval<decltype(*a)>()));

    if constexpr (std::is_same<type,void>::value) {

      if (fwd(a)) {
        f(*fwd(a));
      }

    } else {

      type ro;

      if (fwd(a)) {
        ro = f(*fwd(a));
      }
      return ro;
    }
  }

  F f; 
};

A test for this monad could be

using namespace cat;

std::optional<double> test_optional_functor(std::optional<int> o)
{
  auto one_third = [] (int e) {
    return std::optional<double>(e*0.33333);
  };

  return one_third <<op::ma>> o;
}

int main()
{
  auto o = test_optional_functor({1});

  if (o) {
    std::cout << *o << std::endl;
  }

  return 0;
}

This situation describes a monadic application, where a monadic function is applied to a monadic value. A monadic binding goes the opposite direction, which takes a monadic value and binds it to a monadic function. This can be achieved simply by switching the parameters around. The monadic binding is often used to simulate the procedural left to right sequencing of commands. Here the actual functor code motivates the go first the analog application way.

Another problem we have still regarding the use of operators. We don't have control over the operator precedence. A right to the left logic is easier to implement, than a left to right sequencing.

Actually we can apply a function on a value

fun<x>() <<op::a>> v;

But what can we do if the function has more than one parameter in it's definition. We should be able to write the following

f<x>() <<op::a>> v1 <<op::a>> v2;

To deliver such a functionality let's first introduce a new operator

namespace cat::op
{
  struct t_ta ta;
}

Now we can plugin a new concept - the function transpose - according to the considerations in an earlier section. A function transpose is perhaps not the same as a curried function, because the transposed function is not equal compared to the original one - in c++.

The transpose of a function is again a function, where values are captured. Again, the term capture of a lambda is equivalent to members of an object. So a transpose function could be

struct transpose {};

template<typename F, typename A>
struct fun<transpose, F ,A>
{
  fun(F&& _f, A&& _a, transpose) : f(fwd(_f)), a(fwd(_a)) {}

  template<typename... X>
  constexpr decltype(auto) operator()(X&&... x)
  {
    return f(a,fwd(x)...);
  }

  F f;
  A a;
};

template<typename F, typename A>
fun(F&&,A&&,transpose) -> fun<transpose,F,A>;

The operator handler can now return this function in the following way

template<typename F, typename G>
decltype(auto) operator>>(F&& f, G&& g)
{
  if constexpr (is_op<op::a_t,F>) {
    return fwd(f).v(fwd(g));
  }
  if constexpr (is_op<op::t_ta,F>) {
    return fun(fwd(f).v,fwd(g),transpose{});
  }
  if constexpr (is_op<op::fa_t,F>) {
    return functor<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  if constexpr (is_op<op::da_t,F>) {
    return data_application<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  if constexpr (is_op<op::ma_t,F>) {
    return monad<util::clear_type<G>>()(fwd(f).v)(fwd(g));
  }
  throw 1;
}

A test code could loo like this

int test_transpose_1()
{
  auto multi = [] (int e, int f) {
    return e*f;
  };

  using namespace cat;

  return multi <<op::ta>> 6 <<op::a>> 2;
}

int test_transpose_2()
{
  auto multi = [] (int e, int f) {
    return e*f;
  };

  using namespace cat;

  return (multi <<op::ta>> 6 <<op::ta>> 2)();
}

int main()
{
  auto r1 = test_transpose_1();

  std::cout << r1 << std::endl;

  auto r2 = test_transpose_2();

  std::cout << r2 << std::endl;

  return 0;
}

We can improve this construction by separating the transpose function by an transpose operator and an application

template<typename F>
constexpr decltype(auto) operator~(F&& f)
{
  return fun(fwd(f),name::transpose{});
}

The closing operator part can now be rewriten as

template<typename F, typename G>
decltype(auto) operator>(F&& f, G&& g)
{
  ...
  if constexpr (is_op<op::ta_t,F>) {
    return (~fwd(f).v) <<op::a>> fwd(g);
  }
  ...
}

We can add some additional testcases, which show the usage of this operator

int test_transpose_1()
{
  using namespace cat;

  auto multi = +[] (int e, int f) {
    return e*f;
  };

  return (~multi) <<op::a>> 6 <<op::a>> 2;
}

int test_transpose_2()
{
  using namespace cat;

  auto multi = +[] (int e, int f) {
    return e*f;
  };

  return (~(~multi <<op::a>> 6) <<op::a>> 2)();
}

int test_transpose_3()
{
  using namespace cat;

  auto multi = +[] (int e, int f) {
    return e*f;
  };

  return (multi <<op::ta>> 6 <<op::ta>> 4)();
}

The transpose operator ~ and the lambda operator + seem to me to be very powerful helpers, which avoid very lengthy function calls. This is the way operators should work in general.

Now we can regard a functor operation, where we apply a binary function on a list of values. The result will be a list of unary functions, which we want apply again to a list of values. This consideration leads to the concept of an applicative. This concept lies between the functor and the monad. So an applicative is a functor but not a monad. A monad is an applicative.

The concept of an applicative can be motivated by applying a binary function to an encapsulated value. In the case of a list we apply such a function to each list element. Let's assume we take the list elements as the first argument of this binary function. The result is a list of unary functions. Now we come in the situation, that we want - perhaps - apply this list of functions to another list of values. So the applicative generalizes the functor. So let's first construct such a list of functions

auto lf = [](int a, int b) { return a+b;} <<op::fta>> list<int>{1,2,3};

The next step is now to specify an operator aa, which expresses this application type

auto l = lf <<op::aa>> std::list<int>{5,6,7};

In the case of a list, every function of the function list, will be applyed to the list of values, like the functor algorithm would do.

In the same way we integrated the functor or the monad concept, the applicative can also be integrated in the same way via the new operator aa.

The code can be found in the source code repo.

Let's assume, that we are only working with function of one argument. If we compose two such functions f and g using the composition operator \(\circ\)

\( f \circ g \)

we translate the argument of the function f from A to B, if g takes a parameter of type B and creates a value of type A. If we use the exponential style for functions we get

\( f:X^A \xrightarrow{g:A^B} f':X^B \)

So the argument type movement goes for the functions f and f' from A to B, but the arugment transforming function g moves from B to A. These opposite directions indicate a contravariant functor. This seems to be the nature of a composition.

But is it possible to look on the composition as a covariant functor? For this purpose we can regard the function f as a transformation of the return type of function g

\( g:A^B \xrightarrow{f:X^A} g':X^B \)

Now the return type movement of g goes from A to X as it goes for the return type transforming function f. So we are now able to use a covariant functor to model a composition.

Now we can provide a functor plugin for a fun object in the following way

namespace cat
{
  template<typename F, typename... T>
  struct fun<name::functor,fun<T...>, name::application>, F>
  {
    template<typename G>
    decltype(auto) operator()(G&& g)
    {
      return [gg=fwd(g),ff=std::move(f)](auto&&... a) mutable {
        return ff(gg(fwd(a)...));
      };
    }

    F f; 
  };
}

The composition is simply a functor application, where the one function translates the return value of the other one

double test_fun_functor()
{
  using namespace cat;

  auto multi = +[](int a, int b) {
    return a * b;
  };

  auto one_third = +[] (int e) {
    return e*0.33333;
  };

  return (one_third <op::fa> multi)(4,6);
}

int main()
{
  std::cout << test_fun_functor() << std::endl;

  return 0;
}

Instead of a fun-functor we can identify this functor to be a hom-functor in category theory. We can extend a little bit this composition approach by a transpose aspect. Let's take a look on the testcode first

double test_fun_functor_transpose()
{
  using namespace cat;

  auto multi = +[](int a, int b) {
    return a * b;
  };

  return (multi <op::fta> multi)(4,6)(2);
}

int main()
{
  std::cout << test_fun_functor_transpose() << std::endl;

  return 0;
}

The result of the composition is again a function, which takes additional arguments. We can state, that the result of a composition is an exponential transpose of the first argument. This transpose may need additional parameters to complete the call. The plugin code is very simple. First the operator definition

    const struct a_t {} a;
    const struct ta_t {} ta;
    const struct fa_t {} fa;
    const struct fta_t {} fta;
    const struct da_t {} da;
    const struct ma_t {} ma;

    struct capture
    {
      V v;
    };
}

This defines a new operator symbol fta, which is connected within the close operator implementation

template<typename F, typename G>
decltype(auto) operator>(F&& f, G&& g)
{
  ...
  if constexpr (is_op<op::fta_t,F>) {
    using ftype = decltype(fwd(f).v);
    return functor<util::clear_type<G>,
                   name::transpose,ftype>{fwd(f).v}(fwd(g));
  }
  ...
}

Finally the plugin code

template<typename F, typename... T>
struct fun<name::functor,fun<T...>, name::transpose, F>
{
  template<typename G>
  constexpr decltype(auto) operator()(G&& g) const
  {
    return +[gg=fwd(g),ff=std::move(f)](auto&&... a) {
      return +[fff=std::move(ff),
               ggg=std::move(gg),
               t=std::forward_as_tuple(a...)](auto&&... b)
      {
        return fff(std::apply(ggg,t),fwd(b)...);
      };
    };
  }

  F f; 
};

As a first example of a polimorphic data type we can replace a std::optional by the maybe type. Two data constructors are needed - a constructor, which represents nothing and a constructor to represent just the value.

namespace cat
{
  namespace name
  {
    struct maybe {};
    struct nothing;
    struct just;
  }

  template<>
  struct ctx<name::maybe>
  {
    using types = typelist<name::just,name::nothing>;
  };

  template<typename A>
  struct ctr<name::maybe,name::nothing,A>
  {};

  template<typename A>
  using nothing = ctr<name::maybe,name::nothing,A>;

  template<typename A>
  struct ctr<name::maybe,name::just,A>
  {
    ctr(A&& a) : value(fwd(a)) {}

    A value;
  };

  template<typename A>
  using just = ctr<name::maybe,name::just,A>;

  template<typename A>
  using maybe = data<name::maybe,A>;
}

The functor, applicative and monad interpretations must now be added to this structure, by using the data application operator. Take a look at the code for more details.

A possible list implementation looks very similar.

In analogy to the maybe structure, we need to data constructures. First one, which represetns an empty list and second one, which holds the list_data.

namespace cat
{
  namespace name
  {
    struct list {};
    struct list_data;
    struct empty;
  }

  template<>
  struct ctx<name::list>
  {
    using types = typelist<name::empty,name::list_data>;
  };

  template<typename A>
  struct ctr<name::list,name::empty,A>
  {};

  template<typename A>
  using empty = ctr<name::list,name::empty,A>;

  template<typename A>
  struct ctr<name::list,name::list_data,A>
  {
    template<typename X>
    ctr(A&& a, X&& x) : first(fwd(a)), tail(fwd(x)) {}

    A first;

    data<name::list,A> tail;
  };

  template<typename A>
  using list_data = ctr<name::list,name::list_data,A>;

  template<typename A>
  using list = data<name::list,A>;
}

In contrast to the maybe structure, the list_data object has an additional tail attribute, which makes this structure recursive. The recursion ends with an empty list. Again we have to add the functor, applicative and the monad interpretation to this structure. For details refer to the code.

The example code can be found at http://git.macajobe.de.

For making a runnable program take a look at the README.

There is certainly a big community, which is very impressed by the topic programming. Even it should be possible to learn children how to write or create software – is the opinion. Why there isn't an equivalent community, which states, that children should learn mathematics (perhaps there is one I don't know)? Programming seems to be much simpler, could be an answer. Or, programming is much more exiting?

In the same direction goes the evolution of getting more and more programming languages. It seems, there are many problems, which can only be solved by programming.

Another aspect is the device – the computer, the smartphone – which seems to be an object of desire and the language to talk with are programming languages.

If I talk in this way about programming, the feeling must arise, that something is missing. The question is "why".

One direct answer on my own question "why" is, that programmiing let us feel to make important things, because we are using a language in a formalized, systemtic way, which give us the impression it has to do with logic. So we feel like mathematicians.

Indeed, there is a connection between programming and logic. But in the end our feeling is in general wrong.

But what are the indicators of this failure. I think it is expressed in the yearning after new programming languages, new language features and new language concepts. Even I am a highly experienced c++ developer – and I can say it's a complex language – not so easy to manage – what is the result of my logical work. What is the logic of my matheamical work my soul feels to do.

Devices are all around. So children will become good pyhsicists, because of the experiences they make in the area if doing something and analyzing the response. In the same way software developers are making code and they only know if it is working correctly by testing. Without testing we cannot be sure.

But logic in a mathematical sense is more art then physics. And art must be exchanged by people and certainly not by devices.

Mathematics is only one element in the world of the art of thinking systematically. Philosophy and Linguistic as scientific research areas are in the same way important. So if you are bored - take a look on these disciplines in the area of logic.

If we would argue, can we really distinguish devices from human beeings and is my last statement really acceptable I would say.

We are able to construct a world where it will be difficult to distinguish devices from a human beeings but we can also do the opposite.

In a world in which it is difficult to know if an intelligence is of human nature or not, it should be alway possible to identify the origin of an intelligence, because of the creation path - something like a birth certificate. I ignore my personal fellings at this point. That's a different thing.

Now, is it possible, that a human beeing can construct a device, which is more intelligence than a human beeing. Because the term intelligence is not a very clear term - the meaning is not totally clear - we can be more precise.

Is it possible, that a human beeing can construct a device, which has more capabilities in logic than the creator?

But if there is an intelligence of an higher order, it would not be possible for human beeings to prove, that this is really the case. This means that this intelligence is potentially bullshit. I cannot prove that something is correct but I don't understand it.

So what is the motivation to find such an intelligence. It's a way to introduce god. And there is no way to dicuss about god. On one hand god is dead, so take the new one.

• https://gist.github.com/sorrge/2d2271e57ad1e91a50ea Dependent types in C++
• https://web.mit.edu/6.001/6.037/sicp.pdf Structure and Interpretation of Computer Programs
• https://vittorioromeo.info/index/blog/capturing_perfectly_forwarded_objects_in_lambdas.html
• https://awodey.github.io/catlog/notes/catlog0.pdf