TP 02 - Pattern matching

Programmation fonctionnelle

Exercice 1 - Types

Pour chacune des expressions suivantes, déterminer son type, puis vérifier avec l’interpréteur.

  1. 'a'
  2. "abc"
  3. []
  4. ['a']
  5. ['a', 'b']
  6. ["abc", "def"]
  7. ['a', "abc"]
  8. ('a', 'b')
  9. ('a', "abc")
  10. ('a', "abc", 1)
  11. [odd, even]
  12. [odd, even, (==) 1]
  13. [odd, even, mod]
  14. (odd, even, mod)

Exercice 2 - Fonctions sur les listes

  1. La fonction delete du module Data.List supprime la première occurrence d’un élément dans une liste. Définir, avec son type, une fonction delete' ayant le même comportement pour les listes d’entiers.
λ> delete' 2 [1,2,3,2,1]
[1,3,2,1]
λ> delete' 20 [1,2,3,2,1]
[1,2,3,2,1]
  1. Définir, avec son type, une fonction deleteAll' qui prend un entier et une liste d’entiers, puis supprime toutes les occurrences de cet entier dans la liste.
λ> deleteAll' 2 [1,2,3,2,1]
[1,3,1]
  1. La fonction repeat de Prelude construit une liste infinie contenant toujours le même élément. Définir, avec son type, une fonction repeat' ayant le même comportement.
λ> take 10 (repeat' 1)
[1,1,1,1,1,1,1,1,1,1]
  1. La fonction take de Prelude prend les n premiers éléments d’une liste. Si la liste contient moins de n éléments, elle renvoie la liste entière. Définir, avec son type, une fonction take' ayant le même comportement. Ici, pour simplifier, on suppose que n n’est pas négatif.
λ> take' 10 [1..100]
[1,2,3,4,5,6,7,8,9,10]
λ> take' 10 [1..]
[1,2,3,4,5,6,7,8,9,10]
λ> take' 10 [1..2]
[1,2]
  1. La fonction drop de Prelude retire les n premiers éléments d’une liste. Si la liste contient moins de n éléments, elle renvoie la liste vide. Définir, avec son type, une fonction drop' ayant le même comportement. Ici, pour simplifier, on suppose que n n’est pas négatif.
λ> drop' 10 [1..15]
[11,12,13,14,15]
λ> drop' 10 [1..2]
[]
  1. Définir, avec son type, une fonction twoByTwo qui transforme une liste en une liste de paires d’éléments consécutifs. Si la liste contient un nombre impair d’éléments, le dernier est ignoré.
λ> twoByTwo [1..10]
[(1,2),(3,4),(5,6),(7,8),(9,10)]
λ> twoByTwo [1..11]
[(1,2),(3,4),(5,6),(7,8),(9,10)]
  1. La fonction intersperse du module Data.List insère un élément entre chaque paire d’éléments consécutifs d’une liste. Définir, avec son type, une fonction intersperse' ayant le même comportement.
λ> intersperse' 0 [1,2,3,4]
[1,0,2,0,3,0,4]
λ> intersperse' 0 []
[]

La fonction intercalate du module Data.List insère une liste entre les listes d’une liste de listes, puis concatène le résultat. Définir, avec son type, une fonction intercalate' ayant le même comportement.

λ> intercalate' [0] [[1,2],[3,4],[5]]
[1,2,0,3,4,0,5]
λ> intercalate' [0] []
[]
  1. La fonction zip associe deux listes élément par élément pour former une liste de paires. Si les listes n’ont pas la même longueur, elle s’arrête lorsque la plus courte est terminée. Définir, avec son type, une fonction zip' ayant le même comportement que zip.
λ> zip' [1,2,3] [9,8,7]
[(1,9),(2,8),(3,7)]
λ> zip' [1,2,3,4,5] [9,8]
[(1,9),(2,8)]
  1. La fonction unzip réalise l’opération inverse de zip : elle prend une liste de paires et la sépare en une paire de listes. Définir, avec son type, une fonction unzip' ayant le même comportement que unzip.
λ> unzip' [(1,2),(2,3),(3,4)]
([1,2,3],[2,3,4])
  1. La fonction intersect du module Data.List conserve les éléments de la première liste qui sont présents dans la seconde liste. Définir, avec son type, une fonction intersect' ayant le même comportement pour des listes d’entiers.
λ> intersect' [1,2,3,4] [5,4,3]
[3,4]
λ> intersect' [1,1,2,2,3,3,4,4] [5,4,3]
[3,3,4,4]
  1. Définir, avec son type, une fonction contains qui prend deux chaînes de caractères et teste si la première apparaît dans la seconde.

Indication : qu’auriez-vous fait, dans un style impératif ?

λ> contains "askell" "Haskell"
True
λ> contains "Hsk" "Haskell"
False
λ> contains "hello" "Hello"
False
λ> contains "" "Haskell"
True
λ> contains "Haskell" ""
False

Exercice 3 - Optionnel

Récursivité ++

  1. Définir, avec son type, une fonction prefixes qui retourne tous les préfixes non vides d’une liste.
λ> prefixes [1,2,3,4]
[[1],[1,2],[1,2,3],[1,2,3,4]]
  1. Définir, avec son type, une fonction factors qui renvoie tous les facteurs, c’est-à-dire toutes les sous-listes consécutives, ainsi que la liste vide.
λ> factors []
[[]]
λ> factors [1]
[[1],[]]
λ> factors [1,2,3,4]
[[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4],[]]

Trier récursivement, c’est facile

  1. Définir, avec son type, une fonction msplit qui sépare une liste en une paire de listes : la première contient les éléments d’indices pairs et la seconde ceux d’indices impairs. L’ordre des éléments est conservé dans chaque liste.
λ> msplit []
([],[])
λ> msplit [3,1,2,3,4,5,6]
([3,2,4,6],[1,3,5])
  1. Définir, avec son type, une fonction merge qui fusionne deux listes triées par ordre croissant en une seule liste triée par ordre croissant, en conservant les doublons.
λ> merge [] [1,3,4,5,7]
[1,3,4,5,7]
λ> merge [2,5,6,8] []
[2,5,6,8]
λ> merge [2,5,6,8] [1,3,4,5,7]
[1,2,3,4,5,5,6,7,8]
  1. Définir, avec son type, une fonction mergeSort qui trie une liste par ordre croissant en utilisant le tri fusion (merge sort). Utiliser les fonctions msplit et merge des questions précédentes.
λ> mergeSort [3,1,2,3,4,5,6]
[1,2,3,3,4,5,6]
λ> mergeSort []
[]
  1. Définir, avec son type, une fonction qsplit qui prend un pivot et une liste, puis renvoie une paire de listes : la première contient les éléments strictement inférieurs au pivot et la seconde les éléments supérieurs ou égaux au pivot. L’ordre des éléments est conservé dans chaque liste.
λ> qsplit 3 []
([],[])
λ> qsplit 3 [5,1,3,2,4,3]
([1,2],[5,3,4,3])
  1. Définir, avec son type, une fonction quickSort qui trie une liste par ordre croissant en utilisant le tri rapide (quicksort). Le pivot sera toujours choisi comme le premier élément de la liste.

Indication : utiliser qsplit pour répartir les éléments restants en deux listes, puis trier récursivement ces deux listes. Concaténer ensuite les résultats en plaçant le pivot entre les deux.

λ> quickSort [3,1,2,3,4,5,6]
[1,2,3,3,4,5,6]
λ> quickSort []
[]