## help regarding higher order functions

Expand Messages
• hi everyone, I am a ocaml newbie, someone plzz provide the solutions of the following problems...... 1. Write a function multimap flst xlst which takes a list
Message 1 of 5 , Feb 16, 2006
• 0 Attachment
hi everyone,
I am a ocaml newbie, someone plzz provide the solutions of the following problems......

1. Write a function multimap flst xlst which takes a list of functions flst and maps them, one at a time, from right to left, to the list xlst.

# let multimap flst xlst = ...
val multimap : (a -> a) list -> a list -> a list = <fun>
# multimap [( (+) 1); ( ( * ) 2); ( (+) 20) ] [2;3;4;5];;
- : int list = [45; 47; 49; 51]

2. Write a function rsum lst which computes the running sum of the list lst. A running sum of a list is defined as:
[x1; x2; x3; · · · ; xn] = [0; x1; x1 + x2; x1 + x2 + x3; · · · ; x1 + x2 + x3 + · · · + xn]

You may use List.rev for this problem.

# let rsum lst = ...
val rsum : int list -> int list = <fun>
# rsum [1;2;3;4;5];;
- : int list = [0; 1; 3; 6; 10; 15]

Thanks.....

---------------------------------
Yahoo! Autos. Looking for a sweet ride? Get pricing, reviews, & more on new and used cars.

[Non-text portions of this message have been removed]
• It is rare that one sees a please do my homework for me posting any more, but yours appears to be one. You are not likely to get the response you hope for;
Message 2 of 5 , Feb 16, 2006
• 0 Attachment
It is rare that one sees a "please do my homework for me" posting any
more, but yours appears to be one. You are not likely to get the
response you hope for; some responses may be, to your eye, rude.

-- F

On 16 Feb 2006, at 10:07 AM, good boy wrote:

> hi everyone,
> I am a ocaml newbie, someone plzz provide the
> solutions of the following problems......
>
>
> 1. Write a function multimap flst xlst which takes a list of
> functions flst and maps them, one at a time, from right to left, to
> the list xlst.
>
> # let multimap flst xlst = ...
> val multimap : (’a -> ’a) list -> ’a list -> ’a list = <fun>
> # multimap [( (+) 1); ( ( * ) 2); ( (+) 20) ] [2;3;4;5];;
> - : int list = [45; 47; 49; 51]
>
> 2. Write a function rsum lst which computes the running sum of
> the list lst. A running sum of a list is defined as:
> [x1; x2; x3; · · · ; xn] = [0; x1; x1 + x2; x1 + x2 + x3; · · · ;
> x1 + x2 + x3 + · · · + xn]
>
> You may use List.rev for this problem.
>
> # let rsum lst = ...
> val rsum : int list -> int list = <fun>
> # rsum [1;2;3;4;5];;
> - : int list = [0; 1; 3; 6; 10; 15]
>
> Thanks.....
• My apologies to the OP and the list; I meant my last reply to be private. -- F
Message 3 of 5 , Feb 16, 2006
• 0 Attachment
My apologies to the OP and the list; I meant my last reply to be
private.

-- F
• ... While it is the case that the please do my homework for me type of posts are frowned upon, it is still possible to give some help to steer the poster in
Message 4 of 5 , Feb 16, 2006
• 0 Attachment
On Thu, 16 Feb 2006, Fritz Anderson wrote:

> It is rare that one sees a "please do my homework for me" posting any
> more, but yours appears to be one. You are not likely to get the
> response you hope for; some responses may be, to your eye, rude.

While it is the case that the "please do my homework for me" type of posts
are frowned upon, it is still possible to give some help to steer the
poster in the right direction without simply supplying answers so they
might learn a bit of OCaml in the process. And so...

You would be well served by learning the dickens out of the higer order
functions map, iter, fold_left, and fold right (particularly the folds, as
you can implement map and iter using them). Read, for example, the
standard library implementation of the List module. To give you an idea
of what they do, consider List.fold_left. Its type is
('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

What this means is that we supply three things to fold_left:
1: a function that takes a value of type 'a, a value of type 'b (which
could be, but doesn't have to be, the same as 'a), call it f;
2: a base value of type 'a, call it base;
3: a list of items of type 'b, represent this as [l0; l1; l2; ...; ln]

What fold_left does for us then is to compute:
f(f (...f (f (f base l0) l1) l2) ... ln-1) ln).

