Re: [Caml-list] Function returning recursive lists

Re: [Caml-list] Function returning recursive lists

[Julien Blond]

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

Hi Eric,

I tried to do something like that some times ago, while my concern was
about some tricky recursive module definition, i think the problem was the
same : the chicken-egg one. Your docycle is trying to define something it
must already know and the problem can't be escaped for evaluation order
prevents any value to be recursive at definition time. The recursivity can
be achieved by using a second construction pass that corresponds to
additional properties (lazyness or mutability or hacking through Obj).
Those properties will necessarily occur either explicitly (like OCaml) or
implicitly (like in Haskell).

So, the real question, as far as i understand your problem, is : are you
asking how to hide those properties in OCaml or to see if you need to ask
your purchasing department some quantum computer that can predict the
address of a future allocated block ? ;)

-- Julien


2012/12/18 Eric Jaeger <eric.jaeger@ssi.gouv.fr>

> Hi everyone,****
>
> ** **
>
> There are various discussions on recursive lists in the archive, yet I was
> wondering whether or not it was possible in pure OCaml to write a function
> returning non-constant recursive lists.****
>
> ** **
>
> For example, I would like to have a function “docycle:’a list->’a list”
> that takes a non recursive list and transforms it into a recursive list
> containing the same elements. That is, “docycle [1;2;3]” would return a
> list structurally equivalent to “let rec c=1::2::3::c in c”. So far, my
> various attempts (OCaml 3.12) have not been successful. Another good
> example is to have a List.map compatible with recursive lists.****
>
> ** **
>
> Please note that it is, in a way, a theoretical (and possibly naïve)
> question :****
>
> **-          **I do not consider recursive lists as the perfect
> implementation for my problem****
>
> **-          **I do not care about efficiency****
>
> **-          **I do not want to use an ad hoc mutable/lazy list datatype
> (unless I’ve also a conversion function toward standard lists)****
>
> **-          **I do not want to use Obj or other similar tricks****
>
> It’s just that I’m curious whether or not what I’m trying to achieve is
> possible.****
>
> ** **
>
>   Regards, Eric****
>
> ** **
>

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

RE: [Caml-list] Function returning recursive lists

[Eric Jaeger]

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

Thanks all for your answers. The consensus seems to be that it is not
possible to define an OCaml function returning recursive lists (or more
generally recursive values), unless using various forms of tricks such as
lazyness or Obj. So on the one hand we have OCaml functions as results of
computations which are not analyzable, and on the other hand recursive
(immutable) values which are analyzable but can only be defined instead of
being computed.

 

