True QuickSort в стандарте ML

Question

С RosettaCode's Standard ML solution является очень медленной версией Quicksort в соответствии с вопросом (и обсуждением) «Why is the minimalist, example Haskell quicksort not a "true" quicksort?», как бы функциональный Quicksort выглядел в стандартном ML, если он вел себя в соответствии со сложностью Hoare's algoritm?

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

То есть, который использует некоторые аспекты функционального программирования там, где это имеет смысл. В отличие от версии Haskell, для которой нуждается в, чтобы инкапсулировать ее местное разбиение на разделы, возникла бы необходимость в QuickSort в SML, чтобы каким-либо образом отличаться от версии C помимо синтаксиса? Независимо от того, принимает ли функция массив/вектор или проводит O (n) преобразование времени менее актуально.

Редактировать: Перефразированный вопрос относительно комментариев Джона Колмана.

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, чем я, может придумать более идиоматический qmort SML.