forbidden construct as right hand side of "let rec"

forbidden construct as right hand side of "let rec"

[Mathias Kende]

Hello list,

I need to write something like this :

	let f f i = if i = 0 then 1 else i * f (i - 1)
	let rec g = f g

Of course the compiler won't let me write it (even if the OCaml type
system is happy):
	"This kind of expression is not allowed as right-hand side of `let rec'"

But as the function parameter of function f is used only for a recursive
call I believe that the function I try the define is at least "morally"
correct.

Is there a way to express this sort of construction in OCaml ? My aim is
to be able to have some things equivalent to:
	let rec g = f g
and
	let rec h = t (f h)
where t is some transformation over the function (conserving its type),
and still writing the code for f only once.

Regards,

Mathias

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Stéphane Glondu]

Mathias Kende a écrit :
> 	let rec g = f g

What about:

  let rec g x = f g x


-- 
Stéphane

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Lukasz Stafiniak]

While we are at it, what is the best way to convert a "straight" list
into a cyclic list?

i.e. convert

let l = a::b::[]

into

let rec l = a::b::l

(for arbitrary length lists). (The answer I recall from the archives
was using Obj.magic to mutate the [] in the original list).

On Fri, Oct 23, 2009 at 12:34 AM, Stéphane Glondu <steph@glondu.net> wrote:
> Mathias Kende a écrit :
>>       let rec g = f g
>
> What about:
>
>  let rec g x = f g x

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Damien Guichard]

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


let list_cycle2 a b =
  let rec loop = a::b::loop
  in loop


- damien




En réponse au message
de : Lukasz Stafiniak
du : 2009-10-23 01:10:37
À : caml-list
CC : 
Sujet : Re: [Caml-list] forbidden construct as right hand side of "let rec"

While we are at it, what is the best way to convert a "straight" list
into a cyclic list?

i.e. convert

let l = a::b::[]

into

let rec l = a::b::l

(for arbitrary length lists). (The answer I recall from the archives
was using Obj.magic to mutate the [] in the original list).

On Fri, Oct 23, 2009 at 12:34 AM, Stéphane Glondu  <steph@glondu.net > wrote:
> Mathias Kende a écrit :
> >       let rec g = f g
>
> What about:
>
>  let rec g x = f g x

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
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: 4853 bytes --]

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Marc de Falco]

The issue is that this definition can't be generalized to lists of  
arbitrary size.
The code
let list_cycle l =
  let rec loop = l @ loop in
  loop
will not be accepted.

I don't know the exact rule, but I guess that on the right-hand side  
of a
let rec defining a ground value named foo you can only write a term  
which
evaluates to a finite ground term on the currently defined variables +  
foo.
That is to say something that evaluates to a finite tree of  
constructors with
constants or defined variables as leaves.
Maybe someone more knowledgeable could state the exact rule.

- marc

P.S. : the code using Obj is far from a solution as it modifies the  
existing structure
of the list to add cycling and thus, breaks persistency.

Le 23 oct. 2009 à 17:35, Damien Guichard a écrit :

>
> let list_cycle2 a b =
>   let rec loop = a::b::loop
>   in loop
>
>
> - damien
>
> En réponse au message
> de : Lukasz Stafiniak
> du : 2009-10-23 01:10:37
> À : caml-list
> CC :
> Sujet : Re: [Caml-list] forbidden construct as right hand side of  
> "let rec"
>
> While we are at it, what is the best way to convert a "straight" list
> into a cyclic list?
>
> i.e. convert
>
> let l = a::b::[]
>
> into
>
> let rec l = a::b::l
>
> (for arbitrary length lists). (The answer I recall from the archives
> was using Obj.magic to mutate the [] in the original list).
>
> On Fri, Oct 23, 2009 at 12:34 AM, Stéphane Glondu  <steph@glondu.net  
> > wrote:
> > Mathias Kende a écrit :
> > >       let rec g = f g
> >
> > What about:
> >
> >  let rec g x = f g x
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[blue storm]

On Fri, Oct 23, 2009 at 6:14 PM, Marc de Falco <marc.defalco@gmail.com> wrote:
> I don't know the exact rule, but I guess that on the right-hand side of a
> let rec defining a ground value named foo you can only write a term which
> evaluates to a finite ground term on the currently defined variables + foo.
> That is to say something that evaluates to a finite tree of constructors
> with
> constants or defined variables as leaves.
> Maybe someone more knowledgeable could state the exact rule.