I would not request any form of "improvement" in this area (as far as I'm
concerned, I'm not comfortable with such recursive values); this was pure
curiosity.

 

  Regards, Eric

 


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

Re: [Caml-list] Function returning recursive lists

[Lukasz Stafiniak]

On Tue, Dec 18, 2012 at 2:13 PM, Eric Jaeger <eric.jaeger@ssi.gouv.fr> wrote:
> Thanks all for your answers. The consensus seems to be that it is not
> possible to define an OCaml function returning recursive lists (or more
> generally recursive values), unless using various forms of tricks such as
> lazyness or Obj. So on the one hand we have OCaml functions as results of
> computations which are not analyzable, and on the other hand recursive
> (immutable) values which are analyzable but can only be defined instead of
> being computed.

The restriction is understandable on semantic basis, e.g. you "want"
laziness when you have such recursion. But (1) it can be cumbersome:
call-by-value means I need to inline functions / cannot abstract some
behaviors into functions; (2) it can give unpleasant surprises, for
example when using a state monad hidden behind an abstract data type:
the system does not realize that I'm defining a function.

Re: [Caml-list] Function returning recursive lists

[Philippe Wang]

Hi,

I have a (somehow silly) answer to your question:

let gen_make_circ n =
  Printf.printf "let make_circ = function [] -> []\n";
  for i = 1 to n do
    Printf.printf "| [";
    for j = i to n do
      Printf.printf "x%d;" j
    done;
    Printf.printf "] -> let rec res = ";
    for j = i to n do
      Printf.printf "x%d :: " j
    done;
    Printf.printf "res in res\n"
  done;
  Printf.printf "| _ -> failwith \"not implemented\"\n%!"

let _ = gen_make_circ 4;;

prints this :

let make_circ = function [] -> []
| [x1;x2;x3;x4;] -> let rec res = x1 :: x2 :: x3 :: x4 :: res in res
| [x2;x3;x4;] -> let rec res = x2 :: x3 :: x4 :: res in res
| [x3;x4;] -> let rec res = x3 :: x4 :: res in res
| [x4;] -> let rec res = x4 :: res in res
| _ -> failwith "not implemented"

And then can be used:

let _ = make_circ [23;45];;
- : int list =
[23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45;
 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45;
 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45;
 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45;
 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45;
 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45;
 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45;
 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23;
 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; 45; 23; ...]


Cheers,
Philippe Wang



On Tue, Dec 18, 2012 at 9:37 AM, Eric Jaeger <eric.jaeger@ssi.gouv.fr> wrote:
> Hi everyone,
>
>
>
> There are various discussions on recursive lists in the archive, yet I was
> wondering whether or not it was possible in pure OCaml to write a function
> returning non-constant recursive lists.
>
>
>
> For example, I would like to have a function “docycle:’a list->’a list” that
> takes a non recursive list and transforms it into a recursive list
> containing the same elements. That is, “docycle [1;2;3]” would return a list
> structurally equivalent to “let rec c=1::2::3::c in c”. So far, my various
> attempts (OCaml 3.12) have not been successful. Another good example is to
> have a List.map compatible with recursive lists.
>
>
>
> Please note that it is, in a way, a theoretical (and possibly naïve)
> question :
>
> -          I do not consider recursive lists as the perfect implementation
> for my problem
>
> -          I do not care about efficiency
>
> -          I do not want to use an ad hoc mutable/lazy list datatype (unless
> I’ve also a conversion function toward standard lists)
>
> -          I do not want to use Obj or other similar tricks
>
> It’s just that I’m curious whether or not what I’m trying to achieve is
> possible.
>
>
>
>   Regards, Eric
>
>



-- 
Philippe Wang
   mail@philippewang.info

Re: [Caml-list] Function returning recursive lists

[Jeremy Yallop]

On 19 December 2012 22:23, Philippe Wang <mail@philippewang.info> wrote:
> I have a (somehow silly) answer to your question:
>
> let gen_make_circ n =
>   Printf.printf "let make_circ = function [] -> []\n";

That's an interesting idea, Philippe.  Here's an approach along the
same lines using MetaOCaml.

  let rec docycle l =
   .!(.< let rec s =
          .~(let rec loop = function
               | [] -> .< s >.
               | x :: xs -> .< x :: .~(loop xs) >.
             in loop l)
         in s >.)

The essential idea is the same as in your code: dynamically generating
a suitable 'let rec' expression.  However, MetaOCaml also helpfully
guarantees that the generated code is well-formed and well-typed, and
makes it possible to compile and run the generated code without
leaving the language.

Here's the code in action:

    # docycle;;
    - : 'a list -> 'a list = <fun>
    # docycle [1;2;3];;
    - : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2;
3; 1; ...]
    # docycle [1;2;3;4;5];;
    - : int list = [1; 2; 3; 4; 5; 1; 2; 3; 4; 5; 1; 2; 3; 4; 5; 1; 2;
3; 4; ...]

