如何在 Idris 中编写一个简单的基于列表的快速排序？

Question

我只是想尽最大努力将以下 Haskell 翻译成 Idris（我不是在寻找效率或正确性证明）：

quicksort  []           =  []
quicksort (x:xs)        =  quicksort [y | y <- xs, y<x ]
                        ++ [x]
                        ++ quicksort [y | y <- xs, y>=x]

这是我的 Idris 代码，除了需要告诉 Idris 我们正在处理有序类型外，它与 Haskell 基本没有变化：

quicksort: List (Ord b) -> List (Ord b)
quicksort  []           =  []
quicksort (x::xs)       =  quicksort [y | y <- xs, y<x ]
                        ++ [x]
                        ++ quicksort [y | y <- xs, y>=x]

但是，我显然做错了。我在看到问题有答案，但形式有点不同 - 我想了解当前方法有什么问题。我上面的代码给出了错误：

40 | quicksort (x::xs)       =  quicksort [y | y <- xs, y<x ]
   |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ...
When checking right hand side of quicksort with expected type
        List b

When checking an application of function Prelude.Applicative.guard:
        Can't find implementation for Ord (Ord b)

Answer 1

问题是 Prelude.Applicative.guard（用于列表推导中的守卫的函数）找不到 Ord 类型类的实现。

这告诉我们，我们没有添加（或错误添加）类型类约束。如果我们将您的代码更改为这个，它应该可以工作：

quicksort: Ord b => List b -> List  b
quicksort  []           =  []
quicksort (x::xs)       =  quicksort [y | y <- xs, y < x ]
                        ++ [x]
                        ++ quicksort [y | y <- xs, y >= x]

Answer 2

澄清一下：List (Ord b) 是 Ord b 的实现列表，而 Ord b => List b 是 b 的列表，其中 b 具有接口约束Ord b 个。比较：

[ord1] Ord Nat where
   compare Z (S n)     = GT
   compare (S n) Z     = LT
   compare Z Z         = EQ
   compare (S x) (S y) = compare @{ord1} x y

imps : List (Ord b) -> List (Ord b)
imps xs = xs

ords : Ord b => List b -> List b
ords xs = xs

有 imps [ord1] : List (Ord Nat) 和 ords [1] : List Nat。

如何在 Idris 中编写一个简单的基于列表的快速排序？

How to write a simple list-based quicksort in Idris?

idris