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

问题描述 投票:24回答:6

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

例如:

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]
haskell tuples list-comprehension
6个回答
24
投票

您可以使用列表理解:

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

98
投票

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

到目前为止,我所看到的答案巧妙地使用了列表推导或它们的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成为一个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的第二定律确实成立。

看袋子的另一种方式是作为动力系列。一个包是任何大小的元组的选择,所有可能的排列(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!你去吧由指数函数的数据类型解释自然产生的操作是其自身的衍生物,是用于解决基于选择 - 无替换的问题的方便工具包。


5
投票

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

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

2
投票

另一种可能性是使用monadic表示法:

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

(这个pairs定义最常见的类型是(MonadPlus m, Eq a) => m a -> m (a,a),但我相信除了MonadPlus之外没有其他[]的例子。)


2
投票
import Control.Applicative

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

2
投票
pairs = (filter.uncurry) (/=) . (join.liftA2) (,)
© www.soinside.com 2019 - 2024. All rights reserved.