(possibly) a list comprehensions question

19 Nov 2009

      Hi Cafe!

I am struggling with an interesting problem while defining a function. It
looks quite easy to me, but I couldn't manage to have a proper
implementation yet.
To illustrate what I'm trying to achive, I'll introduce special cases of the
desired function, and hopefully build towards a solution step by step.

-- simplest case, taking 2 lists as parameters and returning a list of list
containing every possible pair (but represented as lists)
allPossibilities2 :: [a] -> [a] -> [[a]]
allPossibilities2 listX listY = [ [x,y] |
    x <- listX,
    y <- listY]

-- sample output
-- allPossibilities2 [1,2,3] [7,8,9]
-- [[1,7],[1,8],[1,9],[2,7],[2,8],[2,9],[3,7],[3,8],[3,9]]

-- simplest case with 3 parameters instead of 2
allPossibilities3 :: [a] -> [a] -> [a] -> [[a]]
allPossibilities3 listX listY listZ = [ [x,y,z] |
    x <- listX,
    y <- listY,
    z <- listZ]

-- allPossibilities3 [1,2] [3,4,5] [6,7]
-- 
[[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]]

These are easy and work just fine. All I want to do is to generalize this
function receiving n lists as parameters and doing the simple action
described above. Since I cannot pass variable number of parameters to a
function, I'll use list of lists from now on.
Following are the implementations of the same functions with different types
(instead of two lists, a list of lists assumed to caontain those 2 elements)

allPossibilities2' :: [[a]] -> [[a]]
allPossibilities2' list = [ [x,y] |
    x <- list !! 0,
    y <- list !! 1]

-- allPossibilities2' [[1,2,3],[7,8,9]]
-- [[1,7],[1,8],[1,9],[2,7],[2,8],[2,9],[3,7],[3,8],[3,9]]

allPossibilities3' :: [[a]] -> [[a]]
allPossibilities3' list = [ [x,y,z] |
    x <- list !! 0,
    y <- list !! 1,
    z <- list !! 2]

-- allPossibilities3' [[1,2],[3,4,5],[6,7]]
-- 
[[1,3,6],[1,3,7],[1,4,6],[1,4,7],[1,5,6],[1,5,7],[2,3,6],[2,3,7],[2,4,6],[2,4,7],[2,5,6],[2,5,7]]

This is ugly!

Anyway, just forget the fact that these funstions do not do a check on the
length of the input list for a moment. My question is, how can I generalize
this function to accept a list of lists of arbitrary length, and produce the
required result.

I hope I managed to make my point clear enough. Waiting for suggestions.

Regards,

-- 
Ozgur Akgun

Ozgur Akgun

Eugene Kirpichov

Neil Brown

Ozgur Akgun

yairchu＠gmail.com

Ozgur Akgun

tags

participants (4)