J'appellerais cet idiome tuple-continuateur ou plus généralement, monadique-continuateur . Il s'agit sans aucun doute d'une instance d'un monade de continuation. Une excellente introduction aux monades de continuation pour les programmeurs C++ est la suivante aquí . En substance, le list lambda ci-dessus prend une valeur (un paquet de paramètres variadiques) et renvoie un simple 'continuateur' (la fermeture interne). Ce continuateur, lorsqu'on lui donne un appelable (appelé access ), y passe le paquet de paramètres et renvoie ce que cet appelant renvoie.
En s'inspirant du blogue de FPComplete, un continuateur ressemble plus ou moins à ce qui suit.
template<class R, class A>
struct Continuator {
virtual ~Continuator() {}
virtual R andThen(function<R(A)> access) = 0;
};
El Continuator ci-dessus est abstrait - il ne fournit pas d'implémentation. En voici donc une simple.
template<class R, class A>
struct SimpleContinuator : Continuator<R, A> {
SimpleContinuator (A x) : _x(x) {}
R andThen(function<R(A)> access) {
return access(_x);
}
A _x;
};
El SimpleContinuator accepte une valeur de type A et le transmet à access cuando andThen est appelé. Le site list lambda ci-dessus est essentiellement le même. Elle est plus générale. Au lieu d'une valeur unique, la fermeture interne capture un paquet de paramètres et le transmet à la fonction access fonction. Super !
J'espère que cela explique ce que signifie être un continuateur. Mais que signifie être une monade ? Voici un bon exemple introduction en utilisant des images.
Je pense que le list lambda est également un monade de liste, qui est implémenté comme un monade de continuation. Notez que la monade de continuation est la mère de toutes les monades . En d'autres termes, vous pouvez implémenter n'importe quelle monade avec une monade de continuation. Bien sûr, le monad de liste n'est pas hors de portée.
Comme un paquet de paramètres est tout naturellement une "liste" (souvent de types hétérogènes), il est logique qu'il fonctionne comme une monade liste/séquence. Le site list lambda ci-dessus est un moyen très intéressant de convertir les paquets de paramètres C++ en une structure monadique. Ainsi, les opérations peuvent être enchaînées les unes après les autres.
El length Le lambda ci-dessus, cependant, est un peu décevant car il brise la monade et le lambda imbriqué à l'intérieur renvoie simplement un entier. Il y a sans doute une meilleure façon d'écrire le "getter" de la longueur comme indiqué ci-dessous.
----Functeur----
Avant de pouvoir dire que le lambda list est une monade, nous devons montrer que c'est un foncteur. C'est-à-dire que fmap doit être écrit pour list.
La liste lambda ci-dessus sert de créateur du foncteur à partir d'un paquet de paramètres ----essentiellement, elle sert d'outil de création d'une liste. return . Le foncteur ainsi créé garde le paquet de paramètres avec lui (capture) et permet d'y "accéder" à condition de fournir un appelable qui accepte un nombre variable d'arguments. Notez que le callable est appelé EXACTEMENT UNE FOIS.
Écrivons fmap pour un tel foncteur.
auto fmap = [](auto func) {
return [=](auto ...z) { return list(func(z)...); };
};
Le type du func doit être (a -> b). C'est-à-dire, en langage C++,
template <class a, class b>
b func(a);
Le type de fmap est fmap: (a -> b) -> list[a] -> list[b] C'est-à-dire, en langage C++,
template <class a, class b, class Func>
list<b> fmap(Func, list<a>);
C'est-à-dire que fmap fait simplement correspondre une liste de-a à une liste de-b.
Maintenant, vous pouvez faire
auto twice = [](auto i) { return 2*i; };
auto print = [](auto i) { std::cout << i << " "; return i;};
list(1, 2, 3, 4)
(fmap(twice))
(fmap(print)); // prints 2 4 6 8 on clang (g++ in reverse)
Par conséquent, il s'agit d'un foncteur.
----Monad----
Maintenant, essayons d'écrire un flatmap (alias bind , selectmany )
Le type de carte plate est flatmap: (a -> list[b]) -> list[a] -> list[b].
C'est-à-dire qu'étant donné une fonction qui fait correspondre a à une liste-de-b et une liste-de-a, flatmap renvoie une liste-de-b. Essentiellement, elle prend chaque élément de la liste-de-a, appelle func dessus, reçoit la liste-de-b (potentiellement vide) un par un, puis concatène toutes les listes-de-b, et enfin renvoie la liste-de-b finale.
Voici une implémentation de flatmap pour la liste.
auto concat = [](auto l1, auto l2) {
auto access1 = [=](auto... p) {
auto access2 = [=](auto... q) {
return list(p..., q...);
};
return l2(access2);
};
return l1(access1);
};
template <class Func>
auto flatten(Func)
{
return list();
}
template <class Func, class A>
auto flatten(Func f, A a)
{
return f(a);
}
template <class Func, class A, class... B>
auto flatten(Func f, A a, B... b)
{
return concat(f(a), flatten(f, b...));
}
auto flatmap = [](auto func) {
return [func](auto... a) { return flatten(func, a...); };
};
Maintenant, vous pouvez faire beaucoup de choses puissantes avec une liste. Par exemple,
auto pair = [](auto i) { return list(-i, i); };
auto count = [](auto... a) { return list(sizeof...(a)); };
list(10, 20, 30)
(flatmap(pair))
(count)
(fmap(print)); // prints 6.
La fonction count est une opération de préservation de la monade car elle renvoie une liste à élément unique. Si vous voulez vraiment obtenir la longueur (non enveloppée dans une liste), vous devez terminer la chaîne monadique et obtenir la valeur comme suit.
auto len = [](auto ...z) { return sizeof...(z); };
std::cout << list(10, 20, 30)
(flatmap(pair))
(len);
S'il est bien fait, le pipeline de collecte (par exemple, filter , reduce ) peut désormais être appliqué aux packs de paramètres C++. Super !
----Les lois des monades----
Assurons-nous que le list La monade satisfait les trois lois des monades .
auto to_vector = [](auto... a) { return std::vector<int> { a... }; };
auto M = list(11);
std::cout << "Monad law (left identity)\n";
assert(M(flatmap(pair))(to_vector) == pair(11)(to_vector));
std::cout << "Monad law (right identity)\n";
assert(M(flatmap(list))(to_vector) == M(to_vector));
std::cout << "Monad law (associativity)\n";
assert(M(flatmap(pair))(flatmap(pair))(to_vector) ==
M(flatmap([=](auto x) { return pair(x)(flatmap(pair)); }))(to_vector));
Toutes les assertions sont satisfaites.
----Collection Pipeline----
Bien que le lambda 'list' ci-dessus soit manifestement un monade et partage les caractéristiques du proverbial 'list-monad', il est assez désagréable. En particulier, parce que le comportement des pipeline de collecte combinateurs, tels que filter (alias where ) ne répond pas aux attentes communes.
La raison en est simplement le fonctionnement des lambdas C++. Chaque expression lambda produit un objet fonction d'un type unique. Par conséquent, list(1,2,3) produit un type qui n'a rien à voir avec list(1) et une liste vide, qui dans ce cas serait list() .
La mise en œuvre simple de where échoue à la compilation car en C++ une fonction ne peut pas retourner deux types différents.
auto where_broken = [](auto func) {
return flatmap([func](auto i) {
return func(i)? list(i) : list(); // broken :-(
});
};
Dans l'implémentation ci-dessus, func renvoie un booléen. C'est un prédicat qui dit vrai ou faux pour chaque élément. L'opérateur ? : ne compile pas.
On peut donc utiliser une autre astuce pour permettre la poursuite de la filière de collecte. Au lieu de filtrer réellement les éléments, ils sont simplement signalés comme tels - et c'est ce qui rend la situation désagréable.
auto where_unpleasant = [](auto func) {
return [=](auto... i) {
return list(std::make_pair(func(i), i)...);
};
};
El where_unpleasant fait le travail, mais de façon désagréable...
Par exemple, voici comment vous pouvez filtrer les éléments négatifs.
auto positive = [](auto i) { return i >= 0; };
auto pair_print = [](auto pair) {
if(pair.first)
std::cout << pair.second << " ";
return pair;
};
list(10, 20)
(flatmap(pair))
(where_unpleasant(positive))
(fmap(pair_print)); // prints 10 and 20 in some order
----Tuples hétérogènes----
Jusqu'à présent, la discussion a porté sur les tuples homogènes. Maintenant, généralisons-la aux vrais tuples. Cependant, fmap , flatmap , where ne prennent qu'un seul callback lambda. Pour fournir plusieurs lambdas travaillant chacun sur un type, nous pouvons les surcharger. Par exemple,
template <class A, class... B>
struct overload : overload<A>, overload<B...> {
overload(A a, B... b)
: overload<A>(a), overload<B...>(b...)
{}
using overload<A>::operator ();
using overload<B...>::operator ();
};
template <class A>
struct overload<A> : A{
overload(A a)
: A(a) {}
using A::operator();
};
template <class... F>
auto make_overload(F... f) {
return overload<F...>(f...);
}
auto test =
make_overload([](int i) { std::cout << "int = " << i << std::endl; },
[](double d) { std::cout << "double = " << d << std::endl; });
test(10); // int
test(9.99); // double
Utilisons la technique du lambda surchargé pour traiter un continuateur de tuple hétérogène.
auto int_or_string =
make_overload([](int i) { return 5*i; },
[](std::string s) { return s+s; });
list(10, "20")
(fmap(int_or_string))
(fmap(print)); // prints 2020 and 50 in some order
Enfin, Exemple en direct
