// Test value
var N = 10;

// Empty array
var x1 = [];

// Finite array
var x2 = [1, 2, 3];

// Infinite bi-dimensional array
var x3 = [(i, j) -> i * j];

// Finite 3x3 sub-array defined as a bi-dimensional slice of x3
var x4 = x3[5..8, 5..8];

// Print the value of x4[i, j] for i in 0..2 and j in 0..2
for (i < 3) {
  for (j < 3) {
    @ print("x4[%d, %d] = %d\n", i, j, x4[i, j]);
  }
}

// Infinite recursively-defined array
var fact = [1, i -> i * fact[i-1]];

// Compute the sum of the first N+1 elements of "fact" using an array
// "sum1" such that "sum1[i]" is the sum of "fact[j]" for "j" smaller
// than "i". We use a very simple iterative definition of "sum1" using
// a "for" loop
var sum1;
sum1[0] = fact[0];
for (i < N) {
  sum1[i + 1] = fact[i + 1] + sum1[i];
}

// The version above is straightforward, but a little verbose. We can
// do better and define "sum2" by a unique recursive definition (note
// that "sum2" is an infinite array in this case)
var sum2 = [fact[0], i -> fact[i] + sum2[i-1]];

// Instead of using an array to store the partial sums of "fact", we
// can define a generic function computing the sum of the first n+1
// elements of an array from right to left (note the use of a run-time
// checked array size assertions "x: int[n + 1]" on the formal
// parameter "x")
fun sum3(n)(x: int[n + 1]) = (n == 0) ? x[0] : (sum3(n - 1)(x) + x[n]);

// Building on the same idea of using a recursive function to compute the sum
// of an array, we can abstract the folding of the array using the "+"
// operation by defining an abstract folding function taking an array "x" of
// elements of type "T", an initial value "u" of some other type "U" used to
// initialize the folding (u=0 for the sum), and a function "f" taking an
// element of type "U" (the current value of the fold operation) together with
// the current element of "x" of type "T" (f="+" for the sum), and returns the
// new current value of the fold operation (of type "T"). This function
// returns an array "y" such that:
//
//   y[0] = x[0];
//   y[i] = f(y[i-1], x[i-1]) for i > 0
//
fun fold(x, u, f) = y
{
  y = [u, i -> f(y[i-1], x[i-1])];
}

// We now apply the "fold" function to the "+" function, so that "sum4"
// returns an array "y" containing the cumulative sum of elements in "x"
fun sum4(n)(x) = fold(x, 0, (+\2))[n + 1];

// In order to illustrate the construction of the array "sum1" of
// partial sums by printing all the prefixes "sum1[0..k]" of "sum1",
// we define a function "prefixes" returns an array containing the
// string representation of the content of all the array slices
// "x[0..k]" of "x" by folding "x" using the "concat" function
fun prefixes(x) = fold(x, "", concat)
{
  fun concat(u: String, t) = (u.length() == 0 ?
                              t.toString() :
                              format("%s, %a", u, t));
}

// Print the sums
@ print("sum1 = %d\nsum2 = %d\nsum3 = %d\nsum4 = %d\n",
        sum1[N], sum2[N], sum3(N)(fact), sum4(N)(fact));

// Print a string representation of the first N prefixes of "sum1"
var pr = prefixes(sum1);
for (i < N - 1) {
  @ print("%s\n", pr[i + 1]);
}

// Sorting of a finite array of random numbers
var nums: int[30] = [i -> Integer.random(1000)];
var snums = Comparable.sort(nums);
for (k < snums.length) {
  @ print("snums[%d] = %d\n", k, snums[k]);
}