使用自定义过滤器进行快速排序

发布于 2024-12-10 23:05:32 字数 523 浏览 0 评论 0原文

我需要使用自定义过滤器进行快速排序。在编译期间，我在 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]

怎么了？

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

暗喜 2024-12-17 23:05:32

我认为有两个问题可能困扰着您。

首先，将包含您的定义的文件加载到ghci中，我尝试

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

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

按照您编写的方式，f采用两个参数。事实上，x 不在此处的范围内。所以自定义过滤器函数应该是简单的(>=)。

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

现在真正的问题是：非详尽的模式。这意味着什么？您已经编写了如何对至少包含一个元素的列表进行排序的定义。但是如何对没有元素的列表进行排序呢？很简单，您忽略自定义过滤器功能，并简单地生成一个空列表。由于空列表没有元素，因此它已经“排序”。

csort _ [] = []

一旦我将该行添加到源文件中，它就突然起作用了。模式 [] 与模式 (x:xs) 相得益彰，这两个模式一起是详尽的（列表要么是空的，要么至少有一个元素）。

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.

这是我的 sort.hs 文件：

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]

我不知道为什么你仍然会出现错误；这对我来说非常有效。

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.

回复收藏 0 原文

~没有更多了~