Re: [Caml-list] listes qui bouclent

[Jeremy Yallop <yallop@gmail.com>]

[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.