fold compter le nombre de float

Version imprimable

02/01/2011, 11h06
guillaume07

fold compter le nombre de float
tiré tout droit de la doc de boost :
Code:

1 2 3 4 5 6 7 typedef vector<long,float,short,double,float,long,long double> types; typedef fold< types , int_<0> , if_< is_float<_2>,next<_1>,_1 > >::type number_of_floats;
j'ai du mal à comprendre la logique , pourquoi est ce que l'on test le deuxième élément de la liste, pour savoir si il faut prendre next ou _1? ici _1 est le chiffre _1 ou le placeholder ?
02/01/2011, 11h56
Goten
Parce que t'as pas la sémantique de fold regarde :
Code:

1 2 3 4 5 6 7 8 fold(Seq, Prev, BinaryOp) := if Seq is empty then: Prev else: fold(tail(Seq), BinaryOp(Prev, head(Seq)), BinaryOp)
Avec ça tu dois pouvoir trouver à quoi "font référence" _2 et _1 ...

Ah et un petit indice, mpl::next a plusieurs "surcharges", ça marche aussi avec les integral constants... (et ça a la sémantique d'une incrémentation)
02/01/2011, 12h04
Joel F

_2 represente l'element courant de l'iteration du fold, _1 represente l'etat courant.

donc le fold dis Pour chaque element dans la meta-sequence, si l'element courant ets un float j'increment l'etat sinon je le laisse tel quel
02/01/2011, 12h07
Goten

Fallait pas spoil comme ça Joel, j'avais volontairement omis la solution toute faite :p
02/01/2011, 12h20
guillaume07

Merci :)!
02/01/2011, 14h45
Joel F

Citation:

Envoyé par Goten

Fallait pas spoil comme ça Joel, j'avais volontairement omis la solution toute faite :p

c'est les fetes ca doit etre pour ca. Pour penitence j ene repondrais pas a ca prochaine question :o
02/01/2011, 19h40
Alp

Une explication sur le fold en général... : http://www.haskell.org/haskellwiki/Fold
24/04/2011, 09h18
guillaume07

Citation:

Envoyé par Joel F

_2 represente l'element courant de l'iteration du fold, _1 represente l'etat courant.

donc le fold dis Pour chaque element dans la meta-sequence, si l'element courant ets un float j'increment l'etat sinon je le laisse tel quel

- Comment est ce que l'algo arrive à savoir que le premier placeholder (_2) réfère à l'élément courant et que _1 représente l'état courant ?

- Pourquoi est ce is_float<_2> et non is_float<_1> ?

- Qu'est ce qui se passe concrètement si on next ou si on "reste dans l'état courant" ?
24/04/2011, 11h26
Goten

Citation:

Envoyé par guillaume07

- Comment est ce que l'algo arrive à savoir que le premier placeholder (_2) réfère à l'élément courant et que _1 représente l'état courant ?

C'est fold qui dicte ça justement donc il le sait parce ... c'est fait comme ça :'.

Citation:

Envoyé par guillaume07

- Pourquoi est ce is_float<_2> et non is_float<_1> ?

Bah parce que ton test tu le fais sur l'élément courant pas sur un état. Ce que tu veux tester c'est chaque élément du vector!

Citation:

- Qu'est ce qui se passe concrètement si on next ou si on "reste dans l'état courant" ?

hum? bah si tu "next" ça fait incrémente l'integral constant. Et si tu "restes dans l'état courant" bah y'a pas d'incrémentation c'est tout.
24/04/2011, 12h31
guillaume07

"Bah parce que ton test tu le fais sur l'élément courant pas sur un état"

ok donc next<_1> = next de l'état courant =

- +1 sur l'integral constante
- fait pointer _2 sur le prochain élément de la séquence

?

Autrement pour info , le piège pour quelqu'un qui découvre cet algo , c'est de penser que is_float<_2> pointe sur le 2eme élément du vecteur, et que _1 sur le premier élément...
24/04/2011, 16h21
Goten

Citation:

Envoyé par guillaume07

ok donc next<_1> = next de l'état courant =

- +1 sur l'integral constante
- fait pointer _2 sur le prochain élément de la séquence

Non, next ne fait _que_ incrémenter l'integral constant. (c'est le nom "next" qui te plante à mon avis). C'est fold en interne qui "avance".
24/04/2011, 18h25
Flob90

Le lien de Alp explique assez bien l'idée du fold je trouve (comparaison entre fold et le constructeur :: des listes).

