liste.c

#include <stdlib.h>
#include <stdio.h>

/************************** Question 1 *****************************/
typedef struct s_maillon *p_maillon_t;
typedef p_maillon_t       liste_t;
typedef liste_t          *p_liste_t;

/************************** Question 2 *****************************/
/******* A la C ***********/
/*  typedef struct s_maillon */
/*  { */
/*    int valeur; */
/*    p_maillon_t suivant; */
/*  } maillon_t; */

/******* A la LISP ***********/
typedef struct s_maillon
{
  int valeur;
  liste_t suivant;
} maillon_t;

/*  typedef struct s_maillon */
/*  { */
/*    int valeur; */
/*    liste_t suivant; */
/*  } maillon_t; */

/************************** Question 3 *****************************/
/******* Liste vide ***********/
liste_t nil()
{
  return NULL;
}

/******* Constructeur ***********/
liste_t cons(int val, liste_t liste)
{
  liste_t tete = malloc(sizeof(maillon_t));

  tete->valeur = val;
  tete->suivant = liste;
  return tete;
}

/************************** Question 4 *****************************/
/******* fonction car ou head ***********/
int car(liste_t liste)
{
  if(liste == nil()) {
    printf("Le car d'une liste vide, c'est pas terrible !!\n");
    exit(1);
  }
  return liste->valeur;
}

/******* fonction cdr ou tail ***********/
liste_t cdr(liste_t liste)
{
  if(liste == nil()) {
    printf("Le cdr d'une liste vide... disons vide par convention !\n");
    return(nil());
  }
  return liste->suivant;
}

/******* copie d'une liste *************/
liste_t copie(liste_t liste)
{
  if(liste==(nil())) {
    return (nil());
  } else {
    return (cons(car(liste),copie(cdr(liste))));
  }
}

/************************** Question 5 *****************************/
/******* concatenation ***********/
/* concat([a_1, a_2, ... , a_n],[b_1, b_2, ... , b_p]) ->
       [a_1, a_2, ... , a_n, b_1, b_2, ... , b_p]       */

/*** Version itérative paresseuse ***/
/*** on crée juste un lien entre le dernier élément de fst et
     le premier élément de snd ***/
liste_t iter_lazy_concat(liste_t fst, liste_t snd)
{
  liste_t current=fst;
   
  if(fst==NULL) {
    return snd;
  } else {
    while(current->suivant!=NULL) current=current->suivant;
    current->suivant=snd;
    return fst;
  }
}

/*** Version récursive paresseuse ***/
/*** on peut mieux faire ... c'est bizarrement écrit ***/
liste_t recur_lazy_concat(liste_t fst, liste_t snd)
{
  liste_t current;
  
  if(fst==NULL) {
    return snd;
  } else {
    current=recur_lazy_concat(fst->suivant, snd);
    fst->suivant=current;
    return fst;
  }
}

/* Cette fonction modifiant la liste initiale et partageant des données
   avec la seconde, il peut être plus prudent d'utiliser 
   concat(copie(fst), copie(snd)) */

/*** Version récursive vraiment plus safe ... ***/
liste_t concat(liste_t fst, liste_t snd)
{
  if(fst==NULL) {
    return copie(snd);
  } else {
    return cons(car(fst),concat(cdr(fst),snd));
  }
}

/******* reverse  ***********/
/* reverse([a_1, a_2, ... , a_n]) ->
       [a_n, ... , a_2, a_1]                  */

/* mais ici on retourne litéralement la première liste...
   elle est modifiée... */
/*** Version itérative ***/
liste_t iter_reverse(liste_t liste)
{
  liste_t current=liste, next, renversee=nil();
  
  if(liste!=NULL) {
    while(current->suivant!=NULL) {
      next=current->suivant;
      current->suivant=renversee;
      renversee=current;
      current=next;
    }
    current->suivant=renversee;
    renversee=current;
  }
  return renversee;
}

/* si on ne veut pas la modifier, il vaut mieux faire comme ça... */
/*** Version récursive lente ***/
liste_t slow_reverse(liste_t liste)
{
  if(liste!=NULL) {
    int val = car(liste);
    liste_t queue = cdr(liste);

    return concat(slow_reverse(queue),cons(val,nil()));
  } else return nil();
}

