Haskell为列表添加了列表的唯一组合

Question

比方说我有这样的列表

list = ["AC", "BA"]

我想将此列表的每个唯一组合添加到元组,因此结果如下:

[("AC", "AC"),("AC","BA"),("BA", "BA")]

哪里("BA","AC")被排除在外.

我的第一种方法是使用这样的列表理解:

ya = [(x,y) | x <- list, y <- list]

但我无法让它工作,无论如何通过使用列表推导来实现我的结果？

Answer 1

我的首选解决方案使用列表理解

f :: [t] -> [(t, t)]
f list = [ (a,b) | theTail@(a:_) <- tails list , b <- theTail ]

我觉得这很可读:首先你选择(非确定性地)后缀theTail,a从中开始,然后你选择(非确定性地)b后缀的一个元素.最后,(a,b)产生了这对,它明显地超过了所需的对.

它也应该是最佳的效率:每当你需要一个元素时,它就是在恒定的时间内产生的.

Answer 2

ThreeFx的答案可行,但它增加了元素必须可订购的约束.相反,您可以更有效,更通用地使用函数Prelude并Data.List实现它:

import Data.List (tails)

permutations2 :: [a] -> [(a, a)]
permutations2 list
    = concat
    $ zipWith (zip . repeat) list
    $ tails list

它不使用列表推导,但它可以在不必执行可能昂贵的比较的情况下工作,并且不会限制您可以通过它进行何种类型的值.

要了解其工作原理,请考虑如果您拥有该列表[1, 2, 3],则可以使用这些组

[(1, 1), (1, 2), (1, 3),
         (2, 2), (2, 3),
                 (3, 3)]

这相当于

[(1, [1, 2, 3]),
 (2,    [2, 3]),
 (3,       [3])]

因为它不包含任何额外或更少的信息.从这种形式到我们想要的输出的转换是将函数映射到f (x, ys) = map (\y -> (x, y)) ys每个元组,然后将concat它们放在一起.现在我们只需要弄清楚如何获得这些元组的第二个元素.很明显,我们看到它所做的一切都是从列表前面删除连续的元素.幸运的是,这已经通过tails函数实现了Data.List.每个元组中的第一个元素只是组成原始列表,因此我们知道我们可以使用a zip.最初,您可以实现此目的

> concatMap (\(x, ys) -> map (\y -> (x, y)) ys) $ zip list $ tails list

但我个人更喜欢zips,所以我将内部函数转换为不使用lambdas的函数:

> concatMap (\(x, ys) -> zip (repeat x) ys) $ zip list $ tails list

而且因为我喜欢zipWith f过map (uncurry f) . zip,我把它变成

> concat $ zipWith (\x ys -> zip (repeat x) ys) list $ tails list

现在,我们可以进一步减少这一点:

> concat $ zipWith (\x -> zip (repeat x)) list $ tails list
> concat $ zipWith (zip . repeat) list $ tails list

感谢eta减少和功能组成.我们可以把它完全放在哪里

> permutations2 = concat . ap (zipWith (zip . repeat)) tails

但我发现这很难阅读和理解,所以我想我会坚持以前的版本.