haskell - 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

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

直觉:想法是生成 xs 中所有不同元素对。每个元素在列表中都有某个位置。如果我们将 x 置于列表中的 y 之前，则 x 是列表中某些尾部的头部，而 y 是在尾部的某个地方。如果先对 xs 排序，然后对 y >= x 排序。您可以在末尾获取 abs (y-x)，而不是对 xs 进行排序。