/*** ou mieux !!! ***/
/*** Version récursive plus rapide ***/
liste_t aux_reverse(liste_t liste, liste_t renversee)
{
  if(liste==NULL) return renversee;
  else return(aux_reverse(cdr(liste),cons(car(liste),renversee)));
}

liste_t reverse(liste_t liste)
{
  return aux_reverse(liste,nil());
}

/************************** Question 6 *****************************/
/******* fonction map ***********/
/* concat(f,[a_1, a_2, ... , a_n]) ->   
   f(a_1); f(a_2); ... ; f(a_n);
 */
/*** Version itérative ***/
void iter_map(void f(int), liste_t liste)
{
  liste_t current=liste;
  if(current) {
    while(current->suivant!=NULL) {
      f(current->valeur);
      current=current->suivant;
    }
    f(current->valeur);
  }
}

/*** Version récursive ***/
void map(void f(int), liste_t liste)
{
  if(liste) {
    f(liste->valeur);
    map(f, liste->suivant);
  }
}

/******* fonction apply ***********/
/* concat(f,[a_1, a_2, ... , a_n]) ->   
   [f(a_1), f(a_2), ... , f(a_n)]
 */
/*** Version itérative ***/
liste_t iter_apply(int f(int), liste_t liste)
{
  liste_t prev,current;
  liste_t new_prev,new_current,new_liste;
  if(liste) {
    current=liste;
    new_current=new_liste=cons(f(current->valeur),nil());
    while(current->suivant!=NULL) {
      prev=current;
      new_prev=new_current;
      current=current->suivant;
      new_current=cons(f(current->valeur),nil());
      new_prev->suivant=new_current;
    }
  } else {
    new_liste = nil();
  }
  return new_liste;
}

/*** Version récursive ***/
liste_t apply(int f(int), liste_t liste)
{
  if(liste) {
    return(cons(f(car(liste)), apply(f,cdr(liste))));
  } else return nil();
}

/******* fonction reduce ***********/
/* reduce(op,e,[a_1, a_2, ... , a_n]) ->   
   ((...((e op a_1) op a_2) op ... ) op a_n)
 */
/*** Version itérative ***/
int iter_reduce(int op(int,int), int init,liste_t liste)
{
  liste_t current=liste;
  int accu=init;
  if(current) {
    while(current->suivant!=NULL) {
      accu=op(accu,current->valeur);
      current=current->suivant;
    }
    accu=op(accu,current->valeur);
  }
  return accu;
}

/*** Version récursive ***/
int reduce(int op(int,int), int init,liste_t liste)
{
  if(liste) {
    return(reduce(op, op(init,car(liste)), cdr(liste)));
  } else return init;
}

void print_int(int valeur)
{
  printf("%d\n",valeur);
}

void print_separateur()
{
  printf("****\n");
}

int carre(int valeur)
{
  return(valeur*valeur);
}

int plus(int x, int y)
{
  return(x+y);
}

int main()
{
  liste_t first = cons(1, cons(2, cons(3, nil())));
  liste_t second= cons(4, cons(5, nil()));
  liste_t concatenee = nil();
  liste_t first_carre = apply(carre, first);
  liste_t second_carre = apply(carre, second);
  liste_t concatenee_carre = apply(carre, concatenee);

  map(print_int, first);print_separateur();
  map(print_int, second);print_separateur();
  map(print_int, concatenee);print_separateur();
  map(print_int, first_carre);print_separateur();
  map(print_int, second_carre);print_separateur();
  map(print_int, concatenee_carre);print_separateur();
  concatenee = concat (first,second);

  map(print_int, first);print_separateur();
  map(print_int, second);print_separateur();
  map(print_int, concatenee);print_separateur();
  map(print_int, first_carre);print_separateur();
  map(print_int, second_carre);print_separateur();
  map(print_int, concatenee_carre);print_separateur();
  concatenee_carre = apply(carre, concatenee);
  map(print_int, concatenee_carre);print_separateur();
  print_int(reduce(plus, 0, concatenee_carre));print_separateur();
  map(print_int, reverse(cons(1,cons(2,cons(3,nil())))));print_separateur();
  map(print_int, reverse(cons(2,cons(3,nil()))));print_separateur();
  map(print_int, reverse(cons(2,nil())));print_separateur();
  map(print_int, reverse(nil()));print_separateur();
  return 0;
}