Instantly share code, notes, and snippets.

# caotic123/pair_.md

Last active June 28, 2023 08:49
Show Gist options
• Save caotic123/193b635b27c46b129fdbb20ea360cfc4 to your computer and use it in GitHub Desktop.
C++ : A functional analysis of immutable pair construction

# 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;
}```