拆分列表分成可能的元组的列表(Splitting list into a list of possi

我需要一个列表拆分成所有可能的元组的列表，但我不确定如何做到这一点。

例如：

pairs ["cat","dog","mouse"]

应导致：

[("cat","dog"), ("cat","mouse"), ("dog","cat"), ("dog","mouse"), ("mouse","cat"), ("mouse","dog")]

我能组成第2，但我不确定如何得到休息。

这是我到目前为止有：

pairs :: [a] -> [(a,a)]
pairs (x:xs) = [(m,n) | m <- [x], n <- xs]

Answer 1:

您可以使用列表理解：

allpairs :: Eq a => [a] -> [(a,a)]
allpairs xs = [ (x1,x2) | x1 <- xs, x2 <- xs, x1 /= x2 ]

Answer 2:

这个答案是两个部分。 第一部分直接解决的问题。 第二部分，以便在第一部分背后的数学挖约熄灭的切线（直译）：因此可能被证明是兴趣有限难料，但我认为一个少数极端可能会喜欢它。

到目前为止，我已经看到了这些问题的答案使整齐使用列表理解或他们的单子等同的，但他们使用的平等排除重复，因此需要额外的Eq约束。这里有一个解决方案，使所有对处于两个不同位置的元素。

首先，我写了一个方便的功能，装饰与在其他位置的元素列表列表中的每个元素：所有的方式来“挑一，离开他人”。这是每当列表被用来收集的东西进行选择，而无需更换是非常有用的，它的东西，我觉得我用了很多。

picks :: [x] -> [(x, [x])]
picks [] = []
picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs]

需要注意的是map fst . picks = id map fst . picks = id ，使结果的每个位置选定元是从原来的列表中位置的元素：这就是我的意思是“装饰”。

现在，很容易挑二，使用相同的列表中理解一种方法，在其他的答案。但是，而不是从列表中选择自己的第一个组件，我们可以从它的选择picks ，同时获得了第二组分的候选人名单。

allPairs :: [x] -> [(x, x)]
allPairs xs = [(y, z) | (y, ys) <- picks xs, z <- ys]

这只是因为容易得到的三元组的保持，同时picks了两次。

allTriples :: [x] -> [(x, x, x)]
allTriples ws = [(x, y, z) | (x, xs) <- picks ws, (y, ys) <- picks xs, z <- ys]

对于均匀性，这很容易让人使代码略效率较低，写作(z, _) <- picks ys而非z <- ys两个。

如果输入列表中有没有重复，你不会得到输出任何复制的元组，由于元组从不同位置的元素。然而，你会得到

Picks> allPairs ["cat", "cat"]
[("cat","cat"),("cat","cat")]

为了避免这种情况，可随时使用allPairs . nub allPairs . nub ，它去除了选择之前重复和要求一次一个Eq实例为元素类型。

仅适用于极端：容器，微积分，comonads和组合啊嗬！

picks是更一般的构建体的一个实例，从微分而产生。这是一个有趣的事实，即对于任何给定containery排序函子的f ，其数学衍生物，∂F，表示f -structures与一个元件除去。例如，

newtype Trio x = Trio (x, x, x)   -- x^3

具有衍生

data DTrio x = Left3 ((), x, x) | Mid3 (x, (), x) | Right3 (x, x, ())  -- 3*x^2

许多操作都可以用这种结构有关。试想一下，我们真的可以用∂（我们可以把它用型家庭还挺符号UP）。然后，我们可以说

data InContext f x = (:-) {selected :: x, context :: ∂f x}

以得到类型由上下文装饰选择的元素的。我们当然应该期待有操作

plug :: InContext f x -> f x   -- putting the element back in its place

此plug操作使我们朝着如果我们在一棵树上其节点被视为子树的容器zippering约根。

我们还应该想到InContext f是一个comonad，与

counit :: InContext f x -> x
counit = selected

突出所选择的元素和

cojoin :: InContext f x -> InContext f (InContext f x)

装饰的每一个元素与它的背景下，表现出你可以重新调整所有可能的方式，选择不同的元素。

不可估量的彼得·汉考克曾经向我建议，我们也应该期望能够移动“向下”（意为“远离根”），收集所有可能的方式来挑选一个元素，在上下文中从整体结构。

picks :: f x -> f (InContext f x)

应该装点每一个x -元素在输入f与它的上下文-结构。我们应该期待

fmap selected . picks = id

这就是我们前面有规律，也是

fmap plug (picks fx) = fmap (const fx) fx

告诉我们，每一个装饰元素是原始数据的分解。我们没有高于法律。我们有

picks :: [x] -> [(x, [x])]

装饰的每一个元素的东西有点像它的上下文不太：从刚才的其他元素的列表中，你看不到的地方“洞”是。事实上，

∂[] x = ([x], [x])

从孔后的元件的孔之前分离元件的列表。按理说，我应该写

picks :: [x] -> [(x, ([x], [x]))]
picks [] = []
picks (x : xs) = (x, ([], xs)) : [(y, (x : ys, ys')) | (y, (ys, ys')) <- picks xs]

而这当然是一个非常有用的操作了。

但是，到底发生了什么上是非常明智的，只有轻微的虐待。在我最初写的代码，我在本地取[]表示有限袋或无序列表 。手袋是没有具体位置的概念列表，因此，如果您选择一个元素，它的上下文是其余元素的袋子。确实

∂Bag = Bag   -- really? why?

所以正确的观念picks的确

picks :: Bag x -> Bag (x, Bag x)

代表Bag的[]这就是我们有什么。此外，箱包， plug只是(:)和，达袋平等（即置换），对第二定律picks 不成立。

看着包装袋的另一种方式是作为动力系列。 bag是任意大小的元组的选择，以确定所有可能的排列（N！为大小n）。 所以我们可以组合地把它写成由阶乘quotiented权力之大，因为你必须用x ^ N乘N分！考虑到这样的事实，即n的！在其中你可以选择的X的订单给你同样的袋子。

 Bag x = 1 + x + x^2/2! + x^3/3! + ...

所以

∂Bag x = 0 + 1 + x      + x^2/2! + ...

侧向移位系列。事实上，你可能已经意识到了幂级数Bag为对于exp （或E ^ X），这就是著名的是其自身的衍生物。

所以，唷！你去那里。操作自然地从指数函数的数据类型解释而产生，为自身的衍生物，是用于基于选择，而无需更换解决问题的方便的工具包片。

Answer 3:

我的方法，这有点类似于给别人。它不要求Eq 。

allpairs :: [t] -> [(t,t)]
allpairs [] = []
allpairs [_] = []
allpairs (x:xs) = concatMap (\y -> [(x,y),(y,x)]) xs ++ allpairs xs

Answer 4:

另一种可能性是使用一元表示法：

pairs :: (Eq a) => [a] -> [(a,a)]
pairs l = do
    x <- l
    y <- l
    guard (x /= y)
    return (x, y)

（此定义的最普通类型pairs将(MonadPlus m, Eq a) => ma -> m (a,a)但相信没有实例MonadPlus比其他[]为它将使感。）

Answer 5:

import Control.Applicative

pairs xs = filter (uncurry (/=)) $ (,) <$> xs <*> xs

Answer 6:

pairs = (filter.uncurry) (/=) . (join.liftA2) (,)