L'idée et d'appliquer succesivement la méta-fonction sur chaque élément de la séquence et l'accumulateur (l'état).

Après avoir essayé, je trouve que Haskell (et surment d'autre langage fonctionnel pure) peut aider à comprendre le fonctionnement de la méta-prog.

Le piège que tu cites n'existe pas :
- fold applique la méta-fonction comme indiquer dans la doc
- la méta-fonction est ici écrit avec des placeholders, rien de plus
24/04/2011, 18h33
guillaume07

ok merci pour les réponses
25/04/2011, 19h48
Alp

Citation:

Envoyé par Flob90

Après avoir essayé, je trouve que Haskell (et surment d'autre langage fonctionnel pure) peut aider à comprendre le fonctionnement de la méta-prog.

Certainement! Pourquoi ? Tout simplement parce que derrière c'est exactement la même chose. La méta-progr c'est de la programmation fonctionnelle justement, mais à la compilation. (oui Goten tu vas dire que je rabache)

Tu peux regarder ce genre de trucs un peu ésotériques : http://alpmestan.wordpress.com/2009/...pe-lists-in-c/ :aie:

Un post intéressant sur le sujet : http://bartoszmilewski.wordpress.com...-to-do-with-c/
25/04/2011, 21h38
Flob90

Citation:

Certainement! Pourquoi ?

Oui, fondamentalement la méta-prog c'est de la programmation fonctionnelle pure. Mais je pense que le fait qu'Haskell soit fait pour ca dés le départ (contrairement aux templates) et que ca se passe au runtime, ca permet de mieux appréhender les mécanismes (ou plutôt que ca peut aider ceux qui ont du mal)

Je n'ai pas encore pris le temps de lire les articles de ton blog (hors "anciens" articles parus sur dvlp), je le ferais quand j'aurais plus de temps (j'ai le Vandevoorde et le livre de David Abrahams à lire avant).

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
#include <iostream>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/string.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/front.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/mpl/push_back.hpp>
 
using namespace boost;
 
typedef boost::mpl::vector<
   boost::mpl::string<'a','b'>,
   boost::mpl::string<'c','d'>,
   boost::mpl::string<'e','f'>
> slist;
 
 
typedef boost::mpl::reverse_fold<
   slist,
   mpl::string<>,
   boost::mpl::copy<mpl::_1, mpl::back_inserter<mpl::_2> >
>::type string;
 
int main() {
   std::cout << boost::mpl::c_str<string>::value << std::endl;
}

Quand je vois ce code, le _1 et _2 n'ont pas l'air d'être 'réservé' soit pour l'état soit pour l'accumulateur, comme c'était le cas pour l'exemple en début de post.
je suis un peu perdu...j'ai l'impression que parfois ça accumule... et parfois non :)

26/04/2011, 00h55
Alp

_1 et _2 ne sont pas magiques, ils sont déclarés puis utilisés par boost.mpl elle même. Ce sont des "placeholders", c'est à dire qu'ils vont garder les places des arguments bien au chaud en attendant qu'ils arrivent.

De manière générale, _1 désigne le premier argument de ta meta fonction, _2 le deuxième, et ainsi de suite. C'est le même principe qu'avec boost::bind (qui a aussi des _1, _2 etc), sauf que là c'est avec des fonctions "compile time", c'est à dire des meta-fonctions.

@Flob90: oui c'est sûr, mais personnellement j'ai fait le chemin inverse (:aie:), donc je ne saurais dire. Mais le Haskell me permet d'appréhender les codes de métaprogr C++ les plus compliqués bien plus sereinement, ç'a encore plus éclairci ma vision des choses.

Code:

1 2 3 4 5 6 7 typedef vector<long,float,short,double,float,long,long double> types; typedef fold< types , int_<0> , if_< is_float<_2>,next<_1>,_1 > >::type number_of_floats;
_2 sera remplacé par long,float,short,double... et ainsi de suite.

_1 sert à gérer le compteur de l'accu (si j'ai bien compris) et sera remplacé par finalement je ne sais pas quelle variable mais en tout cas ne prendra pas les différents types définis dans la séquence types

Tant dis qu'avec cet exemple :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 typedef boost::mpl::vector< boost::mpl::string<'a','b'>, boost::mpl::string<'c','d'>, boost::mpl::string<'e','f'> > slist; typedef boost::mpl::reverse_fold< slist, mpl::string<>, boost::mpl::copy<mpl::_1, mpl::back_inserter<mpl::_2> > >::type string; int main() { std::cout << boost::mpl::c_str<string>::value << std::endl; }
_1 prendra les différentes valeurs de la séquence slist
_2 désigne la séquence final (je devine)

Au final ce qui me parait surprenant c'est d'obtenir une telle génércité les deux algos sont radicalement différents, quelle est la 'magie' si chose dire ici, comment peut-on avoir une meta-fonction if_ dans le premier cas qui sait qu'il faut utiliser _1 comme variable d'accumulation et même chose comment mpl::copy sait qu'il faut utiliser _2 comme séquence 'final' ?

Edit:concernant les placeHolder, je suis ok avec leur définition à savoir
Code:

1 2 3 4 5 6 7 8 9 10 11 12 template< int n > struct arg; typedef arg<1> _1 template<> struct arg<1> { template<class A1> struct apply { typedef A1 type; } }; arg<1>::apply<int>::type <=> int

26/04/2011, 21h51
Flob90

Dans fold et reverse_fold, _1 est l'accumulateur et _2 est l'itérateur déréférencer sur les élément de la séquence. Pour fold c'est dans l'ordre et pour reverse_fold dans l'ordre inverse.

Je pense que le premier cas tu as compris il me semble, pour le second :
- copy insert la séquence grace au back_inserter

1° passage : l'accumulateur est vide, back_inserter est sur la séquence "e,f", on insert donc la séquence vide à la fin de la séquence "e,f" et ca devient le nouvel accumulateur
2° passage : l'accumulateur est la séquence "e,f", back_inserter est sur la séquence "c,d", on insert donc la séquence "e,f" à la fin de la séquence "c,d" et ca devient le nouvel accumulateur
3° passage : l'accumulateur est la séquence "c,d,e,f", back_insert est sur la séquence "a,b", on inser donc la séquence "c,d,e,f" à la fin de la séquence "a,b" et ca devient le nouvel accumulateur

Fin : Il n'y a plus rien dans la séquence, le dernier accumulateur est le résultat, ie le résultat est "a,b,c,d,e,f"

Essaie de lire la doc et de comprendre comment s'empile et se dépile les instancation template, il faut reconnaitre que c'est pas simple, si tu peux fais un petit passage sur un langage de programmation fonctionnel pure, du genre Haskell, ca peut t'aider à comprendre.

@Apl: J'ai aussi découvert la méta-prog C++ avant Haskell, mais il (Haskell) m'a quand même permis de bien comprendre certains mécanismes.
26/04/2011, 22h51
guillaume07

Très bien merci pour les conseils et explications.

encore un doute que j'aimerais éclaircir avant d'être lâcher dans la nature :)

