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)).

   • Ecrivez les définitions des listes suivantes dans la notation de base, c'est-à-dire avec nil et "|". Affichez-les pour vérifier votre traduction.

        L1=[a]
        L2=[a [b c] d]
        L3=[proc {$} {Browse oui} end proc {$} {Browse non} end]
        L4=[est une liste]
        L5=[[a p]]
     

   • Creez une nouvelle liste en ajoutant ceci en tête de la liste L4.

   • La liste L3 a pour éléments des procédures. Appelez la première procédure (à partir de L3). Vérifiez qu'elle affiche oui.

   • A partir de la liste L2, construisez la liste [[b c] d].

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.

   • Ecrivez une fonction qui prend un argument, et renvoie empty si c'est la liste vide, nonEmpty si c'est une liste non-vide, et other si ce n'est pas une liste.

   • Réécrivez les fonctions Head, Tail, Length et Append (voir exercices précédents) en utilisant le pattern matching.

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.

   • {Take Xs N} renvoie une liste contenant les N premiers éléments de la liste Xs.

        {Browse {Take [r a p h] 2}}     % affiche [r a]
        {Browse {Take [r a p h] 7}}     % affiche [r a p h]
        {Browse {Take [r [a p] h] 2}}   % quel est le resultat?
     

   • {Drop Xs N} renvoie la liste Xs sans ses N premiers éléments.

        {Browse {Drop [r a p h] 2}}     % affiche [p h]
        {Browse {Drop [r a p h] 7}}     % affiche nil
        {Browse {Drop [r [a p] h] 2}}   % quel est le resultat?
     

   • {Interval Xs N M} renvoie la liste des éléments de Xs, du N-ième au M-ième inclus.

        {Browse {Interval [b o r i s s] 3 5}}     % affiche [r i s]
        {Browse {Interval [b o r i s s] 5 3}}     % affiche nil
        {Browse {Interval [b [o r i] s s] 2 3}}   % quel est le resultat?
     

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:

   • Vous pouvez supposer que les deux listes passées en argument ont la même taille.
   • Vous devriez commencer par écrire un additionneur de trois chiffres {AddDigits D1 D2 CI}, qui prend trois chiffres binaires D1, D2 et CI, et renvoie une liste de deux chiffres binaires représentant leur somme. Le bit CI et le premier chiffre du résultat est un chiffre de report. Exemples:

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