Flots de données

Flots de données

Les streams, ou flots, sont des séquences, potentiellement infinies, d'éléments de même nature. L'évaluation d'une partie d'un flot s'effectue à la demande, c'est-à-dire quand cela est nécessaire pour le calcul en cours : c'est une structure de données paresseuse.

Le type stream est un type de données abstrait dont on ne connaît pas l'implantation. On manipule les objets de ce type par des fonctions de construction et de destruction. Pour le confort de l'utilisateur, Objective CAML fournit des constructions syntaxiques simples pour construire des flots et accéder à leurs éléments.

Warning

Les streams sont une extension du langage et ne font pas partie du noyau stable d'Objective CAML.

Construction

La syntaxe allégée de construction des flots est inspirée de celle des liste ou des tableaux. Le flot vide s'écrit :


# [< >] ;;
- : 'a Stream.t = <abstr>

On peut construire un flot par énumération de ses éléments en les faisant précéder d'une apostrophe (caractère ')


# [< '0; '2; '4 >] ;;
- : int Stream.t = <abstr>

Les expressions qui ne sont pas précédées d'une apostrophe sont considérées comme des sous-flots :


# [< '0; [< '1; '2; '3 >]; '4 >] ;;
- : int Stream.t = <abstr>
# let s1 = [< '1; '2; '3 >] in [< s1; '4 >] ;;
- : int Stream.t = <abstr>
# let concat_stream a b = [< a ; b >] ;;
val concat_stream : 'a Stream.t -> 'a Stream.t -> 'a Stream.t = <fun>
# concat_stream [< '"if"; '"c";'"then";'"1" >] [< '"else";'"2" >] ;;
- : string Stream.t = <abstr>

Le module Stream fournit d'autres fonctions de construction. Par exemple, les fonctions of_channel et of_string retournent un flot contenant une suite de caractères, à partir d'un canal d'entrée ou d'une chaîne de caractères.


# Stream.of_channel ;;
- : in_channel -> char Stream.t = <fun>
# Stream.of_string ;;
- : string -> char Stream.t = <fun>

Le calcul retardé des flots permet de manipuler des structures de données infinies d'une façon similaire au type 'a enum défini à la page ??. On définit le flot des entiers naturels par son premier élément et une fonction calculant le flot des éléments suivants.


# let rec nat_stream n = [< 'n ; nat_stream (n+1) >] ;;
val nat_stream : int -> int Stream.t = <fun>
# let nat = nat_stream 0 ;;
val nat : int Stream.t = <abstr>

Destruction et filtrage de flots

La primitive next permet à la fois d'évaluer, de récupérer et d'enlever le premier élément d'un flot :


# for i=0 to 10 do 
   print_int (Stream.next nat) ;
   print_string "  "
   done ;;
0  1  2  3  4  5  6  7  8  9  10  - : unit = ()
# Stream.next nat ;;
- : int = 11

Lorsque le flot est épuisé, une exception est déclenchée.


# Stream.next [< >] ;;
Uncaught exception: Stream.Failure

Pour manipuler les flots, Objective CAML offre une construction de filtrage dédiée dit filtrage destructif. La valeur filtrée est calculée et retirée du flot. Il n'y a pas de notion d'exhaustivité du filtrage des flots et, parce que nous manipulons une structure paresseuse potentiellement infinie, on peut ne pas filtrer la totalité du flot. La syntaxe de filtrage est :

Syntaxe

