117 views

Skip to first unread message

Oct 22, 2009, 6:22:54 PM10/22/09

to caml...@yquem.inria.fr

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

Oct 22, 2009, 6:34:48 PM10/22/09

to mat...@kende.fr, caml...@yquem.inria.fr

Mathias Kende a écrit :

> let rec g = f g

> let rec g = f g

What about:

let rec g x = f g x

--

Stéphane

Oct 22, 2009, 7:10:42 PM10/22/09

to caml-list

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

into a cyclic 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

_______________________________________________

Oct 23, 2009, 11:39:32 AM10/23/09

to caml-list

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"

Oct 23, 2009, 12:15:11 PM10/23/09

to caml...@inria.fr

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.

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 :

Oct 23, 2009, 1:51:19 PM10/23/09

to Marc de Falco, caml...@inria.fr

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.

> 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

Oct 25, 2009, 10:12:00 AM10/25/09

to Stéphane Glondu, caml...@yquem.inria.fr

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

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 ?

Oct 25, 2009, 11:04:18 AM10/25/09

to Mathias Kende, caml...@yquem.inria.fr

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.

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

Oct 28, 2009, 12:52:36 PM10/28/09

to mat...@kende.fr, caml...@yquem.inria.fr

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

Oct 28, 2009, 6:45:15 PM10/28/09

to caml-list

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?

>

> 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

>

>

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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu