Re: [Caml-list] Function returning recursive lists

[Peter Frey <pjfrey@sympatico.ca>]

On Sat, 2012-12-22 at 11:53 +0100, Eric Jaeger (ANSSI) wrote: 
> On 21/12/2012 20:55, Peter Frey wrote:
> > It sometimes helps to read read the various libraries.
> > For example, this thing is a variation of Batteries.BatList.Append:
> >
> > module Cycle = struct
> >    type 'a mut_list = { hd: 'a; mutable tl: 'a list }
> >    external inj : 'a mut_list -> 'a list = "%identity"
> >    external jni : 'a list -> 'a mut_list = "%identity"
> As far as I know, the use of "%identity" is a trick which is similar to 
> Obj, telling the compiler to do nothing. You would not be allowed to do 
> that with standard, typed OCaml identity. In this sense, it is not the 
> sort of solution I'm looking for.
> 
>    Regards, Eric

For what it's  worth: Obj.ml, contains the line:
...
external magic : 'a -> 'b = "%identity"
...
That type allows anything, including 'unifying' any two types.
(The compiler does not do nothing: it assigns the argument of type 'a to
be the result which is of type 'b and is perfectly willing to produce
code that instantly causes a segmentation fault)

inj and its inverse jni seem to have a type at least a bit more friendly
since they control the usage of the individual fields.
As long as you trust Ocaml lists to always have the layout above, this
seems a lot saver to me than type 'a -> 'b.

You wanted, in effect, something like:
# let rec l = [1;2;3;l];;
Error: This expression has type int list
       but an expression was expected of type int

The type 'a list is built into the system; it is not recursive and if
there was a way to force it to be so (without hacks), the type system
would not be sound.

You know the following, of course:

# type 'a aRec = {mutable hd: 'a; mutable tl:'a aRec};;
type 'a aRec = { mutable hd : 'a; mutable tl : 'a aRec; }

# let rec a = {hd=1; tl=a};;           
val a : int aRec =
  {hd = 1;
   tl =
    {hd = 1;
     tl =
      {hd = 1;
       tl =
        {hd = 1;
         tl =

The problem with docycle is not its coding style but that it produces in
fact a cyclic list, which is not very useful: Almost all functions, such
as List.rev are undefined. 


Peter