Haskell中的2個列表的笛卡爾積

Question

我希望在Haskell中生成2個列表的Cartesian乘積，但是我不知道如何去做。笛卡爾乘積給出列表元素的所有組合：

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的笛卡兒乘積，我們只需要對xs中的每個元素x和ys中的每個元素y採用元組(x,y)。

這給了我們以下列表理解：

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 (,) 

你可能止跌我們永遠不想用真實代碼來編寫這個代碼，但是基本思想是你一直會在Haskell中看到的東西：我們使用liftM2來將非一元函數(,)提升爲一個單元 - 在這種情況下，特別是列表單子。

如果這樣做沒有任何意義或者沒有用，忘記它 - 這只是查看問題的另一種方式。

Answer 6

如果輸入列表的類型相同，則可以使用sequence（使用List monad）獲得任意數量列表的笛卡爾乘積。這將讓你列表的列表，而不是元組的列表：

> 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

另一種方式來完成，這是使用applicatives：

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

這是我實現n元笛卡兒積：

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

Answer 11

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

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維笛卡爾產品需求。