当前位置：文江博客话题详情

haskell combinatorics cartesian-product

Haskell 中 2 个列表的笛卡尔积

发布于 2024-10-01 05:24:39 字数 294 浏览 16 评论 0 原文

我希望在 Haskell 中生成 2 个列表的笛卡尔积，但我不知道如何做到这一点。笛卡尔积给出了列表元素的所有组合：

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

这不是一个实际的家庭作业问题，也与任何此类问题无关，但解决此问题的方式可能对我遇到的问题有所帮助。

原文

I wish to produce the Cartesian product of 2 lists in Haskell, but I cannot work out how to do it. The cartesian product gives all combinations of the list elements:

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

This is not an actual homework question and is not related to any such question, but the way in which this problem is solved may help with one I am stuck on.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

无声静候 2024-10-08 05:24:40

如果您想要的只是笛卡尔积，则上述任何答案都可以。但通常情况下，笛卡尔积是达到目的的一种手段。通常，这意味着将元组的元素绑定到一些变量，x和y，然后对它们调用一些函数fx y。如果这就是计划，那么您最好直接使用完整的 monad：

do
    x <- [1, 2]
    y <- [6, 8, 10]
    pure $ f x y

这将生成列表 [f 1 6, f 1 8, f 1 10, f 2 6, f 2 8, f 2 10] 。

If all you want is the Cartesian product, any of the above answers will do. Usually, though, the Cartesian product is a means to an end. Usually, this means binding the elements of the tuple to some variables, x and y, then calling some function f x y on them. If this is the plan anyway, you might be better off just going full monad:

do
    x <- [1, 2]
    y <- [6, 8, 10]
    pure $ f x y

This will produce the list [f 1 6, f 1 8, f 1 10, f 2 6, f 2 8, f 2 10].

回复收藏 0 原文

鸵鸟症 2024-10-08 05:24:40

让我总结一下计算 2 个列表的笛卡尔积的所有方法。其中大部分已经提到过，但是将它们放在一个地方会很有用。我还在最后添加了更多选项，因此这个答案不仅仅是其他答案的汇编。

Monad -- liftM2 (,)
sequence -- 生成列表列表
Applicative -- (,) <$>; xs <*>; ys
列表理解 -- [(x, y) | x <- xs, y <- ys]
do 表示法
绑定 -- xs >>= (\x -> ys >>= ( \y -> (x, y)))
绑定 pointfree -- (ys >>=) 。 (,) =<< xs
MonadPlus -- xs `mplus` ys

回复收藏 0 原文

闻呓 2024-10-08 05:24:39

使用列表推导式这非常容易。要获得列表 xs 和 ys 的笛卡尔积，我们只需为每个元素获取元组 (x,y) xs 中的 >x 和 ys 中的每个元素 y。

这给了我们以下列表理解：

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

This is very easy with list comprehensions. To get the cartesian product of the lists xs and ys, we just need to take the tuple (x,y) for each element x in xs and each element y in ys.

This gives us the following list comprehension:

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

回复收藏 0 原文

画骨成沙 2024-10-08 05:24:39

正如其他答案所指出的，使用列表理解是在 Haskell 中执行此操作的最自然的方法。

然而，如果您正在学习 Haskell 并希望致力于开发有关 Monad 等类型类的直觉，那么找出为什么这个稍短的定义是等效的是一个有趣的练习：

import Control.Monad (liftM2)

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

您可能永远不会想要用真实的代码编写它，但基本思想是你在 Haskell 中经常看到的：我们使用 liftM2 来提升非单子函数 (,) 到一个 monad 中——在本例中具体是列表 monad。

如果这没有任何意义或没有用，那就忘记它吧——这只是看待问题的另一种方式。

As other answers have noted, using a list comprehension is the most natural way to do this in Haskell.

If you're learning Haskell and want to work on developing intuitions about type classes like Monad, however, it's a fun exercise to figure out why this slightly shorter definition is equivalent:

