Есть ли способ сделать обработку массивов в SML более приятной?

Question

При реализации алгоритмов в SML я часто задаюсь вопросом, есть ли простой способ сделать код, который значительно облегчает использование массивов. Например, если я определить функцию SML поменять местами 2 элемента в массиве, код ...

local open Array in 
    fun exch (a, i, j) = 
    let 
     val tmp = sub (a, i) 
     val _ = update (a, i, sub (a, j)) 
     val _ = update (a, j, tmp) 
    in() end 
end 

То, что я хотел бы иметь более удобен, уборщик версии, как в этом Scala-сниппета .. .

def exch[T](a: Array[T], i: Int, j: Int) { 
    val tmp = a(i) 
    a(i) = a(j) 
    a(j) = tmp 
} 

Для чего-то простого, как замена 2 элементов в массиве, версия SML в порядке. Но как только алгоритмы становятся более сложными, код становится все более непонятным и запутывает основной алгоритм.

Несколько более сложный пример будет этот стек (реализован в виде перезначительном массива) ...

structure ArrayStack = struct 
    type 'a stack = ('a option array * (int ref)) ref 
    exception Empty 
    fun mkStack() = ref (Array.array (1, NONE), ref 0) 
    fun isEmpty (ref (_, ref 0)) = true 
    | isEmpty _ = false 
    fun resize (array as ref (xs, n), capacity) = 
     let 
     val length = Array.length xs 
     in 
     array := (Array.tabulate (
        capacity, 
        fn i => if i < length then Array.sub (xs, i) else NONE 
        ), n) 
     end 
    fun push (array as ref (xs, n : int ref), x) = 
    if Array.length xs = !n then (
     resize (array, !n*2) 
    ; push (array, x)) 
    else (
     Array.update (xs, !n, SOME x) 
    ; n := !n+1) 
    fun pop (ref (xs, ref 0)) = raise Empty 
    | pop (array as ref (xs, n : int ref)) = let 
     val _ = (n := !n-1) 
     val x = Array.sub (xs, !n) 
     val _ = Array.update (xs, !n, NONE) 
     val q = (Array.length xs) div 4 
     val _ = if !n > 0 andalso !n = q then resize (array, q) else() 
    in 
     valOf x 
    end 
end 

По сравнению с реализацией Java в http://algs4.cs.princeton.edu/13stacks/ResizingArrayStack.java.html осуществления (особенно нажимной/поп) становится трудно читать ,

Как я могу сделать такой код более удобочитаемым?

Answer 1

Это правда, массивы довольно неудобны для использования в SML. В определенной степени это преднамеренно, препятствовать их использованию - потому что большую часть времени они не лучший выбор структуры данных. Ваш стек является хорошим примером, поскольку он гораздо лучше реализован в виде списка:

structure ListStack = 
struct 
    type 'a stack = 'a list ref 

    fun stack() = ref nil 
    fun isEmpty s = List.null (!s) 
    fun push (s, x) = s := x::(!s) 
    fun pop s = 
     case !s of 
     nil => raise Empty 
     | x::xs => (s := xs; x) 
end 

(На самом деле, вы даже не обычно делают это, и избежать запоминанием состояния структуры данных, как это в целом, используя простые списки вместо этого.)

Если ваша проблема связана с списками, то обратите внимание, что (a) он не делает больше распределений, чем версия массива (один :: вместо одного НЕКОТОРЫЙ для каждого нажатия) и (b) распределения очень дешевы на языке, подобном SML.

Но поскольку ваш вопрос об использовании массивов, вот несколько более идиоматической реализация вашего стека массива:

structure ArrayStack = 
struct 
    open Array infix sub 

    datatype 'a stack = Stack of {data : 'a option array ref, size : int ref} 

    fun stack() = Stack {data = ref (array (1, NONE)), size = ref 0} 

    fun isEmpty (Stack {size, ...}) = !size = 0 

    fun resize (data, len') = 
     let val data' = array (len', NONE) in 
     copy {src = !data, dst = data', di = 0}; 
     data := data' 
     end 

    fun push (Stack {data, size}, x) = 
     let val size' = !size + 1 in 
     if size' > length (!data) then resize (data, !size * 2) else(); 
     update (!data, !size, SOME x); 
     size := size' 
     end 

    fun pop (Stack {data, size}) = 
     if !size = 0 then raise Empty else 
     let 
     val _ = size := !size - 1 
     val x = !data sub (!size) 
     val q = length (!data) div 4 
     in 
     update (!data, !size, NONE); 
     if q > 0 andalso !size = q then resize (data, q) else(); 
     valOf x 
     end 
end 

В частности, я сделал sub инфикс, что позволяет писать arr sub i. Я сделал это только для демонстрации, в этом примере это действительно не стоит, только с одним таким использованием.