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

Re: "ocaml_beginners"::[] match or function (Was: Combining the elements of a list)

Expand Messages
  • Johann Spies
    ... Thanks for this. It prompts me to ask a question that about something I never fully understood: When to use (like you did in this example) function and
    Message 1 of 19 , Jul 7, 2005
    • 0 Attachment
      > Here is a possible solution:
      >
      > let rec combine x = function
      > [] -> []
      > | h :: t -> (x, h) :: (combine x t);;
      >
      > let rec choose_two = function
      > [] | [_] -> []
      > | h :: t -> (choose_two t) @ (combine h t);;
      >

      Thanks for this. It prompts me to ask a question that about something
      I never fully understood: When to use (like you did in this example)
      'function' and when 'match x with'...

      I can rewrite your "combine" function like this:

      let rec kombine x l = match l with
      [] -> []
      | h :: t -> (x, h) :: (kombine x t);;

      and it seems to do exactly the same.

      Regards
      Johann
      --
      Johann Spies Telefoon: 021-808 4036
      Informasietegnologie, Universiteit van Stellenbosch

      "Trust in the Lord with all your heart, and do not
      lean on your own understanding."
      Proverbs 3:5


      Vrywaring: Jy hoef eintlik net die e-pos self te gelees het. :)
      Disclaimer: If you are reading this you are wasting your time :)
    • Radu Grigore
      ... I d say it s a matter of style. Personaly I decide on case by case basis and whenever I m in doubt I use function . Here is an example where I would use
      Message 2 of 19 , Jul 7, 2005
      • 0 Attachment
        --- Johann Spies <jspies@...> wrote:

        > When to use (like you did in this example)
        > 'function' and when 'match x with'...

        I'd say it's a matter of style. Personaly I decide on case by case
        basis and whenever I'm in doubt I use "function". Here is an example
        where I would use "match":

        let combine_in_list x = List.map (fun y -> x :: y);;
        let rec choose_n n lst = begin
        assert (n >= 0);
        match (n, lst) with
        (0, _) -> [[]]
        | (_, []) -> []
        | (n, h :: t) ->
        (combine_in_list h (choose_n (n - 1) t)) @ (choose_n n t)
        end;;

        Two reasons: (1) I wanted to put an assert on n, and (2) there is
        more than one argument on which I wish to do a match.

        regards,
        radu


        __________________________________________________
        Do You Yahoo!?
        Tired of spam? Yahoo! Mail has the best spam protection around
        http://mail.yahoo.com
      • Remi Vanicat
        ... And i prefer the second because one read more easily the number of argument. It is a matter of style and taste
        Message 3 of 19 , Jul 7, 2005
        • 0 Attachment
          2005/7/7, Richard Jones <rich@...>:
          >
          > Anyway, function and match can be used equivalently to each other.
          > The following functions are identical:
          >
          > let f = function
          > | Some i -> printf "Some %d\n" i
          > | None -> printf "None\n"
          >
          > let f x =
          > match x with
          > | Some i -> printf "Some %d\n" i
          > | None -> printf "None\n"
          >
          > I tend to prefer the first form because it's more concise.

          And i prefer the second because one read more easily the number of
          argument. It is a matter of style and taste
        • Richard Jones
          ... I think this deserves a section in http://www.ocaml-tutorial.org/ - the difference between fun, function and match. Anyway, function and match can be used
          Message 4 of 19 , Jul 7, 2005
          • 0 Attachment
            On Thu, Jul 07, 2005 at 10:40:42AM +0200, Johann Spies wrote:
            > Thanks for this. It prompts me to ask a question that about something
            > I never fully understood: When to use (like you did in this example)
            > 'function' and when 'match x with'...

            I think this deserves a section in http://www.ocaml-tutorial.org/ -
            the difference between fun, function and match.

            Anyway, function and match can be used equivalently to each other.
            The following functions are identical:

            let f = function
            | Some i -> printf "Some %d\n" i
            | None -> printf "None\n"

            let f x =
            match x with
            | Some i -> printf "Some %d\n" i
            | None -> printf "None\n"

            I tend to prefer the first form because it's more concise.

            Rich.

            --
            Richard Jones, CTO Merjis Ltd.
            Merjis - web marketing and technology - http://merjis.com
            Team Notepad - intranets and extranets for business - http://team-notepad.com
          • Eray Ozkural
            I would like to note that this might be a perfect problem to demonstrate use of lazy evaluation. In most applications of the combination function we are merely
            Message 5 of 19 , Jul 11, 2005
            • 0 Attachment
              I would like to note that this might be a perfect problem to
              demonstrate use of lazy evaluation. In most applications
              of the combination function we are merely interested in
              iterating or mapping the elements of the combination
              list, without actually generating anything. Good for a
              tutorial?

              On 7/7/05, Lecca Paola <lecca@...> wrote:
              >
              > Dear all,
              > I'm dealing now with the problem of finding all the combinations between
              > the elements of a list of lists. For example, suppose to have
              >
              > let l1 = [ ["a"; "b"]; ["c"; "d"]; ["e"; "f"]; ["h"; "k"] ];;
              >
              > I wish to combine with the function List.combine, the first element of l1
              > with each of the remaining elements, then I want to combine the second
              > element of l1 with each of the successive elements, and so on.
              > The final result I would like to obtain looks like the following
              >
              > [("a", "c"); ("b", "d")]; [("a", "e"); ("b", "f")]; [("a", "h"); ("b",
              > "k")]; [("c", "e"); ("d", "f")]; [("c", "h"); ("d", "k")]; [("e", "h");
              > ("f", "k")] ]
              >
              > However, I'm not able to find a strategy to combine an element of l1 with
              > another element that is not the next, i. e. how to perform the combination
              > between ["a", "b"] and ["e"; "f"], for instance ?
              >
              > Using the function "numberd_list" suggested by Richard Jones I tried to
              > write the following
              >
              > (* numbering a list *)
              > let numbered_list xs =
              > let rec loop n = function
              > | [] -> []
              > | x :: xs -> (n, x) :: loop (succ n) xs
              > in
              > loop 1 xs;;
              >
              >
              > (* get the next element of a given element of a numbered list *)
              > (* the input of this function is the output of the numbered_list *)
              > (* function *)
              >
              > let list_next elt l =
              > match l with
              > [] -> []
              > |_ -> List.nth l ((first elt))
              > ;;
              >
              > let rec combine_in l =
              > let nl = numbered_list l in
              > match nl with
              > [] -> []
              > | nl'::nl ->
              >
              > (List.combine (second nl') (list_next nl' l)):: combine_in l
              > ;;
              >
              > combine_in should combine al least each element with the next one, but
              > also this simple attempt fails.
              >
              > Thanks for your attention,
              > Paola.
              >
              >
              > Archives up to September 30, 2004 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
              >
              >
              >
              >
              >
              >
              >


              --
              Eray Ozkural (exa), PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara
              http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://www.malfunct.com
              Uludag Project: www.uludag.org.tr KDE Project: http://www.kde.org
            • Jon Harrop
              ... I meant to reply to this sooner... Firstly, IIRC performance can be affected by this so you want to avoid using function to match over the last argument of
              Message 6 of 19 , Jul 11, 2005
              • 0 Attachment
                On Thursday 07 July 2005 11:37, Richard Jones wrote:
                > ... function and match can be used equivalently to each other.
                > The following functions are identical:
                >
                > let f = function
                >
                > | Some i -> printf "Some %d\n" i
                > | None -> printf "None\n"
                >
                > let f x =
                > match x with
                >
                > | Some i -> printf "Some %d\n" i
                > | None -> printf "None\n"
                >
                > I tend to prefer the first form because it's more concise.

                I meant to reply to this sooner...

                Firstly, IIRC performance can be affected by this so you want to avoid using
                function to match over the last argument of a multi-argument function.

                Secondly, function is an even better substitute for a match wrapped in an
                anonymous function:

                List.map (fun x -> match x with Some _ -> 1 | None -> 0) l

                List.map (function Some _ -> 1 | None -> 0) l

                --
                Dr Jon D Harrop, Flying Frog Consultancy Ltd.
                Technical Presentation Software
                http://www.ffconsultancy.com/products/presenta
              • Radu Grigore
                ... Yes. ____________________________________________________ Sell on Yahoo! Auctions � no fees. Bid on great items. http://auctions.yahoo.com/
                Message 7 of 19 , Jul 11, 2005
                • 0 Attachment
                  --- Eray Ozkural <erayo@...> wrote:

                  > Good for a tutorial?

                  Yes.





                  ____________________________________________________
                  Sell on Yahoo! Auctions – no fees. Bid on great items.
                  http://auctions.yahoo.com/
                • Remi Vanicat
                  2005/7/11, Jon Harrop : [...] ... No. both let f a b = function ... and let f a b c x = match x with ... are completly equivalent in the
                  Message 8 of 19 , Jul 11, 2005
                  • 0 Attachment
                    2005/7/11, Jon Harrop <jon@...>:
                    [...]
                    > I meant to reply to this sooner...
                    >
                    > Firstly, IIRC performance can be affected by this so you want to avoid using
                    > function to match over the last argument of a multi-argument function.

                    No. both
                    let f a b = function
                    | Some i -> printf "%d %d Some %d\n" a b i
                    | None -> printf "%d %d None\n" a b

                    and

                    let f a b c x =
                    match x with
                    | Some i -> printf "%d %d Some %d\n" a b i
                    | None -> printf "%d %d None\n" a b

                    are completly equivalent in the point of vue of the caml compiler.
                    I prefer the former because all argument are treated the same, so one
                    imediatly that this a a 4 argument function, but they do are strictly
                    equivalent.
                  • Remi Vanicat
                    ... I obviously meant let f a b x = match x with ... and so it is a 3 argument function.
                    Message 9 of 19 , Jul 11, 2005
                    • 0 Attachment
                      2005/7/11, Remi Vanicat <remi.vanicat@...>:

                      > No. both
                      > let f a b = function
                      > | Some i -> printf "%d %d Some %d\n" a b i
                      > | None -> printf "%d %d None\n" a b
                      >
                      > and
                      >
                      > let f a b c x =
                      > match x with
                      > | Some i -> printf "%d %d Some %d\n" a b i
                      > | None -> printf "%d %d None\n" a b

                      I obviously meant
                      let f a b x =
                      match x with
                      | Some i -> printf "%d %d Some %d\n" a b i
                      | None -> printf "%d %d None\n" a b

                      and so it is a 3 argument function.
                    • Jon Harrop
                      ... Do you mean you prefer the latter (rather than the former) because it makes it more obvious that it is a 3 argument function? I don t know that the
                      Message 10 of 19 , Jul 11, 2005
                      • 0 Attachment
                        On Monday 11 July 2005 19:19, Remi Vanicat wrote:
                        > No. both
                        > let f a b = function
                        >
                        > | Some i -> printf "%d %d Some %d\n" a b i
                        > | None -> printf "%d %d None\n" a b
                        >
                        > and
                        >
                        > let f a b x =
                        > match x with
                        >
                        > | Some i -> printf "%d %d Some %d\n" a b i
                        > | None -> printf "%d %d None\n" a b
                        >
                        > are completly equivalent in the point of vue of the caml compiler.
                        > I prefer the former because all argument are treated the same, so one
                        > imediatly that this a a 4 argument function, but they do are strictly
                        > equivalent.

                        Do you mean you prefer the latter (rather than the former) because it makes it
                        more obvious that it is a 3 argument function?

                        I don't know that the compiler will definitely treat those the same way but
                        you are quite right to expect that it should. I've just done some tests and
                        it seems that the assembler outputs are equivalent and the performance is not
                        significantly different.

                        Looks like I over-simplified my example. Let me try again. Here are two code
                        snippets which do the same thing:

                        let rec eval state =
                        let eval = eval state in
                        function
                        `Int i -> i
                        | `Var s -> List.assoc s state
                        | `Add (a, b) -> eval a + eval b;;

                        let rec eval state t =
                        let eval = eval state in
                        match t with
                        `Int i -> i
                        | `Var s -> List.assoc s state
                        | `Add (a, b) -> eval a + eval b;;

                        I factored out the common subexpression "eval state" to shrink the code.
                        However, the latter version is significantly faster (IIRC).

                        I think the reason is that the subtle difference in order of evaluation causes
                        ocamlopt to make an unnecessary closure in the first case. I believe that
                        optiming away this closure would be very difficult. It probably requires a
                        proof that "eval" is purely functional, for a start.

                        --
                        Dr Jon D Harrop, Flying Frog Consultancy Ltd.
                        Technical Presentation Software
                        http://www.ffconsultancy.com/products/presenta
                      • Remi Vanicat
                        ... Yes I do. English is not my native language, and sometimes I realy do big mistake... ... [...] ... [...] Those two example must not be compiled in the same
                        Message 11 of 19 , Jul 11, 2005
                        • 0 Attachment
                          2005/7/11, Jon Harrop <jon@...>:

                          >
                          > Do you mean you prefer the latter (rather than the former) because it makes it
                          > more obvious that it is a 3 argument function?

                          Yes I do. English is not my native language, and sometimes I realy do
                          big mistake...

                          > Looks like I over-simplified my example. Let me try again. Here are two code
                          > snippets which do the same thing:


                          >
                          > let rec eval state =
                          > let eval = eval state in
                          > function

                          [...]

                          >
                          > let rec eval state t =
                          > let eval = eval state in
                          [...]

                          Those two example must not be compiled in the same way, because in
                          case of partial application they should not do the same thing (imagine
                          that (eval state) print somethig for example). So they are not
                          equivalent anymore. More precisely, what is equivalent is :

                          let f x y z = match z with ...
                          and
                          let f x y = function ...

                          with nothing between the = and the match/the function.
                        • Jon Harrop
                          ... They are not compiled in the same way. I do not believe that they must not be compiled in the same way, as you say, in this particular case. ... No, I
                          Message 12 of 19 , Jul 11, 2005
                          • 0 Attachment
                            On Monday 11 July 2005 20:27, Remi Vanicat wrote:
                            > Those two example must not be compiled in the same way,

                            They are not compiled in the same way. I do not believe that they "must not"
                            be compiled in the same way, as you say, in this particular case.

                            > because in
                            > case of partial application they should not do the same thing
                            > (imagine that (eval state) print somethig for example). So they are not
                            > equivalent anymore...

                            No, I think they really are equivalent. It is just that proving this
                            equivalence is suddenly much harder and is beyond the capability of ocamlopt.

                            Note that I was careful to choose a self-contained example where the recursive
                            "eval" function clearly doesn't print anything (or have any side effects). I
                            came across this coding style (as you can tell) when writing an interpreter
                            in a purely functional style.

                            From the programmers point of view, the common subexpression elimination is a
                            simple, easy and helpful thing to do. I was surprised to find a significant
                            performance difference here. Now that I have studied a bit about how to write
                            ML compilers, the difference from the compiler's point of view is clear to me
                            but I think others on this list will be interested in this.

                            --
                            Dr Jon D Harrop, Flying Frog Consultancy Ltd.
                            Technical Presentation Software
                            http://www.ffconsultancy.com/products/presenta
                          • Remi Vanicat
                            ... They are no more equivalent for the ocaml compiler. It was what I wanted to say: function .. and funx - match x with ... are equivalent in the point of
                            Message 13 of 19 , Jul 11, 2005
                            • 0 Attachment
                              2005/7/12, Jon Harrop <jon@...>:
                              > On Monday 11 July 2005 20:27, Remi Vanicat wrote:
                              > > Those two example must not be compiled in the same way,
                              >
                              > They are not compiled in the same way. I do not believe that they "must not"
                              > be compiled in the same way, as you say, in this particular case.
                              >
                              > > because in
                              > > case of partial application they should not do the same thing
                              > > (imagine that (eval state) print somethig for example). So they are not
                              > > equivalent anymore...
                              >
                              > No, I think they really are equivalent.

                              They are no more equivalent for the ocaml compiler. It was what I
                              wanted to say: function .. and funx -> match x with ... are equivalent
                              in the point of vue of the ocaml compiler.

                              > It is just that proving this equivalence is suddenly much harder and
                              > is beyond the capability of ocamlopt.

                              it is not much harder, it is inpossible in general: look to what
                              happen in case of non termination of eval. (for example if you run it
                              on 'a' define as
                              let a = Add (a, a) ).
                            • Jon Harrop
                              ... Yes. ... Note that let a = Add (a, a) cannot be represented using the code I gave. Indeed, eval should always terminate on finite input. However, I got
                              Message 14 of 19 , Jul 12, 2005
                              • 0 Attachment
                                On Tuesday 12 July 2005 07:48, Remi Vanicat wrote:
                                > function .. and funx -> match x with ... are equivalent
                                > in the point of vue of the ocaml compiler.

                                Yes.

                                > > It is just that proving this equivalence is suddenly much harder and
                                > > is beyond the capability of ocamlopt.
                                >
                                > it is not much harder, it is inpossible in general: look to what
                                > happen in case of non termination of eval.
                                > (for example if you run it on 'a' define as let a = Add (a, a) ).

                                Note that "let a = Add (a, a)" cannot be represented using the code I gave.
                                Indeed, "eval" should always terminate on finite input.

                                However, I got it wrong again... whilst composing an answer to your post I
                                noticed that partial application of "eval" must do nothing in all cases but
                                in the first implementation of "eval" it creates an infinite loop. So one
                                version never terminates and the other always terminates.

                                Well, you get the basic idea anyway. :-)

                                --
                                Dr Jon D Harrop, Flying Frog Consultancy Ltd.
                                Technical Presentation Software
                                http://www.ffconsultancy.com/products/presenta
                              • Eray Ozkural
                                ... I might be of service here, then, let me think of something for the tutorial. Regards, -- Eray Ozkural (exa), PhD candidate. Comp. Sci. Dept., Bilkent
                                Message 15 of 19 , Jul 13, 2005
                                • 0 Attachment
                                  On 7/11/05, Radu Grigore <radugrigore@...> wrote:
                                  > --- Eray Ozkural <erayo@...> wrote:
                                  >
                                  > > Good for a tutorial?
                                  >
                                  > Yes.

                                  I might be of service here, then, let me think of something
                                  for the tutorial.

                                  Regards,

                                  --
                                  Eray Ozkural (exa), PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara
                                  http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://www.malfunct.com
                                  Uludag Project: www.uludag.org.tr KDE Project: http://www.kde.org
                                • Arturo Bórquez
                                  to Paola example finding the combinations let rec combine_2_list in_list out_list = match in_list with ... (if t [] then (List.fold_left (fun r elt - match
                                  Message 16 of 19 , Jul 15, 2005
                                  • 0 Attachment
                                    to Paola example finding the combinations

                                    let rec combine_2_list in_list out_list =
                                    match in_list with
                                    | [] -> List.rev out_list
                                    | [x; y] :: t -> combine_2_list t
                                    (if t <> [] then
                                    (List.fold_left (fun r elt ->
                                    match elt with
                                    | [x'; y'] -> r @ [(x, x'); (y, y')]
                                    | _ -> r) [] t :: out_list (* or raise exception *))
                                    else out_list)
                                    | _ -> out_list (* or raise exception *) in

                                    combine_2_list [["a"; "b"]; ["c"; "d"]; ["e"; "f"]; ["h"; "k"]] []
                                    ;;


                                    On 7/11/05, Eray Ozkural <erayo@...> wrote:
                                    > I would like to note that this might be a perfect problem to
                                    > demonstrate use of lazy evaluation. In most applications
                                    > of the combination function we are merely interested in
                                    > iterating or mapping the elements of the combination
                                    > list, without actually generating anything. Good for a
                                    > tutorial?
                                    >
                                    > On 7/7/05, Lecca Paola <lecca@...> wrote:
                                    > >
                                    > > Dear all,
                                    > > I'm dealing now with the problem of finding all the combinations between
                                    > > the elements of a list of lists. For example, suppose to have
                                    > >
                                    > > let l1 = [ ["a"; "b"]; ["c"; "d"]; ["e"; "f"]; ["h"; "k"] ];;
                                    > >
                                    > > I wish to combine with the function List.combine, the first element of l1
                                    > > with each of the remaining elements, then I want to combine the second
                                    > > element of l1 with each of the successive elements, and so on.
                                    > > The final result I would like to obtain looks like the following
                                    > >
                                    > > [("a", "c"); ("b", "d")]; [("a", "e"); ("b", "f")]; [("a", "h"); ("b",
                                    > > "k")]; [("c", "e"); ("d", "f")]; [("c", "h"); ("d", "k")]; [("e", "h");
                                    > > ("f", "k")] ]
                                    > >
                                    > > However, I'm not able to find a strategy to combine an element of l1 with
                                    > > another element that is not the next, i. e. how to perform the combination
                                    > > between ["a", "b"] and ["e"; "f"], for instance ?
                                    > >
                                    > > Using the function "numberd_list" suggested by Richard Jones I tried to
                                    > > write the following
                                    > >
                                    > > (* numbering a list *)
                                    > > let numbered_list xs =
                                    > > let rec loop n = function
                                    > > | [] -> []
                                    > > | x :: xs -> (n, x) :: loop (succ n) xs
                                    > > in
                                    > > loop 1 xs;;
                                    > >
                                    > >
                                    > > (* get the next element of a given element of a numbered list *)
                                    > > (* the input of this function is the output of the numbered_list *)
                                    > > (* function *)
                                    > >
                                    > > let list_next elt l =
                                    > > match l with
                                    > > [] -> []
                                    > > |_ -> List.nth l ((first elt))
                                    > > ;;
                                    > >
                                    > > let rec combine_in l =
                                    > > let nl = numbered_list l in
                                    > > match nl with
                                    > > [] -> []
                                    > > | nl'::nl ->
                                    > >
                                    > > (List.combine (second nl') (list_next nl' l)):: combine_in l
                                    > > ;;
                                    > >
                                    > > combine_in should combine al least each element with the next one, but
                                    > > also this simple attempt fails.
                                    > >
                                    > > Thanks for your attention,
                                    > > Paola.
                                    > >
                                    > >
                                    > > Archives up to September 30, 2004 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
                                    > >
                                    > >
                                    > >
                                    > >
                                    > >
                                    > >
                                    > >
                                    >
                                    >
                                    > --
                                    > Eray Ozkural (exa), PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara
                                    > http://www.cs.bilkent.edu.tr/~erayo Malfunction: http://www.malfunct.com
                                    > Uludag Project: www.uludag.org.tr KDE Project: http://www.kde.org
                                    >
                                    >
                                    > Archives up to September 30, 2004 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
                                    >
                                    >
                                    >
                                    >
                                    >
                                    >
                                    >
                                  Your message has been successfully submitted and would be delivered to recipients shortly.