Séance 3
Programmation récursive avec des listes

Cette séance poursuit l'utilisation de la récursivité comme technique de programmation. Nous allons l'utiliser sur des listes. N'oubliez pas de spécifier les fonctions que vous écrivez, et d'utiliser des invariants pour garantir leur correction.

Enoncés des exercices

  1. Le minimum syndical. Rappelons qu'une liste est soit la liste vide nil, soit une paire H|T, où H est l'élément de tête et T est la queue, c'est-à-dire la liste des éléments restants. Formellement, cela se définit par la grammaire (notation EBNF)

    <List T> ::= nil | T '|' <List T>

    On utilise aussi la notation [a b c], qui est simplement un raccourci de notation pour la liste a|b|c|nil, qui se lit comme a|(b|(c|nil)).

  2. Décomposition. Ecrivez deux fonctions Head et Tail qui retournent respectivement la tête et la queue de la liste passée en argument.

       {Browse {Head [a b c]}}   % affiche a
       {Browse {Tail [a b c]}}   % affiche [b c]
    

  3. Qui a la plus longue? Construisez la fonction récursive Length, qui renvoie la longueur de la liste passée en argument. La liste vide a une longueur nulle.

       {Browse {Length [r a p h]}}       % affiche 4
       {Browse {Length [[b o r] i s]}}   % affiche 3
       {Browse {Length [[l u i s]]}}     % affiche 1
    
    Votre définition est-elle récursive terminale? Si ce n'est pas le cas, rendez-la récursive terminale à l'aide d'un accumulateur. N'oubliez pas de spécifier l'invariant que vous utilisez.

  4. Concaténer deux listes. Ecrivez une fonction récursive Append, qui prend deux listes en argument et renvoie leur concaténation, c'est-à-dire les deux listes mises bout à bout.

       {Browse {Append [r a] [p h]}}       % affiche [r a p h]
       {Browse {Append [b [o r]] [i s]}}   % affiche [b [o r] i s]
       {Browse {Append nil [l u i s]}      % affiche [l u i s]
    
    Pour vous aider, représentez graphiquement les deux listes du premier exemple, ainsi que le résultat. Y a-t-il des similitudes dans ces représentations ? Pensez également à des cas particuliers : que renvoie {Append nil L} ?

  5. Pattern matching. Le pattern matching permet de comparer une valeur avec un pattern, c'est-à-dire un patron ou une forme. Cette technique permet de décomposer un traitement par cas de façon très concise et lisible. Par exemple, l'instruction

       case L
       of nil then {Browse rien}
       [] H|T then {Browse H} {Browse T}
       end
    
    teste d'abord si L correspond à la liste vide (nil), et affiche rien si c'est le cas. Sinon, elle teste si L est une liste composée d'une tête et d'une queue, et affiche ces parties. Si aucun test ne réussit, et qu'il n'y a pas de clause else (comme dans l'exemple), une erreur est signalée.

  6. Sous-séquences dans des listes. Implémentez les fonctions suivantes. Tâchez de raisonner de manière inductive sur la structure des listes.

  7. Multiplions. Écrivez une fonction MultList telle que {MultList L} renvoie le résultat de la multiplication des éléments de la liste L. Par exemple,

       {Browse {MultList [1 2 3 4]}}   % affiche 24
    

  8. Nombres factoriels. Écrivez une fonction Fact telle que {Fact N} renvoie la liste des N premiers nombres factoriels dans l'ordre croissant. Par exemple,

       {Browse {Fact 4}}   % affiche [1 2 6 24]
    

Exercices supplémentaires

  1. Mettons les listes à plat. Écrivez une fonction Flatten prenant une liste L en paramètre. Les éléments de L peuvent eux-même être des listes, dont les éléments peuvent aussi être des listes, et ainsi de suite. L'appel {Flatten L} renvoie la liste ``aplatie'', c'est-à-dire les éléments de L et des listes contenues dans L qui ne sont pas des listes. Exemple:

       {Browse {Flatten [a [b [c d]] e [[[f]]]]}}   % affiche [a b c d e f]
    

  2. Occurrences d'une sous-liste. Écrivez une fonction FindString telle que {FindString S T} renvoie la liste des occurrences de la succession de caractères S dans le texte T. Chaque occurrence est identifiée par la position de son premier caractère dans T. Par exemple,

       {Browse {FindString [a b a b] [a b a b a b]}}   % affiche [1 3]
       {Browse {FindString [a] [a b a b a b]}}         % affiche [1 3 5]
       {Browse {FindString [c] [a b a b a b]}}         % affiche nil
    

    Conseil: commencez par écrire une fonction Prefix telle que {Prefix L1 L2} renvoie true si L1 est un préfixe de L2, false sinon. Par exemple,

       {Browse {Prefix [1 2 1] [1 2 3 4]}}   % affiche false
       {Browse {Prefix [1 2 3] [1 2 3 4]}}   % affiche true
    

  3. Représentation binaire d'entiers avec des listes. Écrivez une fonction Add telle que {Add B1 B2} renvoie le résultat de l'addition des nombres binaires B1 et B2. Un nombre binaire est représenté par une liste de chiffres binaires (0 ou 1). Le chiffre le plus significatif est le premier élément de la liste. Par exemple,

       {Browse {Add [1 1 0 1 1 0] [0 1 0 1 1 1]}}   % affiche [1 0 0 1 1 0 1]
    

    Quelques remarques:


Luis Quesada et Raphaël Collet - 7 octobre 2005