The Problem Statement: Write a function pair that takes two lists of integers and generates a list of pairs, where each pair is a combination of each element from each list.
For example, pair ([1,2], [3,4,5]) should return
[(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)].
My work so far:
-fun pair(a:int list, b:int list) = if null a then nil else if null b then nil else (hd a, hd b)::pair(a, tl b)@pair(tl a, b);
val pair = fn : int list * int list -> (int * int) list
-pair([1,2],[3,4,5]);
val it = [(1,3),(1,4),(1,5),(2,5),(2,4),(2,5),(2,3),(2,4),(2,5)]
I've tried to trace the function to find out why the (2,5), (2,4), (2,5) are showing up but I'm not seeing it clearly still.
It seems straightforward enough but I can't seem to get the last bits ironed out. Some assistance pinpointing why those elements are being added in the middle would be of help.
Thanks.
Peter
The main problem is that you're recursing over both lists.
If you look at your example,
pair ([1,2], [3,4,5]) -> [(1,3), (1,4), (1,5), (2,3), (2,4), (2,5)]
you will see that it has two sublists,
[(1,3), (1,4), (1,5)]
[(2,3), (2,4), (2,5)]
where the first consists of pairs formed from the first element of [1,2] and every element of [3,4,5], and the second is the second element of [1,2] also paired with every element of [3,4,5].
Note that each sublist contains all of [3,4,5] but only one element of [1,2] - the first is the same as pair ([1], [3,4,5]) and the second is pair ([2], [3,4,5]) - so you should only need to recurse over the first list.
You can create such a list like this:
a and pair it with every element of b in a list (hint: think about map.)a and all of b.With pattern matching:
fun pair ([], _) = []
| pair (_, []) = []
| pair (x::xs, ys) = <something involving x and ys, suitably combined with 'pairs (xs, ys)'>
It might help if you write step 1 as a separate function.