lists.deed

// Holding more than one of something, which until now the language could not
// do at all.
//
// Every program written in Deed before this file worked on a fixed number of
// named variables. There was no way to say "these things", so there was no way
// to read input, no way to build a report, and no way to write down almost any
// problem worth writing down. That is a bigger hole than any of the ones the
// type checker had.
//
// `List` is built in rather than declared, and it was once because there was
// no way to declare a generic type. There is now: `examples/generic_types.deed`
// declares `Pair` and `Option`, `std/table` declares `Entry`, and
// `examples/tree.deed` declares `Tree`. So the shortcut it takes, comparing
// element types componentwise and letting an unknown one absorb, is a choice
// rather than the only thing available.
//
// It stayed a choice on purpose. Moving `List` out would move the type, which
// lives in one crate, and leave behind the syntax over it, which does not:
// `[1, 2, 3]` has to build something, and `for` is the only loop in the
// language and walks nothing else. That is measured in design/02-syntax.md.

module examples/lists

// The first element decides the element type. There is nothing to meet two
// candidates with, so the rule is the one that fits in a sentence.
fn digits() -> List<Int> {
    [1, 2, 3]
}

// `[]` is a list of nothing in particular, which is what lets it stand in for
// a list of anything. Same trick as `ok(x)` saying nothing about the error.
fn nothing() -> List<String> {
    []
}

// `length` measures a list for the same reason it measures a string, and it is
// still never negative, so this is settled ahead of time rather than checked
// again when it runs.
type Counted = Int where value >= 0

fn count(items: List<Int>) -> Counted {
    length(items)
}

// `at` hands back a `Result` rather than the element. An index nobody promised
// is there is not a mistake in the caller, and nothing in this language stops
// a program, so it is an error value like every other thing that can fail.
fn first(items: List<String>) -> Result<String, String> {
    at(items, 0)
}

// `push` does not change the list it was given. Handler state is the only
// mutable thing in Deed, and a collection that could be written through would
// quietly be a second one.
fn with_item(items: List<String>, item: String) -> List<String> {
    push(items, item)
}

// Walking one is a `for`, which is a fold with syntax: `sum` is bound again on
// every turn rather than assigned, so iteration exists and handler state is
// still the only mutable thing in the language. It walks a list that already
// exists, so it stops, so there is nothing to declare.
fn total(numbers: List<Int>) -> Int {
    for n in numbers with sum = 0 {
        sum + n
    }
}

// What is deliberately missing: a way to declare `List<T>` yourself, maps,
// sets, `break`, and any operation that takes a function. The last one needs a
// row on a function type, which is the piece the effect system is still short
// of, so `map` and `filter` are waiting on the same thing.

test "a literal decides its element type" {
    assert digits() == [1, 2, 3]
    assert count(digits()) == 3
    assert count([]) == 0
}

test "an empty list fits where any list was wanted" {
    assert nothing() == []
    assert with_item([], "milk") == ["milk"]
}

test "reading past the end is a value, not a crash" {
    assert first(["a", "b"]) == ok("a")
    assert first([]) == err("index 0 is outside a list of 0")
}

test "push leaves the original alone" {
    let start = ["milk"]
    let longer = with_item(start, "bread")

    assert start == ["milk"]
    assert longer == ["milk", "bread"]
}

test "walking one is a fold" {
    assert total([1, 2, 3]) == 6
    assert total([]) == 0
}