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

как отметили другие ответы, использование понимания списка является наиболее естественным способом сделать это в 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)

другие ответы предполагают, что два входных списка конечны. Часто идиоматический код Хаскелла включает бесконечные списки, и поэтому стоит кратко прокомментировать, как создать бесконечное декартово произведение в случае необходимости.

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

   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]

хотя это выглядит немного сложнее, это значительно больше эффективный. Он также обрабатывает проверку границ,которую мы использовали в более простой версии.

но вы не должны писать весь этот код самостоятельно, конечно! Вместо этого, вы должны использовать Вселенной пакета. В 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-мерных декартовых потребностей продукта.

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

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

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

что-то типа:

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

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

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]]

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

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

просто добавить еще один способ для энтузиастов, используя только рекурсивный шаблон.

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