Returning pairs of lists in SML

Question

I would like to construct a list with all elements in the list paired up with the head of the given list.So far have the code below.I am not really sure where I am getting things wrongs here.

 fun foo [[]] = [[],[]]
  | foo [[x]] = []
  | foo (x::y::ys) =(x,y)::foo(ys); 

My signature should look like this

 ('a list) list ->('a list * 'a list) list

example output

foo [[2,3,4],[1,2],[6,7,8]] = [([2,3,4],[1,2]),([2,3,4],[6,7,8])]

Answer 1

There is a more general version of the question that is maybe a little clearer. Instead of specifically working with lists of lists, I'll instead discuss this with the more general type:

'a list -> ('a * 'a) list

This includes your desired signature ('a list) list ->('a list * 'a list) list as a special case.

It now breaks into three cases: empty lists, lists of a single element, and any other lists. You can't make pairs of elements with the first two, so we'll have those evaluate to an empty list. The remaining case is the interesting one, and looks similar to what you have. However, since you want to pair the first element of the list with all others, you'll need to put that first element back into the list when foo is recursively called. The end result looks like this:

fun foo [] = []
  | foo [x] = []
  | foo (x::y::ys) = (x,y)::foo(x::ys)

And when used (in Moscow ML):

- foo [[2,3,4], [1,2], [6,7,8]];
> val it = [([2, 3, 4], [1, 2]), ([2, 3, 4], [6, 7, 8])] :
  (int list * int list) list

Answer 2

A neater way of doing the same thing:

fun foo [] = []
  | foo (x::xs) = map (fn y => (x,y)) xs