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

_______________________________________________
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

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

[Damien Guichard-2]

Some parts of this message have been removed. Learn more about Nabble's security policy.

 

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

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

_______________________________________________
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

[blue storm]

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

_______________________________________________
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

[Mathias Kende]

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

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

_______________________________________________
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

[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

_______________________________________________
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

[Lukasz Stafiniak]

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

_______________________________________________
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