Philippe.Dumas@inria.fr


http://algo.inria.fr/dumas/Maple/

Retour en page principale Table des matières Index

Maple V.4 worksheet Maple V.5 worksheet

1 | 2

L'énoncé demande d'employer des tables pour représenter les listes, mais laisse une certaine liberté dans cet emploi. Nous définissons un constructeur List qui va faire passer de la séquence de ses arguments à la table demandée.

> List:=proc()

    local i;

    if nargs=0 then

      table([first=NULL,tail=NULL])

    elif nargs=1 then 

      table([first=args[1],tail=NULL])

    else

      table([first=args[1],tail=List(seq(args[i],i=2..nargs))])

    fi

  end:

On notera que les noms first et tail sont globaux. Testons la procédure sur quelques exemples simples.

> L0:=List();

> L1:=List(x[1]);

> L2:=List(x[1],x[2]);

Une liste Maple comme [a,b,c] a la structure suivante.

Avec la structure que nous venons de définir, la même liste est représentée par l'arbre suivant.

Cet arbre est un peigne et la structure est une liste chaînée.

Pour la suite, il sera utile de disposer d'un type List. Ceci permettra de vérifier la correction des arguments passés aux procédures.

> `type/List`:=proc()

    local ind;

    if not type(args[1],table) then false fi;

    ind:=map(op,{indices(args[1])});

    if  not (ind={first,tail}) then false fi;

    [args[1][tail]]=[] or `type/List`(eval(args[1][tail]))

   end:

> type(L0,List);

> type(L2,List);

1. Traitement sans modification des arguments. Répondons maintenant aux questions posées. Nous commençons par le cas où l'on ne modifie pas les listes passées en argument, car ce cas est moins subtil que l'autre. Pour repérer la séquence vide NULL, nous la mettons entre crochets ce qui nous donne la liste vide (au sens usuel des listes Maple). La procédure first fournit la tête de liste et la procédure tail fournit la queue. On pourrait donner des messages d'erreur plus explicites.

> first:=proc(L::List)

    if [L[first]]=[] then ERROR()

    else L[first]

    fi

  end:

> first(L0);

Error, (in first)

> first(L2);

> tail:=proc(L::List)

    if [L[first]]=[] then ERROR()

    elif [L[tail]]=[]  then table([first=NULL,tail=NULL])

    else eval(args[1][tail])

    fi

  end:

> tail(L0);

Error, (in tail)

> tail(L1);

> tail(L2);

Passons à la procédure append qui concatène deux listes.

> append:=proc(L1::List,L2::List)

    if [L1[first]]=[] then eval(L2)

    else table([first=first(L1),tail=append(tail(L1),L2)])

    fi

  end:

> append(L0,L2);

> append(L2,L2);

Continuons avec cons et endcons qui permettent d'augmenter la liste en plaçant un élément en tête ou en queue.

> cons:=proc(x,L::List)

    if [L[first]]=[] then 

      table([first=x,tail=NULL])

    else

      table([first=x,tail=eval(L)])

    fi

  end:

> cons(x,L0);

> cons(x,L1);

> endcons:=proc(L::List,x)

    if [L[first]]=[] then 

      table([first=x,tail=NULL])

    else

      table([first=first(L),tail=endcons(tail(L),x)])

    fi

  end:

> endcons(L0,x);

> endcons(L1,x);

> endcons(L2,x);

La procédure reverse fournit la liste en ordre inverse.

> reverse:=proc(L::List)

    if [L[first]]=[] then eval(L)

    else endcons(tail(L),first(L))

    fi

  end:

> reverse(L2);

Enfin la procédure rest donne le reste de la liste à partir d'une position donnée.

> rest:=proc(L::List,i::posint)

    if [L[first]]=[] then ERROR()

    elif i=1 then eval(L)

    else rest(tail(L),i-1)

    fi

  end:

> rest(L0,1);

Error, (in rest)

> rest(L1,1);

> rest(L1,2);

Error, (in rest)

> rest(L2,2);

Nous en avons ainsi terminé avec le cas où les procédures ne modifient pas leurs arguments.

