All non-duplicate combinations of two list elements

  • A+
Category:Languages

It's easier to explain this with an example:

I want to write a function [a] -> [(a,a)] so if I get a list

[A, B, C, D]  

I want this list to return:

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

I came up with this code:

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

Which works correctly for a list of integers, but I want this to work for data types that are not instances of the Ord class. My data type derives Show and Eq. So is there a simple way to solve this problem? I'm thinking maybe by filtering the tuples from

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

But I dont know how I can do that either.

 


Solution using recursion:

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

Without recursion:

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

Without list comprehension:

import Data.List (tails)   f'' :: [a] -> [(a, a)] f'' xs = concatMap (/sl -> zip (repeat $ head sl) sl) (tails xs) 

Best is by Daniel Wagner, just use

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

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: