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

Neil Brown nccb2 at kent.ac.uk
Thu Nov 19 08:48:58 EST 2009

Ozgur Akgun wrote:
> 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.


The concise solution is the list monad, as already posted.  If that 
confuses you, here is a version using list comprehensions (well, mostly):

allPossibilities :: [[a]] -> [[a]]
allPossibilities [] = [[]]
allPossibilities (l:ls) = [ x : xs | x <- l, xs <- allPossibilities ls]

The second line prefixes all possibilities from the later lists with 
every element from the the first list.  Note that the base-case is 
crucial; if it is the empty list [], that "xs <- allPossibilities ls" 
will not find any elements, and thus the list comprehension becomes the 
empty list, and the whole thing falls apart.  Thus the base case must be 
the list containing the empty list, so that you have one possibility 
arising at the end upon which to prefix the items.  Hope that makes sense...



More information about the Haskell-Cafe mailing list