Listes et pseudo listes en javascript.

Nous avons vu qu'un tableau en javascript a une longueur variable et qu'il existe des fonctions pour retirer le dernier élément du tableau ( pop) ou le premier élément (unshift). Nous avons choisi d'utiliser plus souvent pop car cette fonction ne fait que diminuer la taille du tableau sans avoir à re-numéroter chaque élément du tableau, comme l'aurait imposé un shift.
On peut donc considérer qu'un tableau se comporte comme une liste....
Mais qu'est-ce qu'une liste ? : C'est une collection d'éléments qui s'empilent les uns dernières les autres et dont ont peut en enlever qu'un seul à la fois. C'est donc une pile, à l'image d'une pile d'assiettes, la dernière assiette empilée, sera la première assiette extraite (Last in, first out ) ou LIFO. L'autre variante de structure de données étant la file d'attente: le premier entré sera le premier sortie (First In, First Out) FIFO .Cette structure pourrait être obtenue à l'aide des fonctions shift/ unshift.

Traitement des listes:

Tester si un élément est présent dans une liste.

// Méthode récursive: 
function exists (liste, e){
 return (liste.length===0)? false: e===liste.pop() ||  exists(liste,e) ;
}
// Attention exists récursive consomme la liste !

Méthode itérative:

function exists (liste, e){
 for(var i=0; i< liste.length; i++) 
  if(liste[i]==e) return true ;
 return false;
}

Une façon élégante est d'utiliser apply (ou list-it du caml ) vu précédemment:

function apply(f, l, n){
    for(var i=0; i< l.length ; i++){  n= f( l[i], n );  }
    return n;
}
// ici on peut alors écrire: 
var exists = function(l,e){
    return apply( function(element, boolean){ return (element===e || boolean)  ; }, l,  false ) ;
};

Union de listes

Comment faire l'union de deux listes ? C'est à dire tous les éléments de deux listes, sans répéter les éléments présents dans l'une et l'autre des deux listes ?

//union [1;2;3;3;4] [2;3;4;5;5]  récursive : 

function union(l1,l2){
     if (l2.length ===0) return l1;
     var e = l2.pop();
     return exists(l1,e) ?  union(l1,l2): union(l1.push(e),l2);
}
union([1,2,3,4], [2,3,4,5,5]);  //[1, 2,  3, 4, 5]

Retrait d'un ou plusieurs éléments d'une liste

Comment retirer un élément d'une liste ?
Méthode récursive:

function retrait(l, e){
    if(l.length == 0) return [];
    var c = l.pop();
    if( e===c)  return l ;
        var lb=retrait(l,e);
        return lb.push(c) && lb; // lb.push(c) renvoie la longueur de la liste, donc on renvoi la liste. 
}
retrait([1,3,4,5],4);

retrait itératif: utilisation de la fonction splice:

function retrait(l,e){
    for(var i=0; i< l.length; i++){
        if(l[i]==e)
            l.splice(i,1);  // retire en position i la longueur l ;
    }
    return l;
}
retrait([1,2,3,4,5],3);//[1, 2, 4, 5]

Idem à l'aide de la fonctionnelle apply :

function retrait(liste, e) {
    return apply( 
        function(element, liste){ 
           return element===e ? liste:(liste.push(element) &&liste) ;
       }
     , liste , [] );
}
retrait([1,3,6,7] , 3) ; // [1,6,7]

Filtrer suivant un prédicat: sélectionner les éléments correspondant à un prédicat dans une liste.

// filtrer selon un prédicat en mode récursif: 
function filtre(pred,l){
  if( l.length ===0) return [];
    var e = l.pop();    
    if( !pred(l.pop()) ) 
        return filtre(pred,l);   
    var suite = filtre(pred,l); // recursion ici
    return suite.push(e) && suite;
}

filtre(function(e){ return e>3 ; },[2,3,4,3,5]) ;

Note sur la syntaxe liste.push(element) && liste .

Normalement liste.push renvoi la longueur de la nouvelle liste, ce qui semble plutôt inutile. D'où cette syntaxe javascript qui
permet de renvoyer la liste après concaténation.