(For the sake of simplicity I haven't handled the case where the input
list is empty, but that's not difficult to do.)

Re: [Caml-list] Function returning recursive lists

[Ashish Agarwal]

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

It would be nice to have metaocaml as one of the available compilers in
opam. Anyone thinking of doing that?

On Wed, Dec 19, 2012 at 6:50 PM, Jeremy Yallop <yallop@gmail.com> wrote:

> On 19 December 2012 22:23, Philippe Wang <mail@philippewang.info> wrote:
> > I have a (somehow silly) answer to your question:
> >
> > let gen_make_circ n =
> >   Printf.printf "let make_circ = function [] -> []\n";
>
> That's an interesting idea, Philippe.  Here's an approach along the
> same lines using MetaOCaml.
>
>   let rec docycle l =
>    .!(.< let rec s =
>           .~(let rec loop = function
>                | [] -> .< s >.
>                | x :: xs -> .< x :: .~(loop xs) >.
>              in loop l)
>          in s >.)
>
> The essential idea is the same as in your code: dynamically generating
> a suitable 'let rec' expression.  However, MetaOCaml also helpfully
> guarantees that the generated code is well-formed and well-typed, and
> makes it possible to compile and run the generated code without
> leaving the language.
>
> Here's the code in action:
>
>     # docycle;;
>     - : 'a list -> 'a list = <fun>
>     # docycle [1;2;3];;
>     - : int list = [1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2;
> 3; 1; ...]
>     # docycle [1;2;3;4;5];;
>     - : int list = [1; 2; 3; 4; 5; 1; 2; 3; 4; 5; 1; 2; 3; 4; 5; 1; 2;
> 3; 4; ...]
>
> (For the sake of simplicity I haven't handled the case where the input
> list is empty, but that's not difficult to do.)
>
> --
> 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: 2520 bytes --]

Re: [Caml-list] Function returning recursive lists

[Gabriel Scherer]

No, I don't think it is.

On Tue, Dec 18, 2012 at 9:37 AM, Eric Jaeger <eric.jaeger@ssi.gouv.fr> wrote:
> It’s just that I’m curious whether or not what I’m trying to achieve is
> possible.
>
>

[Caml-list] Function returning recursive lists

[Eric Jaeger]

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

Hi everyone,

 

There are various discussions on recursive lists in the archive, yet I was
wondering whether or not it was possible in pure OCaml to write a function
returning non-constant recursive lists.

 

For example, I would like to have a function “docycle:’a list->’a list” that
takes a non recursive list and transforms it into a recursive list
containing the same elements. That is, “docycle [1;2;3]” would return a list
structurally equivalent to “let rec c=1::2::3::c in c”. So far, my various
attempts (OCaml 3.12) have not been successful. Another good example is to
have a List.map compatible with recursive lists.

 

Please note that it is, in a way, a theoretical (and possibly naïve)
question :

-          I do not consider recursive lists as the perfect implementation
for my problem

-          I do not care about efficiency

-          I do not want to use an ad hoc mutable/lazy list datatype (unless
I’ve also a conversion function toward standard lists)

-          I do not want to use Obj or other similar tricks

It’s just that I’m curious whether or not what I’m trying to achieve is
possible.

 

  Regards, Eric

 


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

Re: [Caml-list] Function returning recursive lists

[Peter Frey]

On Tue, 2012-12-18 at 09:37 +0100, Eric Jaeger wrote:
> Hi everyone,
> 
>  
> 
> There are various discussions on recursive lists in the archive, yet I
> was wondering whether or not it was possible in pure OCaml to write a
> function returning non-constant recursive lists.
> 
>  
> 
> For example, I would like to have a function “docycle:’a list->’a
> list” that takes a non recursive list and transforms it into a
> recursive list containing the same elements. That is, “docycle
> [1;2;3]” would return a list structurally equivalent to “let rec
> c=1::2::3::c in c”. So far, my various attempts (OCaml 3.12) have not
> been successful. Another good example is to have a List.map compatible
> with recursive lists.
> 
>  
> 
> Please note that it is, in a way, a theoretical (and possibly naïve)
> question :
> 
> -          I do not consider recursive lists as the perfect
> implementation for my problem
> 
> -          I do not care about efficiency
> 
> -          I do not want to use an ad hoc mutable/lazy list datatype
> (unless I’ve also a conversion function toward standard lists)
> 
> -          I do not want to use Obj or other similar tricks
> 
> It’s just that I’m curious whether or not what I’m trying to achieve
> is possible.
> 
>  
> 
>   Regards, Eric
> 
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"
 

  let docycle = function              (* copy and convert to circular *)
	| [] -> raise (Failure"Cannot make [] circular")
	| h0 :: t ->
		let r = { hd = h0; tl = [] } in
		let rec loop dst = function
	        | [] -> dst.tl <- inj r; dst.tl
		| h :: t ->
                        let cell = { hd = h; tl = [] } in
		        dst.tl <- inj cell;
                        loop cell t
		in loop r t

  let docycle = function              (* convert to circular in place *)
	| [] -> raise (Failure"Cannot make [] circular")
	| ll ->
                let rec aux dst = 
                if dst.tl = [] then begin     (* at end : *)
                        dst.tl <- ll;   (* replace last cell with ll *)
                        List.tl (inj dst)     (* and rotate to begin *)
                end else aux (jni (dst.tl));  (* advance *)
                in aux (jni ll)
end

let a = Cycle.docycle (ExtLib.String.explode "1234")
let _ = let open Printf in List.iter print_char (ExtLib.List.take 50 a) 

$peter@ubuntu:~/ocaml/dink$ ./a.out 
12341234123412341234123412341234123412341234123412peter@ubuntu:~/ocaml/dink$ 

Re: [Caml-list] Function returning recursive lists

[Philippe Wang]

On Fri, Dec 21, 2012 at 8:55 PM, Peter Frey <pjfrey@sympatico.ca> wrote:
>   external inj : 'a mut_list -> 'a list = "%identity"
>   external jni : 'a list -> 'a mut_list = "%identity"

This is exactly like using Obj.magic ! ;-)

