Haskell Quicksort效率

本文介绍了Haskell Quicksort效率的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是了解您的Haskell"中的一个示例:

Here's an example from Learn you a Haskell:

quicksort :: (Ord a) => [a] -> [a] quicksort [] = [] quicksort (x:xs) = let smallerSorted = quicksort [a | a <- xs, a <= x] biggerSorted = quicksort [a | a <- xs, a > x] in smallerSorted ++ [x] ++ biggerSorted

似乎每次递归都会对列表进行两次迭代，对于每次列表理解都会对它进行一次迭代.编译器中是否有一些魔术可以优化此效果?如果没有，如何解决?

It seems that the list is iterated twice for each recursion, once for each list comprehension. Is there some magic in the compiler that optimizes this? If not, how can this be fixed?

我不在乎这是不是一个真正的快速排序.忽略快速排序. 我的问题是关于两个列表推导的效率 ，以及如何修改此特定算法(快速排序与否)，以避免每次递归两次迭代xs.

I don't care if this is a real quicksort. Ignore the quicksort. My question is about the efficiency of the two list comprehensions, and how you can modify this specific algorithm (quicksort or not) in order to avoid iterating xs twice per recursion.

推荐答案

否.截至目前，GHC 7.8.2尚不足以从上述quicksort定义中找出聪明的就地快速排序算法.通过将quicksort定义为

No. As of now, GHC 7.8.2 is not smart enough to figure out the clever in place quicksort algorithm from the above quicksort definition. You can do the same thing in a single pass by defining quicksort as

import Data.List (partition) quicksort :: (Ord a) => [a] -> [a] quicksort [] = [] quicksort (x:xs) = let (psx1, psx2, psx3) = partition3 x (x:xs) in quicksort psx1 ++ psx2 ++ quicksort psx3 partition3 _ [] = ([], [], []) partition3 a (x:xs) | a == x = (pxs1, x:pxs2, pxs3) | a < x = (pxs1, pxs2, x:pxs3) | a > x = (x:pxs1, pxs2, pxs3) where (pxs1, pxs2, pxs3) = partition3 a xs

但是您应该检查是否可以对列表进行一次快速排序?，因为它比上述版本更有效.

But you should check is it possible to do quicksort of a list with only one passing? as it is more efficient than the above version.