Я хочу произвести декартово произведение двух списков в 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)]
Это не настоящий вопрос о домашнем задании и не связан с каким-либо таким вопросом, но способ решения этой проблемы может помочь с тем, что я застрял.
Это очень легко со списком. Чтобы получить декартово произведение списков xs и ys, нам просто нужно взять кортеж (x,y) для каждого элемента x в xs и каждый элемент y в ys.
Это дает нам следующее понимание списка:
cartProd xs ys = [(x,y) | x <- xs, y <- ys]
Как отмечали другие ответы, использование списка в списке - самый естественный способ сделать это в Haskell.
Если вы изучаете Haskell и хотите работать над разработкой интуиций о типах классов, таких как Monad, однако, это забавное упражнение, чтобы понять, почему это немного более короткое определение эквивалентно:
import Control.Monad (liftM2)
cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)
Вы, вероятно, никогда не захотели бы писать это в реальном коде, но основная идея - это то, что вы увидите в Haskell все время: мы используем liftM2 для отмены немонодической функции (,) в монаду - в данном случае именно монаду списка.
Если это не имеет никакого смысла или не полезно, забудьте об этом - это просто еще один способ взглянуть на проблему.
Если ваши входные списки одного типа, вы можете получить декартово произведение произвольного количества списков, используя sequence (используя монаду List). Это даст вам список списков вместо списка кортежей:
> sequence [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
Существует очень элегантный способ сделать это с помощью аппликативных функторов:
import Control.Applicative
(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
Основная идея - применить функцию к "завернутым" аргументам, например.
(+) <$> (Just 4) <*> (Just 10)
-- Just 14
В случае списков функция будет применена ко всем комбинациям, поэтому все, что вам нужно сделать, это "поместить" их с помощью (,).
См. http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors или (более теоретический) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf для деталей.
Правильный способ - это использование списков, как уже отмечали другие люди, но если вы хотите сделать это без использования списков, по каким-либо причинам, вы можете сделать это:
cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys
Еще один способ добиться этого - использовать аппликации:
import Control.Applicative
cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys
Еще один способ, используя обозначение do:
cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
y <- ys
return (x,y)
Ну, очень простой способ сделать это будет со списком:
cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = [(x, y) | x <- xs, y <- ys]
Как я полагаю, я бы это сделал, хотя я не эксперт Haskell (каким-либо образом).
что-то вроде:
cartProd x y = [(a,b) | a <- x, b <- y]
Другие ответы предполагают, что два входных списка являются конечными. Часто идиоматический код Haskell включает в себя бесконечные списки, и поэтому стоит кратко остановиться на том, как создавать бесконечное декартово произведение в случае необходимости.
Стандартным подходом является использование диагонализации; записывая один вход по верхнему и другому входам слева, мы могли бы написать двумерную таблицу, содержащую полное декартово произведение следующим образом:
1 2 3 4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...
. . . . . .
. . . . . .
. . . . . .
Конечно, работа над любой отдельной строкой даст нам бесконечные элементы до того, как она достигнет следующей строки; Подобным же образом столкновение будет катастрофическим. Но мы можем идти по диагоналям, которые идут вниз и влево, начиная снова немного дальше вправо каждый раз, когда мы достигаем края сетки.
a1
a2
b1
a3
b2
c1
a4
b3
c2
d1
... и так далее. Для этого это даст нам:
a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...
Чтобы закодировать это в Haskell, мы можем сначала написать версию, которая создает двумерную таблицу:
cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]
Неэффективный метод диагонализации состоит в том, чтобы затем итерации сначала по диагоналям, а затем по глубине каждой диагонали, каждый раз вытягивая соответствующий элемент. Для простоты объяснения я предполагаю, что оба входных списка бесконечны, поэтому нам не нужно обходиться с проверкой границ.
diagonalBad :: [[a]] -> [a]
diagonalBad xs =
[ xs !! row !! col
| diagonal <- [0..]
, depth <- [0..diagonal]
, let row = depth
col = diagonal - depth
]
Эта реализация немного неудачна: операция индексации повторного списка !! становится все дороже, когда мы идем, давая довольно плохую асимптотическую производительность. Более эффективная реализация возьмет вышеуказанную идею, но реализует ее с помощью молнии. Итак, мы разделим нашу бесконечную сетку на три формы:
a1 a2 / a3 a4 ...
/
/
b1 / b2 b3 b4 ...
/
/
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...
. . . . .
. . . . .
. . . . .
Верхний левый треугольник будет битами, которые мы уже выбрали; верхний правый четырехугольник будет рядами, которые были частично выпущены, но все равно будут способствовать результату; а нижний прямоугольник будет строками, которые мы еще не начали испускать. Начнем с того, что верхний треугольник и верхний четырехугольник будут пустыми, а нижний прямоугольник будет всей сеткой. На каждом шаге мы можем испускать первый элемент каждой строки в верхнем четырехграннике (по существу перемещая наклонную линию на единицу), а затем добавить одну новую строку из нижнего прямоугольника в верхний четырехугольник (по существу перемещая горизонтальную линию вниз на один).
diagonal :: [[a]] -> [a]
diagonal = go [] where
go upper lower = [h | h:_ <- upper] ++ case lower of
[] -> concat (transpose upper')
row:lower' -> go (row:upper') lower'
where upper' = [t | _:t <- upper]
Хотя это выглядит немного сложнее, оно значительно более эффективно. Он также обрабатывает границы, которые проверяются нами в более простой версии.
Но вы не должны писать весь этот код самостоятельно, конечно! Вместо этого вы должны использовать пакет universe. В Data.Universe.Helpers есть (+*+), который объединяет вышеуказанные функции cartesian2d и diagonal, чтобы дать только декартово произведение продукта:
Data.Universe.Helpers> "abcd" +*+ [1..4]
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)]
Вы также можете сами увидеть диагонали, если эта структура станет полезна:
Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4]
[('a',1)]
[('a',2),('b',1)]
[('a',3),('b',2),('c',1)]
[('a',4),('b',3),('c',2),('d',1)]
[('b',4),('c',3),('d',2)]
[('c',4),('d',3)]
[('d',4)]
Если у вас много списков продуктов вместе, повторение (+*+) может несправедливо предвзято относиться к определенным спискам; вы можете использовать choices :: [[a]] -> [[a]] для ваших n-мерных декартовых продуктов.
Вот моя реализация n-арного декартова произведения:
crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]
Это работа для sequence ing. Монадическая реализация этого может быть:
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]]