[Caml-list] listes qui bouclent

[Caml-list] listes qui bouclent

[Jean-Denis Eiden]

Bonjour à tous,

CaML light permet la construction suivante :

#let rec liste = 0::1::2::3::liste;;
liste : int list =
 [0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0;
  1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1;
  2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2;
  3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2;
  ...]

Cela étant, j'aimerais pouvoir faire la même chose en paramétrant la période 
; par exemple, j'aimerais créer [ 0 ; 1 ; 2 ; ... ; n-1 ; 0 ; 1 ; 2 ; ... ] 
:

#let repète n = let aux = ref [] in for i = n-1 downto 0 do aux:= i::(!aux) 
done; !aux;;
repète : int -> int list = <fun>

#let cyclique n = let aux = repète n in let rec liste = aux @ liste in 
liste;;

Mais là :

let cyclique n = let rec liste = (repète n) @ liste in liste;;
>                                           ^^^^^^^
Ce genre d'expressions n'est pas autorisé comme membre droit d'un "let rec".

Est-ce seulement un problème de syntaxe ou bien y a-t-il impossibilité 
absolue, la taille de la liste servant de période devant être connue à la 
compilation ?

Cordialement, Jean-Denis Eiden

Re: [Caml-list] listes qui bouclent

[Rémy Besognet]

[-- Attachment #1: Type: text/plain, Size: 2664 bytes --]

Bonjour,

Il me semble que seules les valeurs fonctionnelles sont autorisées à droite
d'un let-rec.
La seule exception est un constructeur de type

Effectivement, le "::" n'est pas un véritable opérateur, mais bien un
constructeur de type.

Prenons le type :

type 'a t = Empty | List of  'a * 'a t

Si on fait :

let cyclique n = let rec liste = List (1, liste) in liste;;

ça passe parce que List est bien un constructeur de type. Or dans :

let cyclique n = let rec liste = (repète n) @ liste in liste;;

l'opérateur @ n'est pas un constructeur, mais bien un appel de fonction qui
lie le nom liste à l'appel et c'est précisément ce que le compilateur ne
veut pas. Parce qu'il veut que la construction d'une valeur récursif qui
n'est ppas une fonction soit statique.

Tu as le détail dans le manuel d'Ocaml :
http://caml.inria.fr/pub/docs/manual-ocaml/extn.html#s%3aletrecvalues

Cordialement,



Le 7 septembre 2014 10:31, Jean-Denis Eiden <jean-denis.eiden@orange.fr> a
écrit :

> Bonjour à tous,
>
> CaML light permet la construction suivante :
>
> #let rec liste = 0::1::2::3::liste;;
> liste : int list =
> [0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0;
>  1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1;
>  2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2;
>  3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2; 3; 0; 1; 2;
>  ...]
>
> Cela étant, j'aimerais pouvoir faire la même chose en paramétrant la
> période ; par exemple, j'aimerais créer [ 0 ; 1 ; 2 ; ... ; n-1 ; 0 ; 1 ; 2
> ; ... ] :
>
> #let repète n = let aux = ref [] in for i = n-1 downto 0 do aux:=
> i::(!aux) done; !aux;;
> repète : int -> int list = <fun>
>
> #let cyclique n = let aux = repète n in let rec liste = aux @ liste in
> liste;;
>
> Mais là :
>
> let cyclique n = let rec liste = (repète n) @ liste in liste;;
>
>>                                           ^^^^^^^
>>
> Ce genre d'expressions n'est pas autorisé comme membre droit d'un "let
> rec".
>
> Est-ce seulement un problème de syntaxe ou bien y a-t-il impossibilité
> absolue, la taille de la liste servant de période devant être connue à la
> compilation ?
>
> Cordialement, Jean-Denis Eiden
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>



-- 
*Rémy El SibaïeEquipe APR, LIP6/IRILL, Université Pierre et Marie Curie*

[-- Attachment #2: Type: text/html, Size: 4931 bytes --]

Re: [Caml-list] listes qui bouclent

[Jeremy Yallop]

[This message is intentionally but regrettably written in English.]

Dear Jean-Denis,

Caml Light is not really maintained any more, so unless you have a
special reason to use it it might be better to switch to OCaml.  I'll
suggest an answer to your question for OCaml, which might not apply
directly to Caml Light.

2014-09-07 10:31 GMT+01:00 Jean-Denis Eiden <jean-denis.eiden@orange.fr>:
> Cela étant, j'aimerais pouvoir faire la même chose en paramétrant la période
> ; par exemple, j'aimerais créer [ 0 ; 1 ; 2 ; ... ; n-1 ; 0 ; 1 ; 2 ; ... ]

I don't know of a way to create cyclic lists of a runtime specified
period using the built-in list type, and I suspect that it isn't
possible.  However, if you're willing to use an alternative list type
then it is possible to accomplish what you want.

The natural setting for a cyclic immutable value is a lazy language.
OCaml is eagerly evaluated by default, but provides support for
introducing laziness explicitly.  We can define a type of lazy lists
in OCaml as follows:

   type 'a llist_aux = LNil | LCons of 'a * 'a llist
   and 'a llist = 'a llist_aux Lazy.t

Using this definition we can write a function which creates cyclic
values of a given period:

   let lcyclic period =
     if period <= 0 then invalid_arg "lcyclic";
     let rec loop i =
       if i = period then l
       else lazy (LCons (i, loop (i + 1)))
     and l = lazy (Lazy.force (loop 0)) in
     l

If you trace through the operation of lcyclic you'll see that a call like this

   lcyclic 3

builds a value that's equivalent to the value created by writing this

   let rec l3 =
      lazy (LCons (0,
      lazy (LCons (1,
      lazy (LCons (2, l3))))))))

Since OCaml has special support for lazy values there's less overhead
than you might imagine in programming with values like this.  Once
every element of the list has been examined the runtime system can
make the representation exactly the same as a corresponding value of
the built-in list type.  However, there's still a little overhead
involved in examining values of llist.

A second approach to building cyclic lists of runtime-specified period
is to use mutation.  If you make the tail of your list values mutable
then you can build the list up to the cyclic point, then patch things
up so that the tail of the last cons cell points back to the front of
the list.  Here's a type definition:

   type 'a mlist = MNil | MCons of 'a mcons
   and 'a mcons = { mhead : 'a; mutable mtail : 'a mlist }

and here's a corresponding function for building cyclic lists:

   let mcyclic period =
     if period <= 0 then invalid_arg "mcyclic";
     let rec mlast = { mhead = period - 1; mtail = MCons mlast }
     and loop i head =
       if i = 0 then head
       else loop (i - 1) (MCons { mhead = i - 1; mtail = head }) in
     let l = loop (period - 1) (MCons mlast) in
        mlast.mtail <- l;
        l

Once again, if you trace through the evaluation of an expression like this

   mcyclic 3

you'll see that it builds a value equivalent to the value created by
writing this

   let rec m3 =
    MCons {mhead = 0; mtail =
    MCons {mhead = 1; mtail =
    MCons {mhead = 2; mtail = m3}}}

Using mutation here introduces a little extra representation overhead
in OCaml, since mutation requires a record, which involves allocating
an extra block for every cons cell.  There's consequently also an
extra level of indirection when examining values of mlist compared to
examining values of the built-in list type.

I hope that helps a bit,

Jeremy.