Декартовое произведение из 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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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

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

import Control.Monad (liftM2) 

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

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

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

Answer 6

Если ваши входные списки одного типа, вы можете получить декартово произведение произвольного количества списков, используя sequence (с использованием монады).Это поможет вам список списков вместо списка кортежей:

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

Answer 7

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

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

Answer 8

Еще один способ сделать это с помощью аппликативных:

import Control.Applicative 

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

Answer 9

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

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.

Answer 10

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

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

Answer 11

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

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