--
Philippe Wang
   mail@philippewang.info

Re: [Caml-list] Function returning recursive lists

[Peter Frey]

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

Re: [Caml-list] Function returning recursive lists

[Arkady Andrukonis]

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

Re: [Caml-list] Function returning recursive lists

[Philippe Wang]

> 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

Re: [Caml-list] Function returning recursive lists

[Philippe Wang]

On Fri, Dec 28, 2012 at 2:41 AM, Peter Frey <pjfrey@sympatico.ca> wrote:

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

From my point of view, this coding style is fundamentally *wrong*:
- it makes assumptions on the internal data representation,
- and it prevents the compiler from making any optimisation from the
fact that elements of built-in lists are immutable (and if the
compilers makes some optimisations from that fact, then it's not only
the style but the program that is wrong).

Cheers,

--
Philippe Wang
   mail@philippewang.info

Re: [Caml-list] Function returning recursive lists

[Didier Cassirame]

Hi all,

Regarding the original question, wouldn't it be easier to implement it
as a stream?

didier

2012/12/28, Philippe Wang <mail@philippewang.info>:
> On Fri, Dec 28, 2012 at 2:41 AM, Peter Frey <pjfrey@sympatico.ca> wrote:
>
>> 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.
>
> From my point of view, this coding style is fundamentally *wrong*:
> - it makes assumptions on the internal data representation,
> - and it prevents the compiler from making any optimisation from the
> fact that elements of built-in lists are immutable (and if the
> compilers makes some optimisations from that fact, then it's not only
> the style but the program that is wrong).
>
> Cheers,
>
> --
> Philippe Wang
>    mail@philippewang.info
>
> --
> 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
>

Re: [Caml-list] Function returning recursive lists

[Francois Berenger]

On 12/29/2012 12:22 AM, Didier Cassirame wrote:
> Hi all,
>
> Regarding the original question, wouldn't it be easier to implement it
> as a stream?

It smells as someone needs a stream or a lazy list indeed.

Happy new year! ;)

> didier
>
> 2012/12/28, Philippe Wang <mail@philippewang.info>:
>> On Fri, Dec 28, 2012 at 2:41 AM, Peter Frey <pjfrey@sympatico.ca> wrote:
>>
>>> 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.
>>
>>  From my point of view, this coding style is fundamentally *wrong*:
>> - it makes assumptions on the internal data representation,
>> - and it prevents the compiler from making any optimisation from the
>> fact that elements of built-in lists are immutable (and if the
>> compilers makes some optimisations from that fact, then it's not only
>> the style but the program that is wrong).
>>
>> Cheers,
>>
>> --
>> Philippe Wang
>>     mail@philippewang.info
>>
>> --
>> 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
>>
>