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

(19)
• NextPrevious
• ... 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
View Source
• 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
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 :)
• ... 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
View Source
• 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,

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... 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
View Source
• 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
• ... 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
View Source
• 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
• 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
View Source
• 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.
>
> 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.
>
>
>
>
>
>
>

--
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
• ... 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
View Source
• 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
• ... Yes. ____________________________________________________ Sell on Yahoo! Auctions � no fees. Bid on great items. http://auctions.yahoo.com/
Message 7 of 19 , Jul 11, 2005
View Source
• 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/
• 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
View Source
• 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.
• ... 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
View Source
• 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.
• ... 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
View Source
• 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
• ... 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
View Source
• 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.
• ... 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
View Source
• 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
• ... 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
View Source
• 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) ).
• ... 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
View Source
• 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
• ... 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
View Source
• 0 Attachment
> --- 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
• 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
View Source
• 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.
> >
> >
> >
> >
> >
> >
> >
>
>
> --
> 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.
>
>
>
>
>
>
>
Your message has been successfully submitted and would be delivered to recipients shortly.