Functionally comparing data sets to each other once with Haskell

Question

After over a year of mental wrangling, I finally understand Haskell well enough to consider it my primary language for the majority of my general programming needs. I absolutely love it.

But I still struggle with doing very specific operations in a functional way.

A simplified example:

Set = [("Bob", 10), ("Megan", 7), ("Frank", 2), ("Jane", 11)]

I'd like to compare these entries to each other. With a language like C or Python, I'd probably create some complicated loop, but I'm not sure which approach (map, fold, list comprehension?) would be best or most efficient with a functional language.

Here's a sample of the code I started working on:

run xs = [ someAlgorithm (snd x) (snd y) | x <- xs, y <- xs, x /= y ]

The predicate keeps the list comprehension from comparing entries with themselves, but the function isn't very efficient because it compares entries that have already been compared. For example. It'll compare Bob with Megan, and then compare Megan with Bob.

Any advice on how to solve this issue would be greatly appreciated.

Answer 1

If you have an ordering on your data type, you can just use x < y instead of x /= y.

Another approach is to use tails to avoid comparing elements in the same position:

[ ... | (x:ys) <- tails xs, y <- ys]

This has the effect of only picking items y that occur after x in the original list. If your list contains duplicates, you'll want to combine this with the explicit filtering from before.