Честный quicksort на чистом ленивом языке

[rdia]

Не только лишь все знают, что обычный Хаскельный пример quicksort'а несколько жульнический. Тем не менее, можно сделать реальный in-place quicksort на изменяемых массивах. Ниже - программа на Clean:
module quicksort
import StdEnv
import StdClass

swap :: !*(a e) !Int !Int-> *(a e) | Array a e
swap arr i j
    | i == j = arr
    | i <> j = arr```
    where (a_i, arr`)   = uselect arr i
          (a_j, arr``)  = replace arr`  j a_i
          (_, arr```)   = replace arr`` i a_j

partition :: !*(a e) !Int !Int -> (Int, *(a e)) | Array a e & Ord e
partition arr lo hi = go (uselect arr hi) lo lo
    where go (pivot, arr) i j
            | j >= hi   = (i, swap arr i hi)
            | otherwise = if (a_j < pivot)
                            (go (pivot, swap arr` i j) (i + 1) (j + 1))
                            (go (pivot, arr`) i (j + 1))
                          where (a_j, arr`) = uselect arr j

quicksort :: !*(a e) !Int !Int -> *(a e) | Array a e & Ord e
quicksort arr lo hi
            | lo >= hi  = arr
            | otherwise = quicksort arr`` p hi
                          where arr``     = quicksort arr` lo (p - 1)
                                (p, arr`) = partition arr  lo hi

Start :: *{#Real}
Start = quicksort {1.0, 2.0, 4.0, 3.0, 0.0} 0 4

По итогам эксперимента выяснилось, что писать на unique types крайне неудобно. Библиотека совершенно не продумана в плане работы с массивами - мне пришлось вводить даже функцию swap. Явно не хватает аналогов VectorSlice из SML.

С другой стороны, размер кода примерно такой же, как и на императивном псевдокоде, при том, что явно можно ещё подсократить код, если ввести оператор применения $ и поиграться с порядоком аргументов функций.

Ну и есть предложение переписать программу на линейных типах Хаскеля.