"ocaml_beginners"::[] Re: how to read this function?

If (fold glue lfval l)
is equivalent to: (((fold glue) lfval) l)
Q1. That only means (fold glue) is being evaluated first, correct?

But my main question is not about "fold" but the "glue".
glue = (fun l v r -> l + v + r)
which means glue accepts three int parameters not two but the function
(fold glue lfval l) has only two parameters passed to "glue".

Q2. Where is the third parameter comes from?
Unless "l" gets transform into (v,Leaf) where v and Leaf are integers
addition can not be done.

Thanks a lot.

MH

--- In ocaml_beginners%40yahoogroups.com">ocaml_beginnersyahoogroups.com, "Christopher L Conway"
<cconway...> wrote:
&gt;
> On 8/3/07, cugf_0956 <mzouk...> wrote:
&gt; > I am looking through some samples and I found this one, could you
> > please explain it to me:
> > let rec fold glue lfval tr = (* Divide/conquer/glue on trees *)
> > match tr with
>; > Leaf -> lfval
&gt; > | Node(l,v,r) -> glue (fold glue lfval l) v (fold glue lfval r);;
>; > let sumlist tr = fold (fun l v r -> l + v + r) 0 tr;;
>; >
>; > If I pass int_tree datatype, which is
> > let int_tree =
> > Node(Node(Leaf, 2, Leaf), 4,
> > Node(Node(Leaf, 1, Node(Leaf, 5, Leaf)), 6,
> > Node(Leaf, 3, Leaf)));;
> > I get result = 21:int
&gt; >
>; > It looks like glue function that is defined as
> > fun l v r -> l + v + r
> > takes three parameters while in
> > glue( fold glue lfval l) v (fold glue lfval r);;
>; > inside parenthesis, it takes only two.
>; > Does this mean that (glue lfval l) doesn't get evaluated until
&gt; > Node "l&quot; is unrolles till the end of the bintree and the only values
&gt; > left are a value of the Node and a Leaf?
&gt; > So in a sense I have to read (glue lfval l) as (glue lfval v Leaf)?
&gt;
> (fold glue lfval l)
> is equivalent to: (((fold glue) lfval) l)
> which is not: (fold (glue (lfval l)))
>; or, as you have it: (fold (glue lfval l))
>
> Try giving fold just a single argument in the top-level and see what
happens.
>;
> Regards,
> Chris
&gt;
> >
>; > Thanks.
> >
>; >
>; >
>; >
>; > 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; >
>; >
>; >
>; >
>; >
>;

•  6
  New Members

• Computer telephony
• Portable computer
• Computer telephony integration
• Computer telephony integration cti
• Portable computer cart

On 8/4/07, cugf_0956 < mzouk%40altavista.com">mzoukaltavista.com> wrote:
&gt; If (fold glue lfval l)
> is equivalent to: (((fold glue) lfval) l)
> Q1. That only means (fold glue) is being evaluated first, correct?
>
>; But my main question is not about "fold" but the "glue".
&gt; glue = (fun l v r -> l + v + r)
> which means glue accepts three int parameters not two but the function
> (fold glue lfval l) has only two parameters passed to "glue".

lfval and l in (fold glue lfval l) are parameters to fold, not
parameters to glue. Function application associates to the left.