import Control.Monad (liftM2)

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

You probably wouldn't ever want to write this in real code, but the basic idea is something you'll see in Haskell all the time: we're using liftM2 to lift the non-monadic function (,) into a monad—in this case specifically the list monad.

If this doesn't make any sense or isn't useful, forget it—it's just another way to look at the problem.

回复收藏 0 原文

不知在何时 2024-10-08 05:24:39

如果您的输入列表属于相同类型，则可以使用 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]]

If your input lists are of the same type, you can get the cartesian product of an arbitrary number of lists using sequence (using the List monad). This will get you a list of lists instead of a list of tuples:

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

回复收藏 0 原文

绝對不後悔。 2024-10-08 05:24:39

有一种非常优雅的方法可以使用应用函子来做到这一点：

import Control.Applicative

(,) <gt; [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

基本思想是将函数应用于“包装”参数，例如，

(+) <gt; (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 了解详细信息。

There is a very elegant way to do this with Applicative Functors:

import Control.Applicative

(,) <gt; [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

The basic idea is to apply a function on "wrapped" arguments, e.g.

(+) <gt; (Just 4) <*> (Just 10)
-- Just 14

In case of lists, the function will be applied to all combinations, so all you have to do is to "tuple" them with (,).

See http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors or (more theoretical) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf for details.

回复收藏 0 原文

楠木可依 2024-10-08 05:24:39

其他答案假设两个输入列表是有限的。通常，惯用的 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 ...

要在 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 中。助手，有(+*+)，将上面的cartesian2d和封装在一起对角线函数仅给出笛卡尔积运算：

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 维笛卡尔积需求。

Other answers assume that the two input lists are finite. Frequently, idiomatic Haskell code includes infinite lists, and so it is worthwhile commenting briefly on how to produce an infinite Cartesian product in case that is needed.

The standard approach is to use diagonalization; writing the one input along the top and the other input along the left, we could write a two-dimensional table that contained the full Cartesian product like this:

   1  2  3  4 . . .
a a1 a2 a3 a4 . . .
b b1 b2 b3 b4 . . .
c c1 c2 c3 c4 . . .
d d1 d2 d3 d4 . . .
.  .  .  .  . .
.  .  .  .  .   .
.  .  .  .  .     .

Of course, working across any single row will give us infinitely elements before it reaches the next row; similarly going column-wise would be disastrous. But we can go along diagonals that go down and to the left, starting again in a bit farther to the right each time we reach the edge of the grid.

...and so on. In order, this would give us:

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...

To code this in Haskell, we can first write the version that produces the two-dimensional table:

cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]

An inefficient method of diagonalizing is to then iterate first along diagonals and then along depth of each diagonal, pulling out the appropriate element each time. For simplicity of explanation, I'll assume that both the input lists are infinite, so we don't have to mess around with bounds checking.

diagonalBad :: [[a]] -> [a]
diagonalBad xs =
    [ xs !! row !! col
    | diagonal <- [0..]
    , depth <- [0..diagonal]
    , let row = depth
          col = diagonal - depth
    ]

This implementation is a bit unfortunate: the repeated list indexing operation !! gets more and more expensive as we go, giving quite a bad asymptotic performance. A more efficient implementation will take the above idea but implement it using zippers. So, we'll divide our infinite grid into three shapes like this:

a1 a2 / a3 a4 . . .
     /
    /
b1 / b2 b3 b4 . . .
  /
 /
/
  c1 c2 c3 c4 . . .
---------------------------------
  d1 d2 d3 d4 . . .
   .  .  .  . .
   .  .  .  .   .
   .  .  .  .     .

The top left triangle will be the bits we've already emitted; the top right quadrilateral will be rows that have been partially emitted but will still contribute to the result; and the bottom rectangle will be rows that we have not yet started emitting. To begin with, the upper triangle and upper quadrilateral will be empty, and the bottom rectangle will be the entire grid. On each step, we can emit the first element of each row in the upper quadrilateral (essentially moving the slanted line over by one), then add one new row from the bottom rectangle to the upper quadrilateral (essentially moving the horizontal line down by one).

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]

Although this looks a bit more complicated, it is significantly more efficient. It also handles the bounds checking that we punted on in the simpler version.

But you shouldn't write all this code yourself, of course! Instead, you should use the universe package. In Data.Universe.Helpers, there is (+*+), which packages together the above cartesian2d and diagonal functions to give just the Cartesian product operation:

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

You can also see the diagonals themselves if that structure becomes useful:

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

If you have many lists to product together, iterating (+*+) can unfairly bias certain lists; you can use choices :: [[a]] -> [[a]] for your n-dimensional Cartesian product needs.

回复收藏 0 原文

时间海 2024-10-08 05:24:39

实现此目的的另一种方法是使用应用程序：

import Control.Applicative

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

Yet another way to accomplish this is using applicatives:

import Control.Applicative

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

回复收藏 0 原文

绮筵 2024-10-08 05:24:39

还有另一种方法，使用 do 表示法：

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

Yet another way, using the do notation:

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

回复收藏 0 原文

糖粟与秋泊 2024-10-08 05:24:39

正确的方法是使用列表推导式，正如其他人已经指出的那样，但是如果您出于任何原因想在不使用列表推导式的情况下执行此操作，那么您可以这样做：

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

The right way is using list comprehensions, as other people have already pointed out, but if you wanted to do it without using list comprehensions for any reason, then you could do this:

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

回复收藏 0 原文

怪我鬧 2024-10-08 05:24:39

好吧，一种非常简单的方法是使用列表理解：

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

我想这就是我将如何做到这一点，尽管我不是 Haskell 专家（无论如何）。

Well, one very easy way to do this would be with list comprehensions:

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

Which I suppose is how I would do this, although I'm not a Haskell expert (by any means).

回复收藏 0 原文

傲世九天 2024-10-08 05:24:39

像这样的东西：

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

something like:

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

回复收藏 0 原文

鸢与 2024-10-08 05:24:39

这是一项测序的工作。它的一元实现可能是：

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

It's a job for sequenceing. A monadic implementation of it could be:

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

As you may notice, the above resembles the implementation of map by pure functions but in monadic type. Accordingly you can simplify it down to

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

回复收藏 0 原文

假装不在乎 2024-10-08 05:24:39

只是为爱好者添加了一种方法，仅使用递归模式匹配。

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

Just adding one more way for the enthusiast, using only recursive pattern matching.

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

回复收藏 0 原文

酸甜透明夹心 2024-10-08 05:24:39

这是我对 n 元笛卡尔积的实现：

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

Here is my implementation of n-ary cartesian product:

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

回复收藏 0 原文

天气好吗我好吗 2024-10-08 05:24:39

没有列表理解的递归模式匹配

crossProduct [] b=[]
crossProduct (x : xs) b= [(x,b)] ++ crossProduct xs b

cartProd _ []=[]
cartProd x (u:uv) = crossProduct x u ++ cartProd x uv

Recursive pattern matching with out List comprehension

crossProduct [] b=[]
crossProduct (x : xs) b= [(x,b)] ++ crossProduct xs b

cartProd _ []=[]
cartProd x (u:uv) = crossProduct x u ++ cartProd x uv

回复收藏 0 原文

~没有更多了~

关于作者

云醉月微眠

暂无简介

0 文章

0 评论

24 人气

关注发私信

友情链接

文江博客

Haskell 中 2 个列表的笛卡尔积

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（16）

关于作者

相关话题

热门标签

推荐作者

杨绘峰

听闻余生

谜兔

xiaotwins

你说

若能看破又如何

友情链接

Haskell 中 2 个列表的笛卡尔积

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（16）

关于作者

相关话题

热门标签

推荐作者

杨绘峰

听闻余生

谜兔

xiaotwins

你说

若能看破又如何

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。