Re: [Caml-list] Function returning recursive lists

[Philippe Wang <mail@philippewang.info>]

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

Actually, no, it does *not* create 40 items at all: the printer make
no difference between circular data and big data.
If one creates a list with 1000 elements, only the first X elements
are displayed by "ocaml top-level interactive loop".
(X depends on the size of the printed data)

If the 39th is "[1; 2; ...]", it's only because the printer has
reached the limit at "2" and won't go further to "see" that there's
only a "3" remaining in that list.
(Reminder: computers are particularly dumb, they only do (exactly)
what we tell them to do.)

let rec ls = [1; 2; 3;] :: ls ;;
allocates [1; 2; 3;] and then a circular block (b) containing two
elements: 1. a pointer to that list ([1; 2; 3;]) and 2. a pointer to
itself (b).

Try this:
Array.to_list (Array.make 1000 42);;
And maybe try this:
List.length (Array.to_list (Array.make 1000 42));;

Cheers,
Philippe Wang

On Fri, Dec 28, 2012 at 10:37 AM, Arkady Andrukonis
<grazingcows@yahoo.com> wrote:
> 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
>
>



-- 
Philippe Wang
   mail@philippewang.info