Arrays and lists

// Arrays, `for` loops, and generic functions over them.
//
// An array is a heap object with its length in the header and its elements
// inline -- the same shape a string literal has. Indexing bounds-checks and
// panics on failure, like `.?` on a null optional: a failure the type system
// permits but the program must not perform.

const array = @import("std/array");
const str = @import("std/str");

// A type parameter is written when it has to be named, and inferred when not.
fn first[T](a: []T) T { return a[0]; }

fn sum(xs: []i64) i64 {
    var total = 0;
    for (xs) |x| { total = total + x; }
    return total;
}

// `for (xs) |x, i|` binds the index as well as the element.
fn show(xs: []i64) str {
    var out = "";
    for (xs) |x, i| {
        if (i > 0) { out = str.concat(out, ", "); }
        out = str.concat(out, str.from_int(x));
    }
    return out;
}

fn main() i64 {
    const xs = []i64{ 3, 1, 4, 1, 5 };
    print(show(xs));
    print(sum(xs));
    print(first(xs));
    print(first([]str{ "a", "b" }));

    // Every one of these returns a new array: the length lives in the header,
    // so there is no capacity to grow into. `std/list` is the type that has
    // one -- see examples/list.ws.
    print(show(array.push(xs, 9)));
    print(show(array.slice(xs, 1, 4)));
    print(show(array.concat(xs, []i64{ 9, 2 })));

    // `a[i]` is a place as well as a value.
    var ys = []i64{ 1, 2, 3 };
    ys[1] += 10;
    print(show(ys));
    return 0;
}

wsharp run examples/arrays.ws

3, 1, 4, 1, 5
14
3
a
3, 1, 4, 1, 5, 9
1, 4, 1
3, 1, 4, 1, 5, 9, 2
1, 12, 3

// A growable array.
//
//   wsharp run examples/list.ws
//
// `[]T` is fixed-length: its count lives in the object header, and there is no
// capacity beside it, so `array.push` allocates a whole new array every call.
// `list.List[T]` is the second object that length needs -- a backing array
// whose header length is the *capacity*, and a count of how much of it is in
// use. Pushing writes into the spare tail; only a full list reallocates, and
// it doubles when it does, so a run of pushes is amortised constant time.
const list = @import("std/list");
const str = @import("std/str");

/// Collatz: how many steps `n` takes to reach 1, and the path it took.
fn path(n: i64) list.List[i64] {
    var steps: list.List[i64] = list.new();
    var v = n;
    list.push(steps, v);
    while (v != 1) {
        if (v % 2 == 0) { v = v / 2; } else { v = 3 * v + 1; }
        list.push(steps, v);
    }
    return steps;
}

fn show(xs: list.List[i64]) str {
    var out = "";
    // A list is walked directly: `for` over anything but an array calls `iter`
    // and `next` from the module that declares the type, so `std/list` says
    // how a list is iterated without the type checker knowing it exists.
    for (xs) |v, i| {
        if (i > 0) { out = str.concat(out, " -> "); }
        out = str.concat(out, str.from_int(v));
    }
    return out;
}

fn main() i64 {
    const p = path(7);
    print(show(p));
    print(list.len(p));

    // The list grew from nothing, so its capacity is the first power of two
    // past its length -- the spare tail is what makes the next push free.
    print(list.capacity(p));

    // Lists of references work the same way; a growth copies them through the
    // write and load barriers, which is why `std/list` is written in W#.
    var words: list.List[str] = list.new();
    list.extend(words, str.split("the quick brown fox", " "));
    list.push(words, "jumps");
    print(str.join(list.to_array(words), ","));

    // `pop` and `remove` hand a value back; both panic rather than returning
    // `?T`, for the reason `a[i]` does.
    print(list.pop(words));
    print(list.remove(words, 0));
    print(list.len(words));
    return 0;
}

wsharp run examples/list.ws

7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
17
32
the,quick,brown,fox,jumps
jumps
the
3