[Haskell-cafe] (possibly) a list comprehensions question

Eugene Kirpichov ekirpichov at gmail.com
Thu Nov 19 08:37:23 EST 2009

```You can easily use "sequence". The less easy part is understanding why
it works. Are you familiar with monads? If you are not, try to take
the source code of 'sequence', inline it and understand why *that*
works.

Prelude> map sum \$ sequence [[1,2], [10,20], [100,200]]
[111,211,121,221,112,212,122,222]

2009/11/19 Ozgur Akgun <ozgurakgun at gmail.com>:
> 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
>
> _______________________________________________