td4.md 4.79 KB
Newer Older
Pierre Letouzey's avatar
Pierre Letouzey committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
TD4 : Listes à accès arbitraire rapide
======================================

**M2 LMFI**

On s'intéresse ici à des structures de données purement fonctionnelles (on dit également *persistantes*) permettant de représenter des *listes*, c'est-à-dire des séquences finies et ordonnées d'éléments ayant des opérations *par la gauche* efficaces: ajout via `cons` et retrait via `head` et `tail`.

En fait, dans ce qui suit, au lieu de fonctions séparées `head` et `tail`, on utilisera désormais une unique fonction `decons` telle que `decons l = Some (h,t)` si la liste a une tête `h` et une queue `t`, et `decons l = None` si `l` est vide.

On souhaite disposer également d'une fonction `nth` permettant d'accéder au n-ième élément d'une liste.

Dans tout ce TD, on considère comme complexité le nombre d'accès à des sous-structures de la liste, dans le pire cas, exprimée en fonction de la taille de la liste. On négligera pour l'instant les coûts liés à d'éventuels opérations sur les entiers. 

#### Exercice 1 : Implémentation par listes Coq

Implémentez les opérations suivantes, et indiquez leurs complexités.

```coq
cons : forall {A}, A -> list A -> list A
decons : forall {A}, list A -> option (A * list A)
nth : forall {A}, list A -> nat -> option 
```

#### Exercice 2 : Implémentation par b-listes

On va maintenant concevoir une structure de données pour laquelle les trois opérations `cons`, `decons` et `nth` seront au pire logarithmiques.

On appelle *b-liste* une liste (usuelle) d'arbres binaires parfaits ayant les données aux feuilles, satisfaisant de plus l'invariant suivant: la taille des arbres binaires est strictement croissante quand on avance vers la droite de cette liste.

  - Définir en Coq `blist : Type -> Type` correspondant à cette structure, ainsi que quelques exemples de petites b-listes de ce type. Définir en particulier la b-liste `empty`. Peut-on avoir deux b-listes différentes contenant les mêmes données ?

  - Ajustez ce type `blist` afin qu'on puisse connaître la taille des arbres qui composent une b-liste sans avoir besoin de parcourir ces arbres.

  - Implémentez maintenant les opérations `cons`, `decons` et `nth` sur le type `blist`, de manière à ce qu'elles soient toutes logarithmiques au pire.

Cette structure montre donc qu'il est possible d'accéder en temps logarithmique à une position arbitraire dans nos listes. Malheureusement ce premier essai conduit à une perte de complexité des opérations *à gauche* (`cons` et `decons`), qui ne sont plus en temps constant. Nous allons maintenant voir comment remédier à cela. Mais tout d'abord, un petit détour par de l'arithmétique : notre première structure est très liée à la décomposition binaire des nombres, et pour faire mieux nous allons utiliser une autre décomposition moins usuelle.

#### Exercice 3 : Arithmétique quasi-binaire

On appelle *écriture quasi-binaire* (ou qb-écriture) d'un nombre entier sa décomposition comme somme de nombres de la forme 2^k -1 avec k>0. On demande de plus que tous les termes de la somme soient différents, à part éventuellement les deux plus petits.

  - Ecrire une fonction `decomp` qui donne l'écriture quasi-binaire de tout nombre entier `n`. Peut-on avoir plusieurs écritures quasi-binaires du même nombre ?

Pierre Letouzey's avatar
Pierre Letouzey committed
44
  - Ecrire deux fonction `next` et `pred` qui font passer de l'écriture quasi-binaire d'un nombre à celle de son successeur et de son prédecesseur, sans chercher à reconstituer les nombres en question, et le tout sans récursivité (pas de `Fixpoint`).
Pierre Letouzey's avatar
Pierre Letouzey committed
45
46
47
48
49

On admet que la qb-écriture de `n` est une somme dont le nombre de termes est logarithmique en fonction de `n`.

#### Exercice 4 : Implémentation par qb-listes

50
  - En vous inspirant de ce qui précède, proposer une structure de *listes quasi-binaire* (ou qb-listes) pour laquelle `cons` et `decons` ont des complexités constantes tandis que `nth` est logarithmique.
Pierre Letouzey's avatar
Pierre Letouzey committed
51
52
53
54
55

  - Comparer ces qb-listes avec les listes usuelles : quelles raisons peuvent expliquer la faible adoption des qb-listes en lieu et place des listes usuelles ?

#### Extensions possibles

56
  - Coder sur les b-listes et les qb-listes une opération `drop` de complexité logarithmique, telle que `drop k l` retourne la b-liste `l` privée de ses `k` premiers éléments.
Pierre Letouzey's avatar
Pierre Letouzey committed
57
58
59
60
61
62
63
64
65

  - Coder sur les b-listes et les qb-listes une opération `update_nth` telle que `update_nth l n a` est une valeur optionnelle contenant une nouvelle liste où le n-ième élément a été changé en `a`, ou bien `None` si `n` n'est pas une position légale dans `l`.

  - Utiliser une représentation binaire des entiers, et calculer les complexités en intégrant le coût des opérations arithmétiques.

#### Reference

  - <https://en.wikipedia.org/wiki/Skew_binary_number_system>
  - Okasaki, Purely Functional Data Structures, 1998, Cambridge University Press