You can find this in the documentation :
http://caml.inria.fr/pub/docs/manual-ocaml/manual021.html#toc70

> P.S. : the code using Obj is far from a solution as it modifies the existing
> structure
> of the list to add cycling and thus, breaks persistency.

Well, you can easily copy the list before using Obj, wich preserves persistency.

Here is a relevant discussion on the list :
http://groups.google.com/group/fa.caml/browse_frm/thread/9aa32076b03dd6ff?pli=1

You can also look at Matias Giovannini's articles on his blogs (wich
are recommended reading anyway) :
http://alaska-kamtchatka.blogspot.com/2007/11/unsafe-clasp.html
http://alaska-kamtchatka.blogspot.com/2007/11/more-elegant-necklace.html

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Mathias Kende]

On Fri, 23 Oct 2009 00:34:29 +0200, Stéphane Glondu <steph@glondu.net>
wrote:
> Mathias Kende a écrit :
>> 	let rec g = f g
> 
> What about:
> 
>   let rec g x = f g x

This will compile, but then I also want to write :
	let rec h = t (f h)
(with t : ('a -> 'b) -> 'a -> 'b) but here, I can't afford to use
	let rec h x = t (f h) x
because t as some side effects and I need it to be evaluated only once.

Any idea on how to do that ?

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Stéphane Glondu]

Mathias Kende a écrit :
> [...] I also want to write :
> 	let rec h = t (f h)
> (with t : ('a -> 'b) -> 'a -> 'b) but here, I can't afford to use
> 	let rec h x = t (f h) x
> because t as some side effects and I need it to be evaluated only once.

Then what about:

let h =
  let tmp = ref (fun x -> assert false) in
  let res x = !tmp x in
  tmp :=
    (fun x ->
       let y = t (f res) in
       tmp := y;
       y x);
  res

Intuitively, the "tmp" reference caches the call to "t (f h)", but this
is otherwise the same technique as I gave earlier.


Cheers,

-- 
Stéphane

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Xavier Leroy]

Mathias Kende wrote:

> I need to write something like this :
> 
> 	let f f i = if i = 0 then 1 else i * f (i - 1)
> 	let rec g = f g
> 
> Of course the compiler won't let me write it (even if the OCaml type
> system is happy):
> 	"This kind of expression is not allowed as right-hand side of `let rec'"
In general, the best thing to do in this case is to switch to lazy
evaluation:

# let f f i = if i = 0 then 1 else i * Lazy.force f (i-1);;
val f : (int -> int) Lazy.t -> int -> int = <fun>
# let rec g' = lazy (f g');;
val g' : (int -> int) Lazy.t = <lazy>
# let g = Lazy.force g';;
val g : int -> int = <fun>
# g 10;;
- : int = 3628800

Lukasz Stafiniak wrote:

> While we are at it, what is the best way to convert a "straight" list
> into a cyclic list?
> 
> i.e. convert
> 
> let l = a::b::[]
> 
> into
> 
> let rec l = a::b::l
> 
> (for arbitrary length lists). (The answer I recall from the archives
> was using Obj.magic to mutate the [] in the original list).

Obj.magic is not part of the OCaml language :-)

Again, you can do that just fine using lazy lists instead of lists:

type 'a lazylist = 'a lazylist_content Lazy.t
and 'a lazylist_content = Nil | Cons of 'a * 'a lazylist

Hope this helps,

- Xavier Leroy

Re: [Caml-list] forbidden construct as right hand side of "let rec"

[Lukasz Stafiniak]

On Wed, Oct 28, 2009 at 5:52 PM, Xavier Leroy <Xavier.Leroy@inria.fr> wrote:
> Lukasz Stafiniak wrote:
>
>> While we are at it, what is the best way to convert a "straight" list
>> into a cyclic list?
>
> Again, you can do that just fine using lazy lists instead of lists:
>
> type 'a lazylist = 'a lazylist_content Lazy.t
> and 'a lazylist_content = Nil | Cons of 'a * 'a lazylist
>
> Hope this helps,
>
> - Xavier Leroy
>

Thank you, it makes sense!