Fonctions récursives sur les listes,

Fonctions récursives sur les listes:

Nous appellerons une liste tout tableau javascript, en effet un tableau javascript a une taille qui varie de façon dynamique. Contrairement aux listes Caml qui ne peuvent qu'extraire le premier élément de la liste, nous allons travailler sur le dernier élément du tableau. En effet, retirer le dernier élément (pop)est moins coûteux en calcul que retirer le premier(shift), une des raisons simple est que javascript n'aura pas besoin de renuméroter les éléments après pop() , ce qu'il aurait fait après shift() .

Fonction map :

Pourquoi à chaque fois refaire une boucle for ... puisqu'on est en programmation fonctionnelle il est plus simple de passer par une boucle générique map. On peut donner une première version de map :

function map(liste, fonction){
 var resultat=[] ;
 for(var i = 0 ; i < liste.length; i++){ resultat.push(fonction(liste[i]) );}
 return resultat ;
}
//Calcul des carrés d'une liste;
map([1,3,5],function(x){ return x*x})) // Pour chaque élément (x) de la liste on retourne x*x ;[1,9,25]

On peut également, programmer un map récursif:

 function map(l,f){
    var r=[]
    function aux(l, f){
        if(l.length==0) return r ;
        r.push(f(l.pop()))
        return aux(l,f) 
    }
    return aux(l,f).reverse();
}
map([1,3,5],function(x){ return x*x}) ;

On voit ici que le map n'est pas adapté à la programmation récursive, en effet, l'utilisation du pop impose en fin de récursion un renversement du tableau..De plus pop() consomme la liste donnée en argument.
Nous utiliserons donc la solution itérative, à l'aide d'une boucle for pour la suite.

Intérêt de la fonction map

Map permet d'être beaucoup plus concis:
Initialiser un tableau:

 map(new Array(100), function(){ return 0 ;});
 map(new Array(100),Math.random);

Fonction do_list :

Parfois, et même souvent, il est inutile de retourner un tableau. On n'a besoin que d'appliquer la fonction sur tous les éléments du tableau en utilisant "l'effet de bord" (c'est à dire les conséquences de la fonction et non son type retourné).
Nous proposons alors la fonction do_list :

 function do_list(liste, f){  for(var i=0; i< liste.length; i++) f(liste[i]); }

Utilisation des fonctionnelles map et do_list

Filtrer une liste suivant un prédicat:

map([1,5,9], function(x){ if(x<5) return x ;}); // renvoi [1,undefined,undefined]

var r=[] ;
do_list([1,5,9], function(x){ if(x<5) r.push(x) ;});
r; // renvoi [1]  // Le résultat attendu.

Fonction list_it ou apply ;

Il est habituel d'utiliser des fonctions binaires à deux arguments, par exemple add(1,2) utilise deux arguments. Il est souvent utile d'appliquer successivement à chaque élément d'une liste, la fonction a deux arguments du résultat courant et de l'élément suivant. Par exemple si on désire obtenir la somme d'une liste on part de l'élément neutre (0 pour l'addition) et on ajoute successivement les éléments de cette liste.

// solution récursive :
function list_it(f, l, n){ return l.length===0? n : f(l.pop(),list_it(f,l,n)); }// 

• f est une fonction binaire à deux arguments,
  
• l est la liste à traiter
  
• n est le résultat courant
  

Attention cette solution consomme la liste, ce qui peut être intéressant en terme de gestion de la mémoire. On peut donc proposer une solution itérative à l'aide d'une boucle for:

function apply(f, l, n){
    for(var i=0; i< l.length ; i++){  n= f( l[i], n );  }
    return n;
}

En général le premier élément courant fournit à la fonction est un élément neutre pour la fonction donnée. Par exemple, -Infinity pour la fonction Math.max, 0 pour l'addition ou 1 pour la multiplication.
Programmer le maximum d'une liste à l'aide de list_it :

 list_it(Math.max , [1,3,2,9,3] , -Infinity ); //9,
 list_it(Math.max ,  map(new Array(100), Math.random)  , -Infinity ); // 0.99
//Programmer la somme des éléments d'une liste:
 var sum = function(a,b){ return a+b;} ;
 list_it(sum,[3,5,7], 0) ; // 15
//Programmer une fonction qui filtre une liste suivant un prédicat :
 var r=[] ; 
 list_it(
              function(x,tableau){ if(x<0.1) return tableau.push(x) ;}, // la fonction
              map(new Array(100),Math.random), // le tableau à traiter
              [] // la fonction de départ.
              ) ;

Malheureusement, cela ne fonctionne pas car la valeur retournée par tableau.push est un entier, il s'agit d'un défaut du langage; voici la bonne version:

list_it(
    function(x,tableau){ if(x<0.1) tableau.push(x); return tableau ;},
    map(new Array(100),Math.random),
    []) ; 
//[0.02288494476776548, 0.04436209344039965, 0.08676040302532284, 0.04035038420070758,
// 0.02041697086984784, 0.06553779951155114, 0.0869513935206444]

Programmer une fonction qui teste si un prédicat est juste dans une liste donnée:
Cette fonction recherche si il existe un élément égal à 3 dans le tableau. On utilise en valeur de retour l'élément neutre pour le || c'est à dire false:

list_it(function(a,b){ return a===3||b},[1,3,5],false);  //

Parties d'un ensembles

Programmer une fonction qui renvoie toutes les partie d'un ensemble, cet ensemble étant représenté par une liste:
exemple:
parties(['a','b']);
//[[], ["a"], ["b"], ["a", "b"]]
Réponse:

function parties(l){
    if(l.length===0) return [[]];
    var e= l.pop();
    var p = parties(l);
    var suite=map(p,function(sousliste){ var r= sousliste.slice(); r.push(e); return r}); 
    return p.concat(suite) ;
}
parties([1,3,4]);//[[], [1], [3], [1, 3], [4], [1, 4], [3, 4], [1, 3, 4]]
parties(map(new Array(10),Math.random)).length; //1024 soit deux puissance n, le nombre de parties d'un ensemble 

Nb: notez dans la fonction map les 3 instructions successives: slice: permet d'obtenir une copie de la sous liste passée en argument, en effet elle est passée sous la forme d'une référence (une adresse en mémoire de la liste) et pour l'utiliser sans la modifier il faut d'abord en faire une copie grâce à sousliste.slice.
Par ailleurs, il n'est pas possible de renvoyer r.push(e) en effet, r.push(e) renvoi la nouvelle longueur de liste, toujours le même défaut de conception de javascript.

Programmer une fonction qui renvoi les anagrammes d'une liste :

//Anagrammes d'un mot 
function anag(l){
    if(l.length<=1) return [l] ;
    var c =  l .pop() ; // c est un  élément
    var ll = anag(l) ; // ll est une liste de liste,
    
    var resultat = [];
    for(var i= 0; i < ll.length ;i++){
        inject(ll[i],c, resultat) ;
    }
    return resultat ;

function inject(liste,element, r){
    var nl= liste.length +1 ;
    for(var i=0; i< nl; i++){
        var temp= new Array(nl);
        temp[i]= element;
        for(var j=0; j < liste.length ; j++){
            temp[(i+j+1)% nl] = liste[j];
        }
        r.push(temp);
    }
    return 
}
}    
anag('mot'.split('')); 
map(anag('mot'.split('')), function(l){ return l.join('');});
 
//tom,mto,omt,tmo,otm,mot