[Haskell-cafe] Generalizing nested list comprehensions

[Daniel Fischer]

Am Freitag 26 Februar 2010 15:52:15 schrieb Ishaaq Chandy:
> Hi all,
> If this question sounds a bit noob-ish, that would be because I am one -
> so apologies in advance!
>
> I have functions that look something like these:
>
> f1 :: [a] -> [b]
> f1 xs = [foo [x1, x2] |
>      x1 <- xs,
>      x2 <- bar x1,
>      baz x1 /= baz x2]
>
> f2 :: [a] -> [b]
> f2 xs = [foo [x1, x2, x3] |
>      x1 <- xs,
>      x2 <- bar x1,
>      x3 <- bar x2,
>      baz x1 /= baz x2,
>      baz x1 /= baz x3,
>      baz x2 /= baz x3]
>
> f3 :: [a] -> [b]
> f3 xs = [foo [x1, x2, x3, x4] |
>      x1 <- xs,
>      x2 <- bar x1,
>      x3 <- bar x2,
>      x4 <- bar x3,
>      baz x1 /= baz x2,
>      baz x1 /= baz x3,
>      baz x1 /= baz x4,
>      baz x2 /= baz x3,
>      baz x1 /= baz x4]
>
> Note that for the purposes of this discussion it does not matter what
> foo, bar and baz do.
>
> Now what I want to do is write a generalized function fn based on the
> pattern set by f1, f2 and f3 such that:
> fn :: Int -> [a] -> [b]
> and:
> (fn 1 xs) == f1 xs
> (fn 2 xs) == f2 xs
> (fn 3 xs) == f3 xs
> (fn 25 xs) == f25 xs
>
> - obviously if I were to implement f25 as nested list comprehensions it
> would be ridiculously tedious!
>
> Any ideas how I can implement fn?

The easy way is recursion:

import Control.Monad (guard)

fn n xs = do
    x1 <- xs
    let b1 = baz x1
    contFn n [] [b1] x1

contFn 0 acc _ xn = [foo (reverse (xn:acc)]
contFn n acc bs xi = do
    xj <- bar xi
    let bj = baz xj
    guard (all (/= bj) bs)
    contFn (n-1) (xi:acc) (bj:bs) xj

Now, there is probably a frighteningly elegant way to do it with foldM or 
somesuch, but I don't see it at the moment :(

>
> Thanks,
> Ishaaq