Look at the manual to see how fold_right differs.

How can we use this? Well, a very simple example is to us it to compute
the sum of a list of numbers:

# let sum lst = List.fold_left (fun b v -> b + v) 0 lst;;
val sum : int list -> int = <fun>
# sum [1; 2; 3; 4; 5];;
- : int = 15

OK, it worked, but it wasn't so informative as to what is going on. Let's
have it tell us what it's doing under the covers (pay attention here, this
may be of use):

# let verbose_sum l =
List.fold_left
(fun b v ->
Printf.printf "Adding b: %d and v: %d to get accumulated value:
%d\n" b v (b+v); b + v)
0
l;;
val verbose_sum : int list -> int = <fun>
# verbose_sum [1; 2; 3; 4; 5];;
Adding b: 0 and v: 1 to get accumulated value: 1
Adding b: 1 and v: 2 to get accumulated value: 3
Adding b: 3 and v: 3 to get accumulated value: 6
Adding b: 6 and v: 4 to get accumulated value: 10
Adding b: 10 and v: 5 to get accumulated value: 15
- : int = 15

Of course, the types 'a and 'b can be any types, not just single values
like ints. We could use a 'b that is some kind of list. Like if we
wanted to implement map using a fold. Given the function, f, that we want
to map over the list, l, we can try the following: given the current
contents of the mapped list (call it b), and the head of the list to be
mapped (call it v), we apply f to v, and cons it onto b:
# let mymap f l =
List.fold_left (fun b v -> (f v)::b) [] l;;
val mymap : ('a -> 'b) -> 'a list -> 'b list = <fun>

Well, it's got the same signature as List.map, so maybe it works. Let's
try it:

# mymap (fun x -> 10 * x) [1; 2; 3; 4; 5];;
- : int list = [50; 40; 30; 20; 10]

Whoops, not quite right (can you see why)? We will need to reverse the
resulting list to get what we want (or just use fold_right -- can you
figure out why/how?).

So bottom line, fold_left takes a function, f, whose parameters are an
accumulator of some sort, and some value that comes from a list. It
then pulls the head off of the list, applies f to the current value of the
accumulator and this head to get the next value of the accumulator (using
the supplied base the first time through), and then computes the fold
using the new accumulator value and the tail of the list, recursing like
this until the supplied list is empty, where it just returns the value of
the accumulator. fold_right is similar, but different.

Given that, you just need to look at your problems in the right way. The
second problem is easier, as it is just a more or less simple
accumulation. The first one is a bit trickier, as it is an accumulation
of accumulations. Now then, go forth and write some code. Learn the
essence of fold, and you will have learned an awful lot.

William D. Neumann

>> 1. Write a function multimap flst xlst which takes a list of
>> functions flst and maps them, one at a time, from right to left, to
>> the list xlst.
>>
>> # let multimap flst xlst = ...
>> val multimap : (�a -> �a) list -> �a list -> �a list = <fun>
>> # multimap [( (+) 1); ( ( * ) 2); ( (+) 20) ] [2;3;4;5];;
>> - : int list = [45; 47; 49; 51]
>>
>> 2. Write a function rsum lst which computes the running sum of
>> the list lst. A running sum of a list is defined as:
>> [x1; x2; x3; � � � ; xn] = [0; x1; x1 + x2; x1 + x2 + x3; � � � ;
>> x1 + x2 + x3 + � � � + xn]
>>
>> You may use List.rev for this problem.
>>
>> # let rsum lst = ...
>> val rsum : int list -> int list = <fun>
>> # rsum [1;2;3;4;5];;
>> - : int list = [0; 1; 3; 6; 10; 15]

---

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

-- Neko Case

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

[Non-text portions of this message have been removed]
• ... Great answer! I would just add that another useful learning exercise is to reimplement some of the HOFs from the standard library. List.map is a good one
Message 5 of 5 , Apr 2, 2006
• 0 Attachment
William D. Neumann wrote:

> While it is the case that the "please do my homework for me" type of posts
> are frowned upon, it is still possible to give some help to steer the
> poster in the right direction without simply supplying answers so they
> might learn a bit of OCaml in the process. And so...

Great answer! I would just add that another useful learning exercise is
to reimplement some of the HOFs from the standard library. List.map is a