Loading ...
Sorry, an error occurred while loading the content.

help regarding higher order functions

Expand Messages
  • good boy
    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]
    • Fritz Anderson
      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.....
      • Fritz Anderson
        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
        • William D. Neumann
          ... 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]
          • Matt Gushee
            ... 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
              good one to start with.

              --
              Matt Gushee
              The Reluctant Geek: http://matt.gushee.net/rg/
            Your message has been successfully submitted and would be delivered to recipients shortly.