"ocaml_beginners"::[] Closures: function passing itself as a parameter

Hello,

Can someone tell me how I can get a recursive function to be applied
passing itself as a parameter? In the example below (see print_r) I can
pass any number of function with no problem. Passing the function itself
as parameter however fails.

TIA,
Hugo F.

let rec print_val prn v =
print_endline ("Value "^v)

and print_var prn v =
print_endline "Var" ;
prn () v

and print_r prn v =
let f = prn (prn)
(*let f = prn (print_val)*)
(*let f = prn (fun _ v' -> print_endline (" ?? "^v') )*)
in
f v

let prn_1 v =
print_r (print_val) v

let prn_2 v =
print_r (print_var) v

let _ = prn_1 "1" ;
prn_2 "2"

Messages in this topic (1) Reply (via web post) | Start a new topic

.

On Fri, 13 Apr 2007, Hugo Ferreira wrote:

> Can someone tell me how I can get a recursive function to be applied
> passing itself as a parameter? In the example below (see print_r) I can
> pass any number of function with no problem. Passing the function itself
> as parameter however fails.

The problem is a basic typing issue that can be simplified to the same
problem as:

let f g = g g

What type should g have?

And even if you were to get this to work -- For example you can use
records and universal quantification to do the following (note, this
does *not* do what you want):

# type prn = { p : 'a 'b. 'a -> 'b -> unit };;
type prn = { p : 'a 'b. 'a -> 'b -> unit; }
# let print_r prn prn_f v = let f = prn.p prn_f in f v;;
val print_r : prn -> 'a -> 'b -> unit = <fun>;
# let pr a b = print_endline "Whoooo!";;
val pr : 'a -> 'b -> unit = <fun>;
# print_r { p = pr } pr "howdy";;
Whoooo!

-- then you'l have issues with print_var. This is because the type of
print_var is (unit -> 'a -> 'b) -> 'a -> 'b -- which is clear from the
definition. But what happens if you were to pass print_var into print_r?
Well, you do a let f = print_var print_var. But the first argument to
print_var is supposed to be unit -> 'a -> 'b, but you're giving it
something of type (unit -> 'a -> 'b) -> 'a -> 'b, and unit cannot unify
with unit -> 'a -> 'b. This is bad juju.

I'm not quite sure what you're trying to do here, but is seems like you
want a printer for a nested data structure. So I guess I have to ask why
you aren't using variants and pattern matching instead?

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy.&quot;

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Friday 13 April 2007 14:36, Hugo Ferreira wrote:
&gt; Hello,
&gt;
> Can someone tell me how I can get a recursive function to be applied
> passing itself as a parameter? In the example below (see print_r) I can
> pass any number of function with no problem. Passing the function itself
&gt; as parameter however fails.

Can you explain what you are trying to do, i.e. what the problem is?

When you say "pass itself as a parameter&quot;, do you mean something like:

# let rec f g x = g f x;;
val f : ('a -> 'b -> 'c) -> 'b -> 'c as 'a = <fun>;

in which case you need -rectypes enabled. Or you can box the function argument
in a variant with one constructor, e.g. a polymorphic variant:

# let rec f (`F g) x = g f x;;
val f : [< `F of 'a -> 'b -> 'c ] -> 'b -> 'c as 'a = <fun>;

However, I am not sure if this is what you should be using.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Messages in this topic (0) Reply (via web post) | Start a new topic

.

I noticed this weird signature :

James A. Crippen < j...%40unlambda.com">j...unlambda.com> ,-./-. Anchorage, Alaska,
Lambda Unlimited: Recursion 'R' Us | |/ | USA, 61.2069 N, 149.766 W,
Y = f.(x.f(xx)) (x.f(xx)) | | | Earth, Sol System,
Y(F) = F(Y(F)) _,-_/ Milky Way.

For example in comp.lang.lisp :
http://groups.google.fr/group/comp.lang.lisp/browse_thread/thread/62960f8ab9119ea0/5396e7eb879b735f?lnk=gst&q=Crippen&amp;rnum=1#5396e7eb879b735f

( With a frightening "unlambda" in address. )

I do not understand this "Y(F) = F(Y(F))&quot;. Maybe is it a same kind of question that Hugo asked ?

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Apr 15, 2007, at 4:30 PM, Fabrice Marchant wrote:

> I do not understand this "Y(F) = F(Y(F))&quot;. Maybe is it a same kind
> of question that Hugo asked ?

That's the Y fix-point combinator -- one way to implement recursion.
You can read a bit about it here <http://www.dreamsongs.com/NewFiles/
WhyOfY.pdf>.
Note that it's not directly implementable in OCaml due to the some
typing issue:

# let y = fun f -> (fun x -> f(x x)) (fun x -> f(x x));;
Characters 32-33:
let y = fun f -> (fun x -> f(x x)) (fun x -> f(x x));;
^
This expression has type 'a -> 'b but is here used with type 'a

There is a funky way around this using variants:

# type 'a t = T of ('a t -> 'a);;

type 'a t = T of ('a t -> 'a)
#
let fix = fun f ->
(fun (T x) -> (f (fun a -> x (T x) a)))
(T (fun (T x) -> (f (fun a -> x (T x) a))))
;;

val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>;

You can use this to create recursive functions without the rec keyword:

# let fact_ = fun fact -> fun i -> if i = 0 then 1 else i * fact (i-1);;
val fact_ : (int -> int) -> int -> int = <fun>;
# let fact = fix fact_;;
val fact : int -> int = <fun>;
# fact 5;;
- : int = 120

Of course, if you're willing to use the rec keyword, you can more
easily define fix:
# let rec fix' f x = f (fix' f) x;;
val fix' : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>;

But that's cheating...

(all of these examples came from the excellent paper: That about
wraps it up <>http://www.lfcs.inf.ed.ac.uk/reports/97/ECS-LFCS-97-375/)

William D. Neumann

"I eat T-bone steaks, I lift barbell plates, I'm sweeter than a
German chocolate cake. I'm the reflection of perfection, the number
one selection. I'm the man of the hour, the man with the power, too
sweet to be sour. The ladies' pet, the men's regret, where what you
see is what you get, and what you don't see, is better yet."

--Superstar Billy Graham

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Mon, 16 Apr 2007, Fabrice Marchant wrote:

> I noticed this weird signature :
>
> James A. Crippen < j...%40unlambda.com">j...unlambda.com> ,-./-. Anchorage, Alaska,
> Lambda Unlimited: Recursion 'R' Us | |/ | USA, 61.2069 N, 149.766 W,
> Y = f.(x.f(xx)) (x.f(xx)) | | | Earth, Sol System,
> Y(F) = F(Y(F)) _,-_/ Milky Way.
>;
> For example in comp.lang.lisp :
> http://groups.google.fr/group/comp.lang.lisp/browse_thread/thread/62960f8ab9119ea0/5396e7eb879b735f?lnk=gst&q=Crippen&amp;rnum=1#5396e7eb879b735f
>
> ( With a frightening "unlambda" in address. )
>
> I do not understand this "Y(F) = F(Y(F))&quot;. Maybe is it a same kind of question that Hugo asked ?

It's the Y combinator- effectively, how you introduce recursion into the
untyped lambda calculus.

If you want to learn more on this, I recommend reading "Types and
Programming Languages&quot;:
http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091/ref=pd_bbs_sr_1/104-6163213-2400720?ie=UTF8&s=books&qid=1176683849&sr=1-1

It's a great introduction to the underlying theory behind Ocaml, Haskell,
etc, both their type systems and their underlying model of computation.
But, I hasten to add, it is by no means *necessary* reading to be a fully
competent Ocaml programmer. And that it is heavy duty theory- exceedingly
well written and explained heavy duty theory, but heavy duty theory none
the less.

Brian

Messages in this topic (0) Reply (via web post) | Start a new topic

.

Hello,

William D. Neumann wrote:
&gt; On Fri, 13 Apr 2007, Hugo Ferreira wrote:
&gt;
>>; Can someone tell me how I can get a recursive function to be applied
>> passing itself as a parameter? In the example below (see print_r) I can
>> pass any number of function with no problem. Passing the function itself
&gt;> as parameter however fails.
&gt;
> The problem is a basic typing issue that can be simplified to the same
> problem as:
>
> let f g = g g
>
> What type should g have?
&gt;

This is what is baffling me. I define g elsewhere so I expected its type
to be defined.

let rec f g v =
let next = something v
in
g (g) next

and g h v =
let next = another_thing v
in
f (h) next

In other words "g&quot; and "h&quot; should have the same signature.

> And even if you were to get this to work -- For example you can use
> records and universal quantification to do the following (note, this
> does *not* do what you want):
&gt;
> # type prn = { p : 'a 'b. 'a -> 'b -> unit };;
> type prn = { p : 'a 'b. 'a -> 'b -> unit; }
> # let print_r prn prn_f v = let f = prn.p prn_f in f v;;
> val print_r : prn -> 'a -> 'b -> unit = <fun>;
> # let pr a b = print_endline "Whoooo!";;
> val pr : 'a -> 'b -> unit = <fun>;
> # print_r { p = pr } pr "howdy";;
> Whoooo!
>
> -- then you'l have issues with print_var. This is because the type of
> print_var is (unit -> 'a -> 'b) -> 'a -> 'b -- which is clear from the
> definition. But what happens if you were to pass print_var into print_r?
> Well, you do a let f = print_var print_var. But the first argument to
> print_var is supposed to be unit -> 'a -> 'b, but you're giving it
> something of type (unit -> 'a -> 'b) -> 'a -> 'b, and unit cannot unify
> with unit -> 'a -> 'b. This is bad juju.
&gt;

Yes, I had realized that using "prn ()" would make the first parameter
unit, hence the signature for print_var as you indicated. I then changed
that to: "prn (fun _ _ -> () )" but this did work either. I was actually
aiming for the type: ('a -> b' -> unit) -> b' -> unit. Still cannot
understand why I didn't get unit as the function output.

Anyway I think the real issue here is trying to make 'a be recursively
equivalent to ('a -> b' -> unit) which does not seem to be possible.

> I'm not quite sure what you're trying to do here, but is seems like you
> want a printer for a nested data structure. So I guess I have to ask why
> you aren't using variants and pattern matching instead?
>

I was trying to do a very simple thing (and as usually complicated it
unnecessarily). I was trying to iterate through a recursive structure
(predicates and literals) and apply a function to a given element (show
variable's values or variable's bindings). I simply wanted to
parametrize the function to be applied (show values or bindings). Here
is the solution:

let print_r prn v = prn v

let print_val v =
print_endline ("Value "^v)

let print_var v =
print_endline ("Var "^v)

let prn_1 v =
print_r (print_val) v

let prn_2 v =
print_r (print_var) v

let _ = prn_1 "1&quot; ;
prn_2 "2&quot;

My confusion stemmed from the fact that print_r is in fact a set of
mutually recursive functions (simplified here) and I made print_var and
print_val also mutually recursive. This is not necessary.

Thank you for the help.
Hugo F.

P.S.: I looked for information on universal quantification but the
manual seems to have very little on this. Anyone have additional pointers?

> William D. Neumann
>
> ---
>
> "There's just so many extra children, we could just feed the
> children to these tigers. We don't need them, we're not doing
> anything with them.
&gt;
> Tigers are noble and sleek; children are loud and messy.&quot;
>
> -- Neko Case
>;
> Life is unfair. Kill yourself or get over it.
> -- Black Box Recorder
>
>
> Archives up to November 11, 2006 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
> The archives of the very official ocaml list (the seniors' one) can be found at http://caml.inria.fr
> Attachments are banned and you're asked to be polite, avoid flames etc.
> Yahoo! Groups Links
&gt;
>
>
>

Messages in this topic (0) Reply (via web post) | Start a new topic

.

Hi,

Jon Harrop wrote:
&gt; On Friday 13 April 2007 14:36, Hugo Ferreira wrote:
&gt;> Hello,
&gt;>
&gt;> Can someone tell me how I can get a recursive function to be applied
>> passing itself as a parameter? In the example below (see print_r) I can
>> pass any number of function with no problem. Passing the function itself
&gt;> as parameter however fails.
&gt;
> Can you explain what you are trying to do, i.e. what the problem is?
>

As I explained to William Neumann I simply wanted to parametrize a
function to be applied to a recursive structure. Sort of an OO style
visitor pattern.

> When you say "pass itself as a parameter&quot;, do you mean something like:
&gt;
> # let rec f g x = g f x;;
> val f : ('a -> 'b -> 'c) -> 'b -> 'c as 'a = <fun>;
>

No, more like:

# let rec f g x = g (g) x ;;
This expression has type 'a -> 'b -> 'c but is here used with type 'a

&gt; in which case you need -rectypes enabled.

Ha.. I see, with -rectypes I get:

# let rec f g x = g (g) x ;;
val f : ('a -> 'b -> 'c as 'a) -> 'b -> 'c = <fun>;

So this seems to "solve" the "real" issue I had with the function
definition.

> Or you can box the function argument in a variant with one constructor,
> e.g. a polymorphic variant:
>
> # let rec f (`F g) x = g f x;;
> val f : [< `F of 'a -> 'b -> 'c ] -> 'b -> 'c as 'a = <fun>;
>

Interesting way to get the "'c as 'a". An alternative solution without
the use of "-rectype".

> However, I am not sure if this is what you should be using.
&gt;

I you may have seen in my previous post the solution is much simpler:
just declare/define the "visiting" functions after the mutually
recursive visiting functions.

Appreciate the feedback. It has allowed me to learn a little more about
Caml.

Hugo F.

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Monday 16 April 2007 08:38, Hugo Ferreira wrote:
&gt; # let rec f g x = g (g) x ;;
> val f : ('a -> 'b -> 'c as 'a) -> 'b -> 'c = <fun>;

Note that the parentheses are superfluous.

>; I you may have seen in my previous post the solution is much simpler:
> just declare/define the "visiting" functions after the mutually
> recursive visiting functions.

Yes. I just did exactly this in the context of a purely functional scene graph
implementation. I defined an "abstract" scene graph with a higher-order
function to traverse it that accepts the functions to be applied to nodes and
leaves. Then I defined a "concrete" scene graph in terms of that, defining a
renderer by traversing the scene graph, applying transformations at transform
nodes and drawing the leaves.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
OCaml for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Messages in this topic (0) Reply (via web post) | Start a new topic

.

Thanks William and Brian ! 'll see if possible to send a private mail about Y function.

And sorry Hugo... Should have submit a new topic for this question that doesn't help a lot for your subject.

Best Regards

Messages in this topic (0) Reply (via web post) | Start a new topic

.