在Haskell中对类型a使用排序时出错

Question

我对Haskell很陌生，我正在尝试编写一个函数neighbours :: Int -> Metric a -> Point a -> [Point a] -> [Point a]，以便neighbours k d p xs根据点列表xs中点p的度量d，按距离顺序返回k个最近邻居的列表。我的代码是

type Point a = (a, a)
type Metric a = Point a -> Point a -> Double
type Tuple a = (Double, Point a)
create:: Metric a -> Point a -> [Point a] ->  [Tuple a] -> [Tuple a]
create d p (x:xs) ys | length xs == 0 = sort(((d p x), x) : ys)
| otherwise      = create d p xs (((d p x), x) : ys)
takeP:: Tuple a -> Point a
takeP (_,p) = p   
pList::  [Tuple a] ->[Point a]-> [Point a]
pList (x:xs) ys | length xs == 0 = reverse (takeP x : ys)
| otherwise      = pList xs (takeP x : ys) 
neighbours :: Int -> Metric a -> Point a -> [Point a] -> [Point a]--
neighbours k d p xs = take k (pList (create d p xs []) [])

但我在分拣时遇到了一个错误，那就是：

* No instance for (Ord a) arising from a use of `sort'
Possible fix:
add (Ord a) to the context of
the type signature for:
create :: forall a.
Metric a -> Point a -> [Point a] -> [Tuple a] -> [Tuple a]
* In the expression: sort (((d p x), x) : ys)
In an equation for `create':
create d p (x : xs) ys
| length xs == 0 = sort (((d p x), x) : ys)
| otherwise = create d p xs (((d p x), x) : ys)

我一开始使用type Point a = (Int, Int)，它工作得很好，但在规范中要求Point是type Point a = (a, a)，这导致了我的错误。另一个问题是，我不能更改函数类型，所以我不能按建议添加(Ord a)。

有没有一种方法可以根据第一个变量对元组列表进行排序而不会出现错误？

Answer 1

在create函数中，您可以使用sort :: Ord a => [a] -> [a]:

… =sort(((d p x), x) : ys)

因此，这意味着我们正在排序的对象类型，在本例中为Tuple a，需要是Ord类型类的实例。如果两个项的类型都是Ord的实例，则2元组是Ord类型类的实例，因此在本例中是Double和Point a。由于Point a也是2元组，但是是两个as，因此这意味着如果a是Ord的实例，则Tuple a是Ord的实例。因此，您应该添加一个类型约束：

create ::Ord a =>Metric a -> Point a -> [Point a] ->  [Tuple a] -> [Tuple a]
create d p (x:xs) ys | length xs == 0 = sort(((d p x), x) : ys)
| otherwise      = create d p xs (((d p x), x) : ys)

create函数使用了一些反模式，如使用length，这需要线性时间。事实上，您可以将其重写为对映射进行排序：

create ::Ord a =>Metric a -> Point a -> [Point a] -> [Tuple a]
create d p = sort .map f
where f x = (d p x, x)

这删除了ys参数，该参数在这里似乎只是用作累加器。

如果只想对2元组的第一项进行排序，可以使用sortOn :: Ord b => (a -> b) -> [a] -> [a]：

create :: Metric a -> Point a -> [Point a] -> [Tuple a]
create d p =sortOn fst. map f
where f x = (d p x, x)