Re: liste de liste

Ok. Comme je vous l'ai dit, le problème se situe au niveau du type de vos données et des signatures de vos fonctions qui doivent toutes retourner le même type "liste" (que j'ai appellé value dans ma solution). En effet, la beauté de LISP, c'est que tout est une liste ! Ainsi, car,cdr,... prennent une liste et retournent une liste... Ça je pense que vous avez compris.

Donc l'astuce c'est que votre node doit pouvoir contenir soit un entier, soit une autre liste. Et par conséquent, doit posséder un moyen de "typer" la node pour savoir si elle représente une liste ou une valeur immédiate/un entier, ici grâce au champs "tag".

struct node3;
struct value {
 enum {LISTE, ENTIER} tag;
 union { struct node3 * lst; int ival; } val;
};

J'ai utilisé une "union" mais rien ne vous empêche d'utiliser une "struct", sauf que vous gaspillez ce faisant un peu de mémoire car une valeur ne peut pas être à la fois un entier et une liste.

Votre type node devient:

struct node3 {
 struct value car;
 struct node3 * cdr ;
};
typedef struct node3 *value;

Remarquez bien au passage que ma définition de struct node3 contient (embed en anglais) la structure value, et non un pointeur. Cela permet de ne faire qu'une seule allocation pour créer une liste d'un élément (cf. plus bàs).

Le typedef rend les choses un peu confuses: "struct value" et "value" représente des choses différentes. Il pourrait avantagement être renommé en "liste" pour rendre les choses plus claires. Il rend déja les déclarations de fonctions plus lisibles. Néanmoins, dans les appels à sizeof je garde j'utilise toujours le type de base, question de goût.

Bref avec cette représentation la construction de cons devient triviale.

value cons(value head, value tail) {
 if (nil == head)
 return nil; /* FIXME: ERROR */
 value nouveau = calloc(sizeof(struct node3),1);
 if (! nouveau)
 return nil; /* IDEM */
 nouveau->car.tag = LISTE;
 nouveau->car.val.lst = head;
 nouveau->cdr = tail;
 return nouveau;
}

Il vous manque plus qu'un constructeur pour créer un entier. Remarquez qu'un entier est une liste d'un élément de type entier... Remarquez aussi l'utilisation de calloc qui initialise la mémoire à zéro en même temps que de l'allouer.

value entier(int i)
{
 value nouveau = calloc(sizeof(struct node3),1);
 if (! nouveau)
 return nil;
 nouveau->car.tag = ENTIER;
 nouveau->car.val.ival = i;
 nouveau->cdr = nil;
 return nouveau;
}

Chez moi ça compile, je n'ai pas implémenté le reste de votre exercice mais cela devrait être trivial maintenant.

int main()
{
 value l1,l2,l3;
 l1 = cons(entier(42),nil); /* (list 42) */
 l2 = cons(l1,nil); /* (list (list 42)) */
 l3 = cons(entier(22),entier(23)); /* (list 22 23) */
 return 0;
}