Clean и Array Slice

[rdia]

Непонятно, почему в Clean, где есть изменяемые массивы, построенные на unique types, нет такой вещи, как ARRAY_SLICE в терминах SML или std::slice в терминах Rust. Конечно, при этом придётся немного разрушить uniqueness, но зато ряд алгоритмов из семейства "разделяй и властвуй" станет намного проще. Собственно, ниже определение ArraySlice и две основные функции
:: ArraySlice a = ArraySlice .(.{!a}, Int, Int)

split :: !*(ArraySlice a) !Int -> *(*(ArraySlice a), *(ArraySlice a))
split (ArraySlice (arr, i, sz)) j
    | j >= sz = abort "Attempt to make slice after end"
    | j <= i  = abort "Attempt to make slice before beginning"
    | otherwise = (ArraySlice (arr`, i, j), ArraySlice (arr``, i + j, sz - j))
        where (arr`, arr``) = unsafeArrayDup arr
              // Helper function, which overcomes uniqueness restrictions
              unsafeArrayDup :: u:{!a} -> u:(u:{!a}, u:{!a})
              unsafeArrayDup x =
                  code
                  {
                      push_a 0
                      push_a 1
                      update_a 1 2
                      updatepop_a 0 1
                  }

merge` :: !*(ArraySlice a) !*(ArraySlice a) -> *(ArraySlice a)
merge` (ArraySlice (arr, i, sz)) (ArraySlice (arr`, i`, sz`))
    | (size arr) <> (size arr`) = abort "Different arrays" // FIX проверка должна быть лучше
    | (i + sz) <> i`            = abort "Slices are not adjacent"
    | otherwise = ArraySlice (arr, i, sz + sz`)

Функция split разделяет один на два соседних, при этом сам массив наследуется, а merge склеивает два соседних среза. В функции merge не хватает проверки, что arr и arr` - это один и тот же массив, но её можно дописать, подшаманив с ABC машиной.

Написать instance Array ArraySlice a тривиально и занудно. Единственный сложный момент - как отсчитывать индексы: от начала массива или от начала среза.

Далее, имея функцию swap, которую я написал ниже, мы легко можем написать любимый quicksort на срезах.