標準MLのTrue QuickSort

Question

は、質問（およびディスカッション） "Why is the minimalist, example Haskell quicksort not a "true" quicksort?"によるQuicksortの非常に遅いバージョンなので、機能的Quicksortは、Hoare's algoritmの複雑さに従って動作すれば、どのように標準MLのように見えますか？

fun quicksort [] = [] 
    | quicksort (x::xs) = 
    let 
     val (left, right) = List.partition (fn y => y<x) xs 
    in 
     quicksort left @ [x] @ quicksort right 
    end 

つまり、意味があるところで機能プログラミングのいくつかの側面を採用するものです。 には、インプレースパーティショニングをカプセル化するために、にはが必要なHaskellのバージョンとは異なり、SバージョンのQuicksortは構文の他にCバージョンからどのように変化する必要がありますか？関数が配列/ベクトルを受け入れるかどうかを指定します。O（n）リストの変換に時間がかかりません。

編集： John Colemanのコメントに関する言い換えられた質問。ここで

Answer 1

は私の試みです：

fun swap(A,i,j) = 
    let 
     val t = Array.sub(A,i) 
    in 
     Array.update(A,i,Array.sub(A,j)); 
     Array.update(A,j,t) 
    end 

fun firstAfter(A,i,f) = 
    if f(Array.sub(A,i)) then i else firstAfter(A,i+1,f) 

fun lastBefore(A,j,f) = 
    if f(Array.sub(A,j)) then j else lastBefore(A,j-1,f) 

fun partition(A,lo,hi)= 
    let 
     fun partition'(A,lo,hi,pivot) = 
      let 
       val i = firstAfter(A,lo,fn k => k >= pivot) 
       val j = lastBefore(A,hi,fn k => k <= pivot) 
      in 
       if i >= j then 
        j 
       else 
       (
        swap(A,i,j); 
        partition'(A,i+1,j-1,pivot) 
       ) 
      end 
    in 
     partition'(A,lo,hi,Array.sub(A,lo)) 
    end 

fun quicksort(A,lo,hi) = 
    if hi <= lo then 
     () 
    else 
     let 
      val p = partition(A,lo,hi) 
     in 
      (
       quicksort(A,lo,p); 
       quicksort(A,p+1,hi) 
      ) 
     end; 

fun qsort A = quicksort(A,0,Array.length A - 1); 

それはかなり密接ウィキペディアで説明したようにHoare's algorithm次のではなく、ループよりも再帰を使用し、交換するインデックスのペアを探しているため、多少の機能的なアプローチがあります。これは、2行または3行の疑似クイックソートと同じくらいエレガントで、関数型プログラミングの入門的な扱いでよく教えられ、関数型プログラミングの力を実際には示していないことは疑いありません。うまくいけば、私よりもSMLをよく知っている人は、もっと慣れ親しんだSML qsortを思いつくことができます。