这是将“真正”的快速排序C代码转换为Haskell的音译。准备好了吗？
import Control.Monad
import Data.Array.IO
import Data.IORef
qsort :: IOUArray Int Int -> Int -> Int -> IO ()
qsort a lo hi = do
(h,l,p,t) <- liftM4 (,,,) z z z z
when (lo < hi) $ do
l .= lo
h .= hi
p .=. (a!hi)
doWhile (get l .< get h) $ do
while ((get l .< get h) .&& ((a.!l) .<= get p)) $ do
modifyIORef l succ
while ((get h .> get l) .&& ((a.!h) .>= get p)) $ do
modifyIORef h pred
b <- get l .< get h
when b $ do
t .=. (a.!l)
lVal <- get l
hVal <- get h
writeArray a lVal =<< a!hVal
writeArray a hVal =<< get t
lVal <- get l
writeArray a hi =<< a!lVal
writeArray a lVal =<< get p
hi' <- fmap pred (get l)
qsort a lo hi'
lo' <- fmap succ (get l)
qsort a lo' hi
那很有趣，不是吗？实际上我在函数开头剪掉了这个大的let，并且在结尾处剪掉了where，定义了所有的辅助函数，使前面的代码看起来更加美观。
let z :: IO (IORef Int)
z = newIORef 0
(.=) = writeIORef
ref .=. action = do v <- action; ref .= v
(!) = readArray
(.!) a ref = readArray a =<< get ref
get = readIORef
(.<) = liftM2 (<)
(.>) = liftM2 (>)
(.<=) = liftM2 (<=)
(.>=) = liftM2 (>=)
(.&&) = liftM2 (&&)
where doWhile cond foo = do
foo
b <- cond
when b $ doWhile cond foo
while cond foo = do
b <- cond
when b $ foo >> while cond foo
这里有一个简单的测试，以检查它是否有效。
main = do
a <- (newListArray (0,9) [10,9..1]) :: IO (IOUArray Int Int)
printArr a
putStrLn "Sorting..."
qsort a 0 9
putStrLn "Sorted."
printArr a
where printArr a = mapM_ (\x -> print =<< readArray a x) [0..9]
我在Haskell中并不经常编写命令式代码，所以我相信有很多方法可以清理这个代码。
那又怎么样？
您会注意到上面的代码非常长。尽管每行代码通常都要冗长一些，但其核心部分与C代码长度相当。这是因为C偷偷地做了很多让您可能视为理所当然的恶心的事情。例如，a[l] = a[h];。这个语句访问可变的变量l和h，然后访问可变数组a，最后改变可变数组a。天啊，变异了！在Haskell中，突变和访问可变变量是明确的。这个"假" qsort有吸引力的原因有很多，但其中最重要的一点是它不使用突变；这种自我限制使得它更容易一眼看懂。
O(N^2)。 - Thomas Eding