用自定义过滤器快速排序 [英] Quicksort with custom filter

问题描述

我需要制作快速排序，但需要使用自定义筛选器。
在编译过程中，我在过滤器（> = x）xs 中得到一个错误。

   - 使用两个过滤器进行排序
 quicksort（x：xs）=（quicksort lesser）++ [x] ++（quicksort greater）
其中lesser = filter（< x）xs 
 greater = filter（> = x）xs 
 
  - 使用自定义过滤器
 csort f（x：xs）=（csort f lessser）++ [x] ++（csort f更大）
其中lesser = [e | e < -  xs，f x e] 
 greater = [e | e < -  xs，不是$ fxe] 
  

有什么不对？

解决方案

有两个问题我觉得可能会让你烦恼。

首先，加载一个把你的定义文件放到ghci中，我试试看

  ghci> csort（> = x）[2,1,3] 
 
< interactive>：1：10：不在范围内：'x'
  

您编写它的方式 f 需要两个参数。事实上 x 不在这里。因此，自定义过滤器函数应该简单地为（> =）。

  ghci中> csort（> =）[2,1,3] 
 ***例外：blahblah：函数csort中的非穷举模式
  

现在真正的问题是：非穷举模式。这是什么意思？你已经写了一个关于如何用至少一个元素对列表进行排序的定义。但是，如何排序没有元素的列表？很简单，你忽略了自定义过滤器功能，并简单地生成一个空列表。由于空列表中没有元素，因此它已被排序。

  csort _ [] = [] 
  

一旦我将该行添加到源文件中，它突然生效。模式 [] 表达了模式（x：xs），并且这两个模式一起是详尽无遗的list是空的，或者它至少有一个元素）。

  ghci> csort（> =）[2,1,3] 
 [1,2,3] 
 ghci> csort（<）[2,1,3] 
 [3,2,1] 
 ghci> quickCheck（\ xs  - > csort（<）xs ==（reverse $ csort（>）xs））
 +++ OK，通过了100次测试。 
  

---

这是我的sort.hs文件：

  csort _ [] = [] 
 csort f（x：xs）= csort f lessser ++ [x] ++ csort f greater 
 where lesser = [e | e < -  xs，f x e] 
 greater = [e | e < -  xs，而不是$ f x e] 
  

我不知道为什么您仍然有错误;这对我来说非常合适。

I need to make quicksort but with a custom filter. During compilation I get an error on filter (>=x) xs.

--sort with two filters
quicksort (x:xs) = (quicksort lesser) ++[x] ++ (quicksort greater)
                  where lesser  = filter (<x) xs
                        greater = filter (>=x) xs

--sort with custom filter
csort f (x:xs) = (csort f lesser) ++ [x] ++ (csort f greater)
                    where lesser  = [e | e <- xs, f x e]
                          greater = [e | e <- xs, not $ f x e]

What is wrong?

解决方案

There are two problems I think might be troubling you.

First of all, loading a file with your definitions into ghci, I try

ghci> csort (>= x) [2,1,3]

<interactive>:1:10: Not in scope: 'x'

The way you wrote it, f takes two parameters. And indeed x is not in scope here. So the custom filter function should be simply (>=).

ghci> csort (>=) [2,1,3]
***Exception: blahblah: Non-exhaustive patterns in function csort

Now the real problem: non-exhaustive patterns. What does this mean? You've written a definition of how to sort a list with at least one element. But how do you sort a list with no elements? Simple, you ignore the custom filter function, and simply produce an empty list. Since an empty list has no elements, it is already "sorted".

csort _ [] = []

Once I added that line to the source file, it suddenly worked. The pattern [] compliments the pattern (x:xs), and those two patterns, together, are exhaustive (a list is either empty, or it has at least one element).

ghci> csort (>=) [2,1,3]
[1,2,3]
ghci> csort (<) [2,1,3]
[3,2,1]
ghci> quickCheck (\xs -> csort (<) xs == (reverse $ csort (>) xs))
+++ OK, passed 100 tests.

---

Here's my sort.hs file:

csort _ [] = []
csort f (x:xs) = csort f lesser ++ [x] ++ csort f greater
  where lesser  = [e | e <- xs, f x e]
        greater = [e | e <- xs, not $ f x e]

I have no idea why you would still have errors; this works perfectly well for me.

这篇关于用自定义过滤器快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！