Haskell 对普通数组进行快速排序 - 可能吗？

Question

在自学过程中 haskell，我正在尝试实现快速排序。为方便起见，我将自己限制在 ghc 附带的包中，这就是我使用 Array 而不是 Vector 的原因：

import Data.Array

type ArrayT = Array Int

quickSort :: Ord t => ArrayT t -> ArrayT t
quickSort a = rQuickSort (bounds a) a

rQuickSort :: Ord t => (Int, Int) -> ArrayT t -> ArrayT t
rQuickSort (beg,end) arr | beg >= end = arr
rQuickSort (beg,end) arr = 
  rQuickSort (beg, pivIndex) . rQuickSort (pivIndex+1, end) $ parted 
  where
    (pivoted, pivValue) = med3pivot (beg, end) arr
    (parted , pivIndex) = partition (beg+1, end-1) pivoted pivValue

med3pivot :: Ord t => (Int, Int) -> ArrayT t -> (ArrayT t, t)
med3pivot (beg, end) = 
  let mid = (beg + end) `div` 2 
    in (\arr -> (arr,arr!mid))
    . (\arr -> if arr!end < arr!mid then swap end mid arr else arr)
    . (\arr -> if arr!mid < arr!beg then swap mid beg arr else arr)
    . (\arr -> if arr!end < arr!beg then swap end beg arr else arr)
    
partition :: Ord t => (Int, Int) -> ArrayT t -> t -> (ArrayT t, Int)
partition (beg, end) arr piv =
  let fw = findForward  (piv <) (beg,end) arr
      bw = findBackward (piv >) (beg,end) arr
    in if fw >= bw then (arr, bw) 
                   else partition (fw+1, bw-1) (swap fw bw arr) piv

findForward :: (t -> Bool) -> (Int, Int) -> ArrayT t -> Int
findForward _ (b,e) _ | b > e = b
findForward p (b,e) a = if p (a!b) then b else findForward p (b+1,e) a

findBackward :: (t -> Bool) -> (Int, Int) -> ArrayT t -> Int
findBackward _ (b,e) _ | b > e = e
findBackward p (b,e) a = if p (a!e) then e else findBackward p (b,e-1) a 

swap :: Int -> Int -> ArrayT t -> ArrayT t
swap i j arr = arr // [(i, arr!j), (j, arr!i)]

mkArray :: [a] -> Array Int a
mkArray xs = listArray (0, length xs - 1) xs

我显然弄错了。我得到运行大约 8 秒的时间来排序 10000 个短字节串的数组（现在省略驱动代码，因为这已经是一堆）。我想我没有正确理解一般的懒惰，以及数组副本发生的地方。感谢任何指点。

（我找到了这个使用 Array.ST 的答案但我仍然想知道我的代码有什么问题。是否有可能使用普通数组进行就地排序就像我在尝试？）

Answer 1

Array 是一种不可变数据类型，因此每次交换都会构造一个新数组“spine”，尽管元素（即 t 类型的值）是共享的。

你通常应该使用 Array 来计算诸如记忆表之类的东西，比如从其他语言翻译动态编程算法时，而不是像这样的顺序算法。当您使用相互引用（无循环）的 thunk 填充元素并从索引中读取以计算和缓存该索引的元素时，数组效果最佳。

获得实际就地排序的唯一方法是在 ST 或 IO 中使用可变数组类型。但是，我认为您也可以通过构建一系列条件交换（即排序网络）并将其仅应用于输入数组 once 来更有效地进行这种不可变数组排序生成输出数组。

Haskell 对普通数组进行快速排序 - 可能吗？

Haskell quicksort on plain arrays - possible?

arrays

haskell

quicksort