Re: [Caml-list] Function returning recursive lists

[Arkady Andrukonis <grazingcows@yahoo.com>]

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

Hi, 


You cannot have a circular recursive definition

let rec ls = [1; 2; 3; ls; ] ;;

but you can have a "circular" list:

let rec ls = [1; 2; 3;] :: ls ;;

it creates 40 items,
the first 38 are [1; 2; 3;] and the 39 is 
[1; 2; ...]; and the last [...]. 
We cannot say it is a true 'circular' list, because
we don't return from the last element to the 
first element. At any rate this will result 
in an expression that is nested too deep and 
we won't be able to use it. The ellipsis [...] has
the force of 'any' but it returns the same element
as before, a list of lists. An example of a not
very useful circular list in the literature 
shows a continuous loop
let rec process = 1 :: 2 :: 3 :: 4 :: 5 :: process;;
while true do
  let process :: process = process in
  printf "Handling  process %d\n" process;
  Unix.sleep 2;
done ;;

________________________________
 From: Peter Frey <pjfrey@sympatico.ca>
To: Eric Jaeger (ANSSI) <eric.jaeger@ssi.gouv.fr> 
Cc: caml-list@inria.fr 
Sent: Thursday, December 27, 2012 8:41 PM
Subject: Re: [Caml-list] Function returning recursive lists
 
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





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

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