2. Traitement avec modification des arguments. Le fait qu'une procédure modifie ses arguments ne semble pas très sain du point de vue de la programmation, puisque l'utilisateur modifie son environnememnt sans s'en rendre compte. Cependant ceci peut être fort utile pour augmenter l'efficacité de la procédure, ce qui peut s'avérer crucial si la procédure est appelée de nombreuses fois. On peut ainsi travailler en place ce qui évite de gaspiller de la mémoire. D'ailleurs cette technique peut être rendue propre ; il suffit que la procédure vue par l'utilisateur ne modifie pas ses arguments mais appelle une procédure auxiliaire non visible qui, elle, modifie ses arguments.

Nous définissons quelques listes test.

> l0:=List():

  l1:=List(a):

  l2:=List(a,b):

  l3:=List(a,b,c):

On pourrait imaginer écrire la procédure append comme suit.

> append:=proc(L1::List,L2::List)

    if [L1[first]]=[] then L1:=eval(L2)

    else 

      L1:=table([first=first(L1),tail=append(tail(L1),L2)])

    fi

  end:

> trace(append):

> append(l1,l2);

{--> enter append, args = l1, l2

{--> enter append, args = table([(tail)=NULL,(first)=NULL]), l2

<-- ERROR in append (now in append) = invalid left hand side in assignment}

<-- ERROR in append (now at top level) = invalid left hand side in assignment}

Error, (in append) invalid left hand side in assignment

Le membre gauche d'une affectation doit être un nom. Ici, à partir du deuxième appel à append, ce membre gauche, qui est le premier argument de append, est une expression qui n'est pas un nom, d'où l'erreur. Nous recommençons donc en fournissant un nom. Bien sûr nous jouons sur le fait qu'une table est évaluée à son nom.

> append:=proc(L1::List,L2::List)

    local LL1;

    if [L1[first]]=[] then L1:=eval(L2)

    else

      LL1:=tail(L1); 

      L1:=table([first=first(L1),tail=append(LL1,L2)])

    fi

  end:

> trace(append):

> append(l1,l2);

{--> enter append, args = l1, l2

{--> enter append, args = LL1, l2

<-- exit append (now in append) = table([(first)=a,(tail)=(table([(first)=b,(tail)=NULL]))])}

<-- exit append (now at top level) = table([(first)=a,(tail)=(table([(first)=a,(tail)=(table([(first)=b,(tail)=NULL]))]))])}

Cette fois-ci, tout fonctionne correctement. Nous avons modifié la liste l1, mais pas la liste l2.

> eval(l1);

> eval(l2);

Pour la procédure cons, on pourrait penser à la version suivante.

> cons:=proc(x,L::List)  # bad

    L[tail]:=eval(L);    # bad

    L[first]:=x;         # bad

    eval(L)              # bad

  end:                   # bad

Cette version est totalement catastrophique. En effet, si l'on repense à la représentation arborescente que nous avons indiquée plus haut, la première affectation a pour effet de donner comme fils de nom tail de la racine la racine elle-même. Autrement dit on a créé un cycle ou encore un arbre infini. L'évaluation produit alors une expression de taille non bornée qui remplit la mémoire et fait mourir le système. Passons à une version moins fatale.

> cons:=proc(x,L::List)

    L:=table([first=x,tail=eval(L)])

  end:

> l3:=List(a,b,c):

> cons(x,l3);

Nous avons modifié la liste passée en second argument.

> eval(l3);

La procédure endcons se traite de la même manière.

> endcons:=proc(L::List,x)

    local LL;

    if [L[first]]=[] then 

      L:=table([first=x,tail=NULL])

    else

      LL:=tail(L);

      L:=table([first=first(L),tail=endcons(LL,x)])

    fi

  end:

> endcons(l2,x);

> eval(l2);

Instruit par l'exprérience, nous continuons sans problème avec reverse et rest.

> reverse:=proc(L::List)

    local LL;

    if [L[first]]=[] then L:=eval(L)

    else

      LL:=tail(L); 

      L:=endcons(LL,first(L))

    fi

  end:

> reverse(l2);

> eval(l2);

> rest:=proc(L::List,i::posint)

    local LL;

    if [L[first]]=[] then ERROR()

    elif i=1 then eval(L)

    else 

      LL:=tail(L);

      L:=rest(LL,i-1)

    fi

  end:

> rest(l2,2);

> eval(l2);

Retour en page principale