Producto cartesiano anidado de Haskell listas

Question

Me gustaría hacer un método donde podría darle una lista de longitudes y devolvería todas las combinaciones de coordenadas cartesianas hasta esas longitudes. Más fácil de explicar con un ejemplo:

cart [2,5] 
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ] 

cart [2,2,2] 
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ] 

Una simple lista de comprensión no funcionará porque no sé cuánto tiempo las listas van a ser. Aunque me encanta la simplicidad de Haskell para muchos problemas, esta es una que podría escribir procedimentalmente (en C o algo así) en 5 minutos, ¡mientras que Haskell me da un aneurisma!

Una solución a este problema específico me ayudaría mucho; También me encantaría escuchar acerca de sus procesos de pensamiento al abordar cosas como esta.

Answer 1

Esto se puede resolver recursivamente. En primer lugar, la Cartesian product of nothing es {∅}:

cart [] = [[]] 

(o definir simplemente la forma 1-elemento si el vacío producto no es válido:

cart [x] = [[i] | i <- [0 .. x-1]] 

)

A continuación, el producto cartesiano de x:xs se puede escribir como

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs] 

---

En general, si lo que escribir una función f que requiere la longitud de la lista N , tratar de pensar en una manera de hacer f (N) depende de listas más pequeñas, por ejemplo, f (N - 1) solamente, entonces resolver el caso base f (0) o f (1) etc. Esto transforma el problema en una recursión que puede ser resuelto fácilmente.

Answer 2

Apuesto a que su solución de procedimiento implicaría la recursión. Nuestra solución Haskell implicará la recursión también.

Entonces, recursion. Primero el caso recursivo.

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart] 
    where rcart = cart cs 

Aquí sólo estamos diciendo que para cada posible coordinar inicial, y cada combinación posible de coordenadas cartesianas de las longitudes restantes, hacemos lo evidente de la combinación de la coordenada con los restantes coordenadas

Luego la funda de base.

cart [] = [[]] 

Usted podría pensar cart [] = []. Lo hice al principio. Pero piense en lo que el caso recursivo requiere del caso base.

Answer 3

Umm ..

cart = sequence . map (enumFromTo 0 . subtract 1) 

Es razonable esperar que una función [[a]] -> [[a]] haciendo lo que esperamos que ya existe en la biblioteca. Entonces, si uno no está familiarizado con sequence, encontrarlo es una simple cuestión de hoogling.

Editar: como newacct señaló:

cart = mapM (enumFromTo 0 . subtract 1) 

Esto también se pueden encontrar por la alimentación de la solución anterior a HLint.