Abstraction type system

Type system is a construction for guarantees safely in a language, though exist many other aplications like metaprogramming... It's means that i can writes a program but with a safe way, sure it's is perfect why it's solve many problems that programmers has after of compilation. The main idea that i can encode and represent a subset of solutions with a safe type system and better maybe the type can help me represent that.

Data representing

Ok it's mean i have a safe type system and i could represent my types of data..... Ok sure...., but no... limited type system have a weak power of abstraction(no i am not talking about c++ but yes a little part of the language).

The problem of "pair"

Let's go represent a pair: Pair is a tuple of the two values like (P x y), where x and y are values, in this discussion the values x and y can be encode a T type and a Tuple T type. So... we have a recursive tuple or in other words a recursive type representation.

Using a untyped functional language it's can to be easy reducing a simply encoding of church:

pair = function(x) return (function(y) return (function(f) return f(x)(y) end) end) end
first = function(_) return _(function(x) return (function(y) return x end) end) end
second = function(_) return _(function(x) return (function(y) return y end) end) end
(function(my_pair) display_ioeffect(first(my_pair)) display_ioeffect(first(second(my_pair))) display_ioeffect(second(second(my_pair))) end)
(pair("hello ")(pair("world")("!")))

As result you will to receive a print message "Hello World!" Very easy and simple yes? OK, but it's really very unsafe let's consider that:

display_ioeffect(first(second(my_pair))) => error trying get a value of string

The best compilers in runtime system will say that you do a mistake but if your language don't have type system it's unpredictable

So.. again let's consider a new codification using algebraic date types:

data Tuple a = Value a | Pair (Tuple a) (Tuple a) | V (Tuple a) deriving Show

pair :: Tuple a -> Tuple a -> Tuple a
pair k x = (Pair (V k) (V x))

first :: Tuple a -> Tuple a
first (Pair k y) = fx k
                   where fx(V d) = d

second :: Tuple a -> Tuple a
second (Pair k y) = fx y
                   where fx(V d) = d

value (Value d) = d

main = do
  let f_ = (pair (Value "Hello ") (Value "World"))
  let f = (pair f_ (Value "!"))
  putStrLn ((value $ first $ first f) ++ (value $ second $ first f) ++ (value $ second f))

Ok... i can represent a tuple with recursive types and with safe way!.

Again but in c++ would be like?? Consider the code in c++17:

#include <variant>
#include <string>
#include <iostream>
#include <list>

template <typename T>
struct Tuple {
    using Pair = std::variant<T, Tuple*>;
    Tuple(Pair f, Pair s)
        : f_({ f, s })
    {
    }
    Tuple* operator()()
    {
        return this;
    } // for secure pointer uses return new Tuple(f_.front(), f_.back())
    template <typename T_>
    static auto first(Tuple* f_)
    {
        return std::get<T_>((*f_).f_.front());
    }
    template <typename T_>
    static auto second(Tuple* f_)
    {
        return std::get<T_>((*f_).f_.back());
    }
    std::list<Pair> f_;
};
template <typename T>
using tuple = Tuple<T>*;

int main()
{
    typedef tuple<std::string> tuple_string;
    auto print_t = [](tuple_string it) {
        std::cout << Tuple<std::string>::first<std::string>(it)
                  << Tuple<std::string>::first<std::string>(
                         Tuple<std::string>::second<tuple_string>(it))
                  << Tuple<std::string>::second<std::string>(
                         Tuple<std::string>::second<tuple_string>(it))
                  << std::endl;
    };

    print_t(Tuple<std::string>("hello ", Tuple<std::string>("world", "!")())());
}

Yes is immutable tuples but a little more complex than the other examples, first i needed of more abstractions and even i still using POINTERS. That's no good.

The main problem i need apply like a functor and evaluates for return the pointer because c++ don't support recursive data types(java supports!!!).

Maybe exist many of ways for solve this but it's yet implies that c++ it's a bad language for represent specific new data :)

Don't agree?: text me : camposferreiratiago@gmail.com

EDIT : [SOLVED?] Luiz Stangarlin solved this with the following code: (the context of type of [X] and [Y] are differents

#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <random>
#include <limits>
#include <string>
#include <iostream>
#include <list>

struct Null {
    enum { isNull = 1 };
};

template<typename X, typename Y>
struct Tuple {
    X _first;
    Y _second;
    Tuple(X x, Y y) : _first(x), _second(y) {}
    auto & first() const {
        return _first;
    }
    auto & second() const {
        return _second;
    }
};

template<typename X>
struct Tuple<X, Null> {
    X _atom;
    Tuple(X x) : _atom(x) {}
    auto & first() const {
        return _atom;
    }
    auto & second() const {
        return Null();
    }
};

template<typename X>
auto tuple(X x) {
    return Tuple<X, Null>(x);
}

template<typename X, typename Y>
auto tuple(X x, Y y) {
    return Tuple<X, Y>(x, y);
}

int main() {
    std::cout << "1" << std::endl;
    auto print_t = [](auto it) {
        std::cout << it.first()
            << it.second().first()
            << it.second().second().first()
            << it.second().second().second()
            << std::endl;
    };
    print_t(tuple("test ", tuple("hello ", tuple("world", "!"))));
    std::cout << "0" << std::endl;
}