Listas em compreensão aninhadas

[InvertedCloud]

Boas,

Estou ultimamente a aprender programação funcional e deparei-me com um exercício que diz o seguinte (no que suponho seja terminologia académica):

mostre que uma lista em compreensão com geradores duplos pode ser descrita usando geradores simples. Sugestão: use a função concat e uma compreensão dentro de outra.

É dado o exemplo de 

[(x, y) | x <- [1, 2, 3], y <- [4, 5, 6] ] 

o meu problema aqui é, como raio é que se encaixa sintacticamente uma lista por compreensão aninhada dentro de outra?

o exemplo descreve uma lista de tuplos (x, y) com aqueles geradores para cada variável. Concat recebe uma lista de listas. Perdi-me algures no meio, suponho.

Não tenho qualquer exemplo de tal situação, estou a seguir o livro "Learn you a Haskell for great good" e paralelamente a frequentar uma cadeira de programação funcional com haskell que me fornece outro tipo de exercicios, admitidamente mais fáceis. Alguma ideia? 

[Baderous]

Para resolveres esse problema, o mais fácil é criares uma função auxiliar que recebe um valor e uma lista e gera pares desse valor com cada elemento da lista:

g _ [] = []
g x (l:ls) = (x,l):(g x ls)

Depois, para cada valor da lista x (obtido pela sua notação em compreensão), aplicas esta função passando como 1º parâmetro o valor em processamento e como 2º parâmetro a lista y:

[g x [y | y <- [4,5,6]] | x <- [1,2,3]]

Esta função devolve-te o resultado: [[(1,4),(1,5),(1,6)],[(2,4),(2,5),(2,6)],[(3,4),(3,5),(3,6)]]

Assim, precisas de aplicar a função concat nele, para obteres exatamente o mesmo da tua função inicial:

func = [(x, y) | x <- [1, 2, 3], y <- [4, 5, 6]]

funcAlt = concat [g x [y | y <- [4,5,6]] | x <- [1,2,3]]

E os resultados de ambas as funções serão iguais:

> func
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

> funcAlt
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]