Сопряженные расстояния списка номеров в Haskell

Question

Если X представляет собой набор чисел, то ΔX представляет собой цифры multiset, представляющие попарные вычитания между каждыми 2 числами. Например, если X представляет собой набор точек на линии в порядке возрастания, то ΔX представляет собой мультимножество попарных расстояний между этими точками. Как написать функцию, которая возвращает попарные расстояния для списка чисел? Ниже работает, но я хочу более элегантное решение. Пожалуйста, включите теорию или интуиции, которые могли бы дать представление о том, как решить подобные проблемы, если это возможно.

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] 

Answer 1

Это написано, как будто это звучит.

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

Это, конечно, будет иметь каждую пару посчитана дважды, один раз в порядке и один раз в обратном порядке, так что половина расстояния будет отрицательной. В зависимости от того, что именно вам нужно, вы можете использовать это, или один из следующих:

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

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

Последнее зависит от хза, являющегося набор, т.е. не повторяющихся точек в нем, и не равно нуле расстояния, которые должны быть включены в ответ.

Answer 2

Одним из вариантов является разделение генерации списков пар из расчета разностей

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 

, так что вы можете написать

pairwise_distances = sort . map (uncurry abs_distance) . pairs 

Это, конечно, чище (и я будет спорить, более элегантно), хотя это может и не быть той элегантностью, которую вы ищете.

Answer 3

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

Интуиция: идея заключается в том, чтобы генерировать все пары различных элементов в xs. Каждый элемент имеет некоторое место в списке. Если мы возьмем x до y в списке, то x - это голова какого-то хвоста списка, а y находится где-то в хвосте хвоста. Если вы сначала сортируете xs, то y >= x. Вы могли бы взять abs (y-x) в конце, а не сортировать xs.