match expr with parser [< 'p₁ ...>] -> expr₁ | ...

La fonction next peut s'écrire :


# let next s = match s with parser [< 'x >] -> x ;;
val next : 'a Stream.t -> 'a = <fun>
# next nat;;
- : int = 12

Remarquez que l'énumération des entiers reprend là où nous l'avions laissée.

À la manière de l'abstraction, il existe une forme syntaxique filtrant un paramètre de type Stream.t.

Syntaxe

parser p -> ...

La fonction next peut alors se réécrire ainsi :


# let next = parser [<'x>] -> x ;;
val next : 'a Stream.t -> 'a = <fun>
# next nat ;;
- : int = 13

Il est possible de filtrer le flot vide, mais attention : le motif de flot [<>] filtre n'importe quel flot. En effet, un flot s est toujours égal au flot [< [<>]; s >]. Il faut en conséquence inverser l'ordre usuel du filtrage :


# let rec it_stream f s =
  match s with parser
    [< 'x ; ss >] -> f x ; it_stream f ss
  | [<>] -> () ;;
val it_stream : ('a -> 'b) -> 'a Stream.t -> unit = <fun>
# let print_int1 n = print_int n ; print_string" " ;;
val print_int1 : int -> unit = <fun>
# it_stream print_int1 [<'1; '2; '3>] ;;
1 2 3 - : unit = ()

En utilisant le fait que le filtrage est destructif, on peut également écrire :


# let rec it_stream f s =
  match s with parser
    [< 'x >] -> f x ; it_stream f s
  | [<>] -> () ;;
val it_stream : ('a -> 'b) -> 'a Stream.t -> unit = <fun>
# it_stream print_int1 [<'1; '2; '3>] ;;
1 2 3 - : unit = ()

Si les flots sont paresseux, ils sont cependant de bonne volonté et ne refusent jamais de fournir leur premier élément et lorsque celui-ci est fourni, il est perdu. Ceci a des conséquences sur le filtrage. La fonction suivante est une tentative (vouée à l'échec) d'un affichage par couple d'un flot d'entiers, sauf éventuellement pour le dernier élément.


# let print_int2 n1 n2 = 
  print_string "(" ; print_int n1 ; print_string "," ; 
  print_int n2 ; print_string ")" ;;
val print_int2 : int -> int -> unit = <fun>
# let rec print_stream s =
  match s with parser
    [< 'x; 'y >] -> print_int2 x y; print_stream s
  | [< 'z >] -> print_int1 z; print_stream s
  | [<>] -> print_newline() ;;
val print_stream : int Stream.t -> unit = <fun>
# print_stream [<'1; '2; '3>];;
(1,2)Uncaught exception: Stream.Error("")

Les deux premiers éléments du flot ont bien été affichés, mais lors de l'évaluation de l'appel récursif (print_stream [< 3 >]) le premier motif a trouvé une valeur pour x, qui a donc été consommée, mais il ne restait plus rien pour y. C'est ce qui a provoqué l'erreur. En fait, le second filtre est inutile puisque, si le flot n'est pas vide, le premier motif peut toujours commencer l'évaluation.

Pour obtenir le résultat attendu, il faut séquentialiser le filtrage :


# let rec print_stream s =
  match s with parser
    [< 'x >]
     -> (match s with parser
           [< 'y >] -> print_int2 x y; print_stream s
         | [<>] -> print_int1 x; print_stream s)
  | [<>] -> print_newline() ;;
val print_stream : int Stream.t -> unit = <fun>
# print_stream [<'1; '2; '3>];;
(1,2)3 
- : unit = ()

Si le filtrage échoue sur le premier élément d'un filtre alors, on retrouve le comportement connu du filtrage :


# let rec print_stream s =
  match s with parser
    [< '1; 'y >] -> print_int2 1 y; print_stream s
  | [< 'z >] -> print_int1 z; print_stream s
  | [<>] -> print_newline() ;;
val print_stream : int Stream.t -> unit = <fun>
# print_stream [<'1; '2; '3>] ;;
(1,2)3 
- : unit = ()

Aux limites du filtrage

Par son caractère destructif, le filtrage des flots diffère du filtrage des types somme. Nous allons voir comment il peut en différer radicalement.

On peut écrire, de façon naturelle, une fonction qui calcule la somme des éléments d'un flot :


# let rec somme s =
  match s with parser
    [< 'n; ss >] -> n+(somme ss)
  | [<>] -> 0 ;;
val somme : int Stream.t -> int = <fun>
# somme [<'1; '2; '3; '4>] ;;
- : int = 10

Mais on peut également consommer le flot << de l'intérieur >> en nommant le résultat obtenu :


# let rec somme s =
  match s with parser
    [< 'n; r = somme >] -> n+r
  | [<>] -> 0 ;;
val somme : int Stream.t -> int = <fun>
# somme [<'1; '2; '3; '4>] ;;
- : int = 10

Nous étudierons d'autres utilisations importantes des flots dans le chapitre 11 consacré aux analyses lexicale et syntaxique. En particulier, nous verrons comment la consommation d'un flot de l'intérieur peut être mise à profit.