将列表拆分为可能的元组列表

Question

我需要将列表拆分为所有可能元组的列表,但我不确定如何这样做.

例如:

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

应该导致:

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

我能够形成前两个,但我不确定如何得到其余的.

这是我到目前为止所拥有的:

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

Answer 1

这个答案分为两部分.第一部分直接解决了这个问题.第二部分是切线(字面意思),以便在第一部分背后的数学中挖掘:它可能因此被证明是有限兴趣的困难材料,但我认为一些极端分子可能会喜欢它.

到目前为止,我所看到的答案巧妙地使用了列表推导或它们的monadic等价物,但它们使用相等来排除重复,因此需要额外的Eq约束.这是一个解决方案,它使所有元素对分成两个不同的位置.

首先,我编写了一个方便的函数,用其他位置的元素列表来装饰列表的每个元素:"选择一个并离开其他"的所有方法.无论什么时候使用列表来收集选择的东西都​​是非常有用的 - 无需替换,这是我发现我经常使用的东西.

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

请注意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,在选择之前删除重复项,并再次要求Eq元素类型的实例.

仅限极端分子:容器,微积分,comonads和combinatorics啊!

picks是一个更一般的结构的一个例子,来自微分学.这是一个有趣的事实,对于任何给定的容器类型的f算子,它的数学导数∂f代表 - f删除了一个元素的结构.例如,

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

有衍生物

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

许多操作可以与这种结构相关联.想象一下,我们可以真正使用∂(我们可以使用类型系列对其进行编码).我们可以说

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

给出一种由上下文修饰的选定元素.我们当然希望有这个行动

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

plug如果我们在树中拉链,其节点被视为子树的容器,则此操作将我们移向根.

我们也应该期待InContext f成为一个共同体

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

突出所选元素和

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

用它的上下文装饰每个元素,显示你可以重新聚焦的所有可能方式,选择一个不同的元素.

不可估量的彼得汉考克曾向我建议,我们也应该期望能够"向下"(意思是"远离根"),收集所有可能的方法从整个结构中挑选一个元素.

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

应该使用其上下文来装饰x输入-structure中的每个元素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 确实成立.

看袋子的另一种方式是作为动力系列.一个包是任何大小的元组的选择,所有可能的排列(n!为大小n)被识别.所以我们可以将它组合起来作为一个由阶乘引导的大量幂,因为你必须将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),它以其自身的衍生物而闻名.

所以,p!你去吧 由指数函数的数据类型解释自然产生的操作是其自身的衍生物,是用于解决基于选择 - 无替换的问题的方便工具包.

Answer 2

您可以使用列表理解:

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

Answer 3

我的方法,有点类似于其他人的方法.它不需要Eq.

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