dans le premier exemple _1 sert à l'accumulateur, _2 à itérer sur la séquence
dans le deuxième exemple _1 sert à itérer, _2 à accumuler

c'est assez déroutant...

edit: ok je viens d'intervertir les deux placeholder le résultat est identique...why not
26/04/2011, 23h28
Flob90

Non, relis mon message, pour fold et reverse_fold, _1 est toujours l'accumulateur (ou l'état c'est pareil) et _2 l'élément courrant.

Non, si tu inverses la sortie est "e,f,c,d,a,b" et pas "a,b,c,d,e,f" essaies de faire les différentes étapes à la main comme je l'ai fait dans mon message précédent pour bien voir.

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 struct My { template<typename T,typename U> struct apply { typedef typename if_< is_float<U>, typename boost::mpl::next<T>::type, T >::type type; }; }; typedef fold< types, int_<0>, My//if_< is_float<_2>,next<_1>,_1 > >::type number_of_floats;
ça permet un peu mieux de comprendre en définissant soit meme la meta class je trouve.

On ne peut pas changer l'ordre de T et U. Je comprends donc que fold à un "protocole" qu'on se doit de respecter

26/04/2011, 23h47
guillaume07

Citation:

Envoyé par Flob90

Non, relis mon message, pour fold et reverse_fold, _1 est toujours l'accumulateur (ou l'état c'est pareil) et _2 l'élément courrant.

Non, si tu inverses la sortie est "e,f,c,d,a,b" et pas "a,b,c,d,e,f" essaies de faire les différentes étapes à la main comme je l'ai fait dans mon message précédent pour bien voir.

oui désolé car j'ai inversé et en meme temps changé en fold et non reverse_fold