The type of fold is (('a -> 'a -> 'a -> 'a) -> 'a -> 'a tree -> 'a), so
the type of (fold glue) is ('a -> 'a tree -> 'a), and
the type of (fold glue lfval) is ('a tree -> 'a), and
the type of (fold glue lfval l) is 'a.

&gt; Q2. Where is the third parameter comes from?
&gt; Unless "l&quot; gets transform into (v,Leaf) where v and Leaf are integers
> addition can not be done.

The only place that glue is invoked is the match case Node(l,v,r):
glue (fold glue lfval l) v (fold glue lfval r)
which has three parameters

If Node(l,v,r) has type 'a tree, then
the type of (fold glue lfval l) is 'a, and
the type of v is 'a, and
the type of (fold glue lfval r) is 'a, so
the type of glue is ('a -> 'a -> 'a -> 'a), as we had above.

Regards,
Chris

>
&gt; Thanks a lot.
>;
> MH
>
>
&gt; --- In ocaml_beginners%40yahoogroups.com">ocaml_beginnersyahoogroups.com, "Christopher L Conway&quot;
> <cconway...> wrote:
&gt; >
>; > On 8/3/07, cugf_0956 <mzouk...> wrote:
&gt; > > I am looking through some samples and I found this one, could you
> > > please explain it to me:
> > > let rec fold glue lfval tr = (* Divide/conquer/glue on trees *)
> > > match tr with
>; > > Leaf -> lfval
&gt; > > | Node(l,v,r) -> glue (fold glue lfval l) v (fold glue lfval r);;
>; > > let sumlist tr = fold (fun l v r -> l + v + r) 0 tr;;
>; > >
>; > > If I pass int_tree datatype, which is
> > > let int_tree =
> > > Node(Node(Leaf, 2, Leaf), 4,
> > > Node(Node(Leaf, 1, Node(Leaf, 5, Leaf)), 6,
> > > Node(Leaf, 3, Leaf)));;
> > > I get result = 21:int
&gt; > >
>; > > It looks like glue function that is defined as
> > > fun l v r -> l + v + r
> > > takes three parameters while in
> > > glue( fold glue lfval l) v (fold glue lfval r);;
>; > > inside parenthesis, it takes only two.
>; > > Does this mean that (glue lfval l) doesn't get evaluated until
&gt; > > Node "l&quot; is unrolles till the end of the bintree and the only values
&gt; > > left are a value of the Node and a Leaf?
&gt; > > So in a sense I have to read (glue lfval l) as (glue lfval v Leaf)?
&gt; >
>; > (fold glue lfval l)
> > is equivalent to: (((fold glue) lfval) l)
> > which is not: (fold (glue (lfval l)))
>; > or, as you have it: (fold (glue lfval l))
> >
>; > Try giving fold just a single argument in the top-level and see what
>; happens.
> >
>; > Regards,
> > Chris
&gt; >
>; > >
>; > > Thanks.
> > >
>; > >
>; > >
>; > >
>; > > 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
&gt; etc.
>; > > Yahoo! Groups Links
&gt; > >
>; > >
>; > >
>; > >
>; > >
>; >
>;
>
>
>
> 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;
>
>
>;
>

On Saturday 04 August 2007 19:59:00 cugf_0956 wrote:
&gt; If (fold glue lfval l)
> is equivalent to: (((fold glue) lfval) l)
> Q1. That only means (fold glue) is being evaluated first, correct?

Yes, exactly. Note that this is _not_ an application of "glue". This is just
passing the "glue" function as an argument to "fold".

> But my main question is not about "fold" but the "glue".
&gt; glue = (fun l v r -> l + v + r)
> which means glue accepts three int parameters not two but the function
> (fold glue lfval l) has only two parameters passed to "glue".
&gt;
> Q2. Where is the third parameter comes from?
&gt; Unless "l&quot; gets transform into (v,Leaf) where v and Leaf are integers
> addition can not be done.

No. As you just said "fold glue lfval l" does not even apply "glue", so you
cannot tell from this alone what the arity of "glue" is.

The "glue" function will actually be applied inside the body of the
higher-order "fold" function.

>From the "fold" that you gave, we have something like:

# type 'a t = Leaf | Node of 'a t * 'a * 'a t;;
type 'a t = Leaf | Node of 'a t * 'a * 'a t
# let rec fold glue lfval tr = (* Divide/conquer/glue on trees *)
match tr with
Leaf -> lfval
| Node(l,v,r) -> glue (fold glue lfval l) v (fold glue lfval r);;
val fold : ('a -> 'b -> 'a -> 'a) -> 'a -> 'b t -> 'a = <fun>;

We know that "glue" is used as the first argument to "fold" and, from the
signature of the "fold" function, this means "glue" must have a type that
unifies with:

'a -> 'b -> 'a -> 'a

because that is the type of the first argument of "fold".

Therefore, the glue function will actually be applied to three arguments. You
can see this by looking at the application of the "glue" function
inside "fold":

glue (fold glue lfval l) v (fold glue lfval r)

The "glue" function is applied to three arguments.

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

•  5
  New Members

• Computer telephony
• Portable computer
• Computer telephony integration
• Computer telephony integration cti
• Portable computer cart