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

Fonctions en javascript

Particularité des Fonctions:

Les fonctions sont des éléments de "première classe", une fonction est un type comme un autre, on peut donc l'échanger à l'aide de son nom ou la retourner.
Pour l'exécuter il faudra utiliser l'opérateur double parenthèse ( ) avec éventuellement des arguments à l'intérieur, on peut ainsi écrire:

var hello = function(){ return "hello";} 
div.onclick = hello ; 

Ainsi la fonction hello sera exécutée seulement lors du clic de la souris sur l'élément div. Mais la variable hello, du type fonction, peut être manipulée comme toute autre variable. En fait ici on assigne à la variable "hello" une fonction anonyme .
Attention, le mot clé var permet de désigner la portée de la variable déclarée, ainsi si hello est déclarée à l'intérieur d'une autre fonction, elle ne sera pas accessible hors de cette fonction, d'où l'intérêt de cette notation. Si var est omis, alors la portée devient globale même à l'intérieur d'une fonction. Si vous scriptez une page web, le contexte global correspond à l'objet window.
On peut également écrire les fonctions façon java:

function hello(){ return "hello" ;} // comme en java ou php

L'inconvénient ici c'est que la fonction risque d'être écrite dans un contexte global, ce qui doit être banni car il y a risque de collision avec d'autres variables importées par d'autres scripts.
Il existe en outre une façon spéciale de construire une fonction en utilisant le mot clé Function et du constructeur "new" :

var add = new Function("x", "y", "return x+y") ;
add('Hello ', 'World' );// "Hello World"

Dans cette dernière syntaxe, le dernier argument de "Function " est le type retourné. Une des utilisation possible de Function est de décoder des objets transmis suivant la notation JSON par exemple:

var monobjet = "{ langage: 'java' , annee: 1995} " ;// un objet javascript au format JSON.
var obj = Function( "return "+ monobjet)() ;// remarquez l'exécution à l'aide de () ;
obj.annee; //1995

On peut également créer une fonction anonyme et l'exécuter immédiatement à l'aide de l'opérateur () ce qui permet à l'interpréteur javascript de ne pas la garder en mémoire :

(function(){ return "hello world";})() // la fonction est anonyme, elle est exécutée immédiatement.

Une dernière variante consiste à nommer une fonction anonyme qui devient moins anonyme mais ce qui permet de l'appeler récursivement :

(function facto (n){    if (n == 1) return 1 ;
else return n* facto(n-1) ;})(5) ; // 5*4*3*2*1= 120 

Valeur retournée par une fonction le mot clé "return " :

Si le mot clé "return" est oublié la fonction retourne par défaut : "undefined".
Par ailleurs il existe des erreurs de conception du langage, ainsi on peut écrire:

if( a==2) return true ; else return false ; //correct

ou

return (a==2)? true : false ; //équivalent

mais pas:

(a==2)? return true: return false; // erreur

ni

(return a==2 || return false) ; // erreur écrire: return (a==2 || 'false' )

En effet l'instruction "return ..." n'est pas évaluée ce qui empêche ce genre d'idiome très utilisé en Perl.

Séparateur de ligne le point-virgule facultatif ; :

Il faut également faire attention au caractère facultatif du point virgule, javascript remplace un retour à la ligne par un point virgule, dans ce cas:

return
true

retourne "undefined" car il est interprété comme return; true ;

Arguments des fonctions, methodes apply et call :

Lors de la définition des fonctions, il est habituel de désigner les arguments de fonctions dans la double parenthèse, or il faut savoir que ces arguments sont facultatifs et qu'ils sont repris par javascript dans un tableau spécial toujours disponible nommé arguments,

function somme(){
var resultat=0 ;
for(var i=0; iresultat += arguments[i] ;
return resultat ;
}
somme(1,3,4); // 8

Attention! Ce tableau arguments, par erreur de conception du langage n'est pas un vrai tableau et il sera parfois nécessaire de le transformer en véritable tableau, en le dupliquant et en utilisant la méthode nouveauTableau = Array.slice(arguments) ;

Apply et call :

On peut parfois appeler une fonction par apply ou call de cette façon:

somme.apply(this, [1,3,4]);
var maximum = Math.max.apply(this,[5,3,10,5]);
var monTableau = [1,4,42,10,7] ;
var maximum = Math.max.apply(null,monTableau);
maximum ; //42

• le premier argument de correspond à l'objet sur lequel est appelé la fonction.
  
• le second argument est un tableau.

On peut également utiliser call, on écrit alors:

somme.call(this, 1,3,4) ; // identique à somme(1,3,4)

Nous avons donc vu ici plusieurs méthodes pour créer une fonction dans un contexte différent des objets .
Le problème du mot clé "return" qui peut être omis.
La variable cachée arguments et les méthodes "apply et call" pour utiliser un nombre indéfini d'arguments.
On voit donc que l'écriture classique des fonctions javascript façon java est le résultat d'un
camouflage de variable et de méthodes.