Standard ML does not have a syntax for array literals or vector literals. The only way to write down an array is like
Array.fromList [w, x, y, z]
No SML compiler produces efficient code for the above expression. The
generated code allocates a list and then converts it to an array. To
alleviate this, one could write down the same array using
Array.tabulate
, or even using Array.array
and Array.update
, but
that is syntactically unwieldy.
Fortunately, using Fold, it is possible to define constants A
,
and `
so that one can write down an array like:
A `w `x `y `z $
This is as syntactically concise as the fromList
expression.
Furthermore, MLton, at least, will generate the efficient code as if
one had written down a use of Array.array
followed by four uses of
Array.update
.
Along with A
and `
, one can define a constant V
that makes
it possible to define vector literals with the same syntax, e.g.,
V `w `x `y `z $
Note that the same element indicator, `
, serves for both array
and vector literals. Of course, the $
is the end-of-arguments
marker always used with Fold. The only difference between an
array literal and vector literal is the A
or V
at the beginning.
Here is the implementation of A
, V
, and `
. We place them
in a structure and use signature abstraction to hide the type of the
accumulator. See Fold for more on this technique.
structure Literal:>
sig
type 'a z
val A: ('a z, 'a z, 'a array, 'd) Fold.t
val V: ('a z, 'a z, 'a vector, 'd) Fold.t
val ` : ('a, 'a z, 'a z, 'b, 'c, 'd) Fold.step1
end =
struct
type 'a z = int * 'a option * ('a array -> unit)
val A =
fn z =>
Fold.fold
((0, NONE, ignore),
fn (n, opt, fill) =>
case opt of
NONE =>
Array.tabulate (0, fn _ => raise Fail "array0")
| SOME x =>
let
val a = Array.array (n, x)
val () = fill a
in
a
end)
z
val V = fn z => Fold.post (A, Array.vector) z
val ` =
fn z =>
Fold.step1
(fn (x, (i, opt, fill)) =>
(i + 1,
SOME x,
fn a => (Array.update (a, i, x); fill a)))
z
end
The idea of the code is for the fold to accumulate a count of the
number of elements, a sample element, and a function that fills in all
the elements. When the fold is complete, the finishing function
allocates the array, applies the fill function, and returns the array.
The only difference between A
and V
is at the very end; A
just
returns the array, while V
converts it to a vector using
post-composition, which is further described on the Fold page.