Есть ли способ сделать обработку массивов в 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 реализация (особенно push/pop) становится трудной для чтения.

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

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

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

Если вас интересует распределение, связанное со списками, то обратите внимание, что (а) он не выполняет больше выделений, чем версия массива (один:: вместо одного SOME на push), и (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, Я сделал это только для демонстрации, в этом примере это не стоит того, только с одним таким использованием.