Декартово произведение 2 списков в Haskell

Question

Я хочу произвести декартово произведение из 2 списков в Haskell, но я не могу понять, как это сделать. Декартово произведение дает все комбинации элементов списка:

xs = [1,2,3]
ys = [4,5,6]

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Это не вопрос домашней работы и он не связан с каким-либо подобным вопросом, но способ решения этой проблемы может помочь с вопросом, на котором я застрял.

Answer 1

Это работа для sequence инг. Монадическая реализация этого может быть:

cartesian :: [[a]] -> [[a]]
cartesian [] = return []
cartesian (x:xs) = x >>= \x' -> cartesian xs >>= \xs' -> return (x':xs')

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

Как вы можете заметить, вышеприведенное напоминает реализацию map чистыми функциями, но в монадическом типе. Соответственно, вы можете упростить его до

cartesian :: [[a]] -> [[a]]
cartesian = mapM id

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

Answer 2

Просто добавьте еще один способ для энтузиастов, используя только рекурсивное сопоставление с образцом.

cartProd :: [a]->[b]->[(a,b)]
cartProd _ []=[]
cartProd [] _ = []
cartProd (x:xs) (y:ys) = [(x,y)] ++ cartProd [x] ys  ++ cartProd xs ys ++  cartProd xs [y] 

Answer 3

Вот моя реализация n-арного декартова произведения:

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]