Introduction

On peut définir des fonctions récursives, on peut aussi définir des structures de données récursives ! Le premier tel exemple est la liste. Nous verrons ensuite les arbres.

La liste est l’équivalent récursif des tableaux. Une liste peut être vide. Ou bien être constituée d’un élément (la tête) et d’une liste des éléments suivants (la queue).

On peut imaginer une liste comme un serpent : si on lui coupe la tête, il reste la queue. Et la queue est elle-même un serpent.

Représentation graphique sur le blog de Philip Wadler

Contraintes

Nous allons utiliser le type liste standard de Haskell

l = [7, 3, 5, 12]

maliste = 9:l

Les listes sont soit la liste vide [] soit une liste composée d’une tête (t) et d’une queue (q) : t:q.

On pourra utiliser une garde (équivalent d’un if) dans un pattern matching :

monmax x y
  | x < y = y
  | otherwise = x

que l’on peut lire comme “monmax x y vaut y si x<y et vaut x sinon”.

Exercices

  1. Essayer la fonction taille d’une liste

    taille [] = 0
taille (t:q) = 1 + (taille q)

    Vérifier que cette fonction est de type [a] -> p. Ce qui signifie qu’elle prend en entrée une liste de choses de type a quelconque et renvoie un nombre (Num p).

  2. estDans teste si un élément donné appartient à la liste.

  3. concatene met deux listes bout à bout.

  4. renverse renvoie la liste à l’envers.

  5. Calculer la complexité des fonctions concatene et renverse.

  6. maximuml renvoie le plus grand élément d’une liste d’entiers.

  7. minimuml renvoie le plus grand élément d’une liste d’entiers.

  8. repete n m renvoie la liste composée de n fois l’élément m.

    *Main> repete 5 "ah"
["ah","ah","ah","ah","ah"]

  9. cyclel n l renvoie la liste composée de n fois la liste l.

  10. pairs n renvoie la liste des n premiers nombres pairs.

  11. takel n l renvoie la liste des n premiers éléments de l.

  12. dropl n l renvoie la liste des éléments de l privée des n premiers.

  13. lastl renvoie le dernier élément d’une liste.

  14. initl renvoie la liste privée de son dernier élément.

*Main> cyclel 4 ["oui", "non"]
["oui","non","oui","non","oui","non","oui","non"]
*Main> pairs 10
[2,4,6,8,10,12,14,16,18,20]
*Main> takel 4 [2,4,6,8,10,12,14,16,18,20]
[2,4,6,8]
*Main> dropl 4 [2,4,6,8,10,12,14,16,18,20]
[10,12,14,16,18,20]
*Main> lastl [2,4,6,8,10,12,14,16,18,20]
20
*Main> initl [2,4,6,8,10,12,14,16,18,20]
[2,4,6,8,10,12,14,16,18]