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

Ответ 1

Это очень легко со списком. Чтобы получить декартово произведение списков xs и ys, нам просто нужно взять кортеж (x,y) для каждого элемента x в xs и каждый элемент y в ys.

Это дает нам следующее понимание списка:

cartProd xs ys = [(x,y) | x <- xs, y <- ys]

Ответ 2

Как отмечали другие ответы, использование списка в списке - самый естественный способ сделать это в Haskell.

Если вы изучаете Haskell и хотите работать над разработкой интуиций о типах классов, таких как Monad, однако, это забавное упражнение, чтобы понять, почему это немного более короткое определение эквивалентно:

import Control.Monad (liftM2)

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)

Вы, вероятно, никогда не захотели бы писать это в реальном коде, но основная идея - это то, что вы увидите в Haskell все время: мы используем liftM2 для отмены немонодической функции (,) в монаду - в данном случае именно монаду списка.

Если это не имеет никакого смысла или не полезно, забудьте об этом - это просто еще один способ взглянуть на проблему.

Ответ 3

Если ваши входные списки одного типа, вы можете получить декартово произведение произвольного количества списков, используя 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]]

Ответ 4

Существует очень элегантный способ сделать это с помощью аппликативных функторов:

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 для деталей.

Ответ 5

Правильный способ - это использование списков, как уже отмечали другие люди, но если вы хотите сделать это без использования списков, по каким-либо причинам, вы можете сделать это:

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

Ответ 6

Еще один способ добиться этого - использовать аппликации:

import Control.Applicative

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys

Ответ 7

Еще один способ, используя обозначение do:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
                    y <- ys
                    return (x,y)

Ответ 8

Ну, очень простой способ сделать это будет со списком:

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

Как я полагаю, я бы это сделал, хотя я не эксперт Haskell (каким-либо образом).

Ответ 9

что-то вроде:

cartProd x y = [(a,b) | a <- x, b <- y]

Ответ 10

Другие ответы предполагают, что два входных списка являются конечными. Часто идиоматический код 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-мерных декартовых продуктов.

Ответ 11

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

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

Ответ 12

Это работа для 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]]