CODEWITHSUNDEEP
haskellcombinatorics
Mirzhan Irkegulov
Mirzhan Irkegulov

Reputation: 18055

Pairwise distances of a list of numbers in Haskell

If X is a set of numbers, then ΔX is a multiset of numbers, representing pairwise subtractions between each 2 numbers. For example, if X is a set of points on a line in increasing order, then ΔX is a multiset of pairwise distances between these points. How to write a function that returns pairwise distances for a list of numbers? The below works, but I want a more elegant solution. Please include theory or intuitions, that might provide insight in how to solve similar problems, if possible.

pairwise_distances :: [Int] -> [Int]
pairwise_distances [] = []
pairwise_distances [x] = []
pairwise_distances (x:xs) = sort $ map (abs . (x-)) xs ++ pairwise_distances xs

pairwise_distances [3,2,1] -- [1,1,2]
pairwise_distances [0,2,4,7,10] -- [2,2,3,3,4,5,6,7,8,10]

Upvotes: 2

Views: 948

Answers (3)

Chad Groft
Chad Groft

Reputation: 380

distances xs = sort [ y - x | (x:ys) <- tails (sort xs), y <- ys ]

Intuition: the idea is to generate all the pairs of distinct elements in xs. Each element has some location in the list. If we take x to come before y on the list, then x is the head of some tail of the list, and y is somewhere in the tail of the tail. If you sort xs first, then y >= x. You could take abs (y-x) at the end instead of sorting xs.

Upvotes: 10

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

It is spelled like it sounds.

 f xs = [x-x' | x <- xs, x' <- xs]

This of course will have each pair counted twice, once in order and once in reverse order, so half of the distances will be negative. Depending on what exactly you need, you may use this, or one of the following:

f xs = [abs(x-x') | x <- xs, x' <- xs]

f xs = [x-x' | x <- xs, x' <- xs, x>x']

The latter relies on xs being a set, i.e. no duplicate points in it, and no zero distances that should be included in the answer.

Upvotes: 1

Chris Taylor
Chris Taylor

Reputation: 47392

One option is to separate the generation of lists of pairs from the calculation of differences

abs_distance x y = abs (x - y)

pairs []     = []
pairs (x:xs) = map (\y -> (x,y)) xs ++ pairs xs
-- or, with TupleSections enabled,
-- pairs (x:xs) = map (x,) xs ++ pairs xs

so that you can write

pairwise_distances = sort . map (uncurry abs_distance) . pairs

This is certainly cleaner (and, I would argue, more elegant) although it may not be the kind of elegance you are looking for.

Upvotes: 3

Related Questions