Re: [Caml-list] Streams

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

    Alain,

> type
>   'a stream =
>      | Nil
>      | Patchable of 'a stream_patchable
> and 'a stream_patchable = { mutable data : 'a streamCell }
> and
>   'a streamCell =
>     | Cons of 'a * 'a stream
>     | Append of 'a stream * 'a stream
>     | Delayed of (unit -> 'a stream)
>     | Generator of int * (int -> int) * (int -> 'a)

Mes listes à évaluation retardées contrairement à celles de Rauglaudre
supportent (quasi) totalement les fonctions génératrices, en
particulier leur concaténation.

Quand Generator ou Delayed vont envoyer une exception [Empty] ou une
liste vide [Nil] respectivement, il faut que je mémorise la valeur, ce
qui empêche la construction que vous proposez à moins d'utiliser
Append (Nil, Nil) ou un nouveau constructeur NilBis dans StreamCell.

voici ma fonction force

let rec force = function stream ->
 (match stream.data with
   | Delayed f -> let x = f () in stream.data <- x.data
   | Generator (index, succ, gen) ->
      (try
         let next_index = succ index in
           stream.data <- Cons (gen next_index, 
              makeStream (Generator (next_index, succ, gen)))
        with Empty -> stream.data <- Nil)
   etc.
  ) ;
  stream 

En fait nous voudrions mimer le mieux possible le comportement des
listes de base, avec une unique représentation de la liste vide :
# []
- : 'a list = []
# let (_ :: tail) = [1] in tail
- : int list = []

# { data = Nil }
- : '_a stream = { data = Nil }

> Couln't you just abstract the generator outside the stream ?
> 
> let gen ini f =
>   let state = ref ini in
>   (fun () -> state := f !state),
>   (fun () -> !state);;
> 
> Do you really need to keep the current state visible ?

Cette représentation des générateurs a été choisie afin de pouvoir
implémenter (relativement) efficacement les fonctions take et drop.

J'ai gardé l'indexe courant visible car c'était fait ainsi dans
l'implémentation de Rauglaudre, en effet dans les streams de Caml
l'indexe compte simultanément le nombre d'états consommés : 

la fonction drop k applique simplement succ^k sur l'indexe,

la fonction take k remplace succ par la version suivante
  let count = ref k in
  let succ' = function index ->
    if !count = 0 then raise Empty
    else decr count ; succ index

L'idée est essentiellement que décaler d'un indice est plus rapide que
générer une valeur avec evenutellement une fonction triviale si ce
n'est pas le cas 'a * 'a -> 'a * 'a -> 'a

        Diego Olivier

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners