Re: [Caml-list] Function returning recursive lists

[Peter Frey <pjfrey@sympatico.ca>]

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$