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

_______________________________________________
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

[Stéphane Glondu]

Mathias Kende a écrit :

> let rec g = f g

What about:

let rec g x = f g x

--
Stéphane

[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 <st...@glondu.net> wrote:
> Mathias Kende a �crit :
>> � � � let rec g = f g

>
> What about:
>
> �let rec g x = f g x

_______________________________________________

[Damien Guichard]

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"

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

[blue storm]

On Fri, Oct 23, 2009 at 6:14 PM, Marc de Falco <marc.d...@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

[Mathias Kende]

On Fri, 23 Oct 2009 00:34:29 +0200, Stéphane Glondu <st...@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 ?

[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

[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

[Lukasz Stafiniak]

On Wed, Oct 28, 2009 at 5:52 PM, Xavier Leroy <Xavier...@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!