haskell - 两个列表元素的所有非重复组合

Question

用一个例子更容易解释这一点:

我想写一个函数 [a] -> [(a,a)] 所以如果我得到一个列表

[A, B, C, D] 

我希望这个列表返回:

[(A, A), (A,B), (A,C), (A,D), (B,B), (B,C), (B,D), (C,C), (C,D), (D,D)]

我想出了这个代码:

function s = [(x,y) | x <- s, y <- s, x<=y]

这适用于整数列表，但我希望它适用于不是 Ord 类实例的数据类型。我的数据类型派生 Show 和 Eq。那么有没有简单的方法来解决这个问题呢？我在想也许通过过滤元组

function s = [(x,y) | x <- s, y <- s]

但我也不知道我怎么能做到这一点。

Answer 1

使用递归的解决方案:

f :: [a] -> [(a, a)]
f []     = []
f (x:xs) = [(x, y) | y <- (x:xs)] ++ f xs 

没有递归:

import Data.List (tails) 

f' :: [a] -> [(a, a)]
f' xs = concat [[(head x, y) | y <- x] | x <- tails xs]

没有列表理解:

import Data.List (tails) 

f'' :: [a] -> [(a, a)]
f'' xs = concatMap (\sl -> zip (repeat $ head sl) sl) (tails xs)

最好的是 Daniel Wagner，只需使用

[(head x, y) | x <- tails xs, y <- x]