# Lists

A list holds items of one type in order, like an array in TypeScript,
except that it never changes: every operation that changes a list gives
you a new one. Each operation is called through the `list` namespace, as
`list.<name>`. In the table below, `T` is the item type.

The list fixes the item type. A list written out of values fixes it for
the call it is passed to, as in `list.sort_by([oat, zopf], product ->
...)`. A list with a literal in it takes the parameter's type.

`collection` is a reserved namespace with no operations. A call through
it is `semantic.standard_operation_moved`, and its edit writes `list.`,
`set.` or `map.`: chosen by the type of the call's first value when that
value is a name or a field, and `list.` otherwise. The call is then
checked as that operation.

Some operations take a function, written inline as `item -> expression`
([Passing functions](passing-functions.md)). Three operations
give their function two values: `list.zip_with` gives an item from each
list, and `map.filter` and `map.map_values` give an entry's key and its
value. Their function takes two parameters, written in parentheses,
`(key, value) -> ...`, and only that way. A function with one parameter
is never written `(item) ->`. Each parameter takes the type of the value
the operation gives in its place, and you don't have to use every one.
(The operations' declarations write such a function as
`Function<K, V, U>`, the last type being its result.)

A function with a different number of parameters than the operation
gives is `type.inline_function_parameters`
([Two parameters](passing-functions.md#two-parameters)). A function with two
parameters anywhere but these three operations is
`type.inline_function_placement`, and its reason names the three.

| Operation | Gives | Fails | SQL form |
|---|---|---|---|
| `count(items)` | `Int`, at least 0 | | `jsonb_array_length(x)::bigint` |
| `contains(items, item)` | `Bool`: an item `==` `item` | | none |
| `map(items, each)` | `List<U>`, in order | | none |
| `filter(items, keep)` | `List<T>`, the items `keep` accepts, in order | | none |
| `sum(items)` | `Int` or `Decimal`, the items added; `0` for none. Items built on `Int` or `Decimal`; `Money` uses `money.sum` | overflow is a defect | none |
| `any(items, check)` | `Bool`: `check` accepts at least one; `false` for none | | none |
| `all(items, check)` | `Bool`: `check` accepts every one; `true` for none | | none |
| `find(items, check)` | `T?`, the first item `check` accepts | | none |
| `first(items)`, `last(items)` | `T?` | | none |
| `at(items, position)` | `T?`, the item at `position` (0 is the first); `position` never negative | | none |
| `min_by(items, key)`, `max_by(items, key)` | `T?`, the item with the smallest or largest key; the first of equal ones | | none |
| `sort_by(items, key, locale:)` | `List<T>`, ordered by `key` ascending; equal keys keep their order. `key` gives a number, a time, a date, a duration, text or a standard type the contract orders (`Money` of one currency): text in code points as queries sort it, or by a locale's rules with `locale:` | | none |
| `reverse(items)` | `List<T>`, last item first | | none |
| `distinct(items)` | `List<T>`, each item's first occurrence, by `==` | | none |
| `slice(items, from, count)` | `List<T>`, up to `count` items from position `from`, cut short at the end; both never negative | | none |
| `keep_first(items, n)`, `keep_last(items, n)` | `List<T>`, at most `n` items from that end; `n` never negative | | none |
| `drop_first(items, n)`, `drop_last(items, n)` | `List<T>` without `n` items from that end; all gone when `n` is longer; `n` never negative | | none |
| `append(items, item)` | `List<T>`, `item` added at the end | | none |
| `concat(first, second)` | `List<T>`, `first`'s items then `second`'s | | none |
| `flatten(lists)` | `List<T>` from a `List<List<T>>`, in order | | none |
| `group_by(items, key)` | `Map<K, List<T>>`: each key with its items in order | | none |
| `zip_with(first, second, (a, b) -> ...)` | `List<U>`, pairing items by position, as long as the shorter | | none |

- **No push or pop.** A list's items never change
  ([Values never change](values-never-change.md)). To
  add an item, `list.append(items, item)` gives a new list. To take the
  last item off, read it with `list.last`, then `list.drop_last(items, 1)`
  gives the rest.
- **The largest is `max_by`,** not `first(reverse(sort_by(...)))`, which
  sorts the whole list to read one item. In a query, you still write
  `order:` and `limit:`.
- **Cutting from either end.** `keep_first`, `keep_last`, `drop_first`
  and `drop_last` cut items from either end, and text has the same four.
  `slice` is for a window in the middle. No position counts back from the
  end: a count or a position is never negative, and one that might be
  doesn't compile (the operation's `never_negative`). A literal below `0`,
  or a value whose type has no `min` of at least `0`, is
  `type.argument_negative`. A call's result, `list.count`'s included, is
  a plain `Int`, which proves nothing about its sign, so build a count as
  a type with `min: 0` first.
- **Keys that order.** `sort_by`, `min_by` and `max_by` need a key that
  can be put in order: one built on a number, `Text`, `Instant`,
  `CalendarDate` or `Duration`, or a standard type the contract marks
  ordered. The key can never be `none`. A `ZonedTime` has no order of its
  own, just as `<` doesn't compare one
  ([Expressions and operators](expressions-and-operators.md)),
  so use its instant as the key (`temporal.instant`). Any other key is
  `type.ordering_operand`. Keys compare in the canonical order, the one
  fixed order Jadpo gives every type's values
  ([Collections](collections.md), "Set order"), so
  text sorts by code point, or by a locale's rules with `locale:`
  ([Text](text.md)).
- **Named types.** An operation that gives `T`, `T?` or `List<T>` keeps
  the items' named type, such as `Batch` or `BatchWeight`. It doesn't keep
  a named list type, because `filter` or `drop_first` can break that
  type's `min_length`; build the result back into it by construction
  ([Named collection construction](collections.md#named-collection-construction)).
  `flatten` takes a `List<List<T>>`. Collections are invariant: a list of
  a named list type doesn't stand in for a `List<List<T>>`.
- **Equal means `==`.** `group_by` groups items whose keys are `==`, and
  gives the keys in the canonical order, so a key may be of any type.
  `distinct` keeps each item's first occurrence, found through the
  canonical order, which agrees with `==` for values of one type.
- **There is no `items[i]`.** Use `list.at`, which gives `T?`, and handle
  the missing case with `match`. An index can be out of range, so
  `items[i]` would need a failure arm or a defect.
- **`sum` gives a representation,** as `+` does: an `Int` or a `Decimal`,
  by its items' representation. An empty list gives `0` or `0.00`, as its
  type says. `Stock(list.sum(counts))` builds the result back into a named
  type. When the items' type has a `min` of at least `0`, the sum is
  proved to be at least `0`, so building it needs no arm for `min`. It
  still needs one for `max` when the type has one.
- **No `reduce`, `fold` or comparator.** To accumulate, use a `for` loop
  with a `var mut`, or `sum` for the common case. To sort, give `sort_by`
  a key, and `reverse` the result for the other direction; there is no
  sort with a comparator function.

A day's baking, through every list operation:

```jadpo
type BatchName = Text {
    min_length: 1
    max_length: 40
}

type BatchWeight = Mass {}

type Shelf = Int {
    min: 1
    max: 6
}

type LoafPrice = Decimal {
    scale: 2
    min: 0.00
}

type Batch = Object {
    name: BatchName
    weight: BatchWeight
    shelf: Shelf
    price: LoafPrice
}

type OverPlan = Bool {}

/// The flour a day's batches take: `list.sum` adds numbers, and
/// `units.sum` adds quantities of one kind.
function flour_needed(bakings: List<Batch>) -> BatchWeight {
    return BatchWeight(units.sum(list.map(bakings, batch -> batch.weight)))
}

/// The day's takings at full price.
function takings(bakings: List<Batch>) -> LoafPrice {
    return LoafPrice(list.sum(list.map(bakings, batch -> batch.price)))
}

/// The heaviest batch, if there is one: `max_by` reads each batch once,
/// where sorting would order them all to read one.
function heaviest(bakings: List<Batch>) -> Batch? {
    return list.max_by(bakings, batch -> batch.weight)
}

/// The batches on each shelf, in baking order.
function by_shelf(bakings: List<Batch>) -> Map<Shelf, List<Batch>> {
    return list.group_by(bakings, batch -> batch.shelf)
}

/// Whether each batch came out heavier than planned, batch by batch: a
/// two-parameter inline function is given one item from each list.
function over_plan(bakings: List<Batch>, goals: List<BatchWeight>) -> List<OverPlan> {
    return list.zip_with(bakings, goals, (batch, goal) -> OverPlan(batch.weight > goal))
}
```

Each operation gives a new list, or an item of the list as it is, still
a `Batch`. `takings([])` is `0.00`, a `Decimal`, because a sum has its
items' representation even when there are none. `by_shelf`'s map is read
with `map.get` and `map.keys` ([Maps](maps.md)).

```jadpo
test "list operations give new lists and keep the items as they are" {
    var rye: Batch = Batch {
        name: "Rye"
        weight: 800g
        shelf: 2
        price: 4.20
    }
    var bap: Batch = Batch {
        name: "Bap"
        weight: 90g
        shelf: 1
        price: 0.60
    }
    var spelt: Batch = Batch {
        name: "Spelt"
        weight: 800g
        shelf: 2
        price: 3.80
    }
    var day: List<Batch> = [rye, bap, spelt]
    var weights: List<BatchWeight> = [800g, 90g, 800g]
    assert flour_needed(day) == 1690g
    assert takings(day) == 8.60
    assert takings([]) == 0.00
    assert list.any(day, batch -> batch.shelf == 1)
    assert not list.all(day, batch -> batch.weight > 100g)
    assert list.find(day, batch -> batch.shelf == 2) == rye
    assert list.first(day) == rye
    assert list.last(day) == spelt
    assert list.at(day, 1) == bap
    assert list.at(day, 3) == none
    assert heaviest(day) == rye  // the first of equal keys
    assert list.min_by(day, batch -> batch.price) == bap
    assert list.sort_by(day, batch -> batch.name) == [bap, rye, spelt]
    assert list.sort_by(day, batch -> batch.weight) == [bap, rye, spelt]  // equal keys keep their order
    assert list.reverse(day) == [spelt, bap, rye]
    assert list.distinct(weights) == [800g, 90g]
    assert list.slice(day, 1, 5) == [bap, spelt]
    assert list.keep_first(day, 2) == [rye, bap]
    assert list.keep_last(day, 2) == [bap, spelt]
    assert list.drop_first(day, 1) == [bap, spelt]
    assert list.drop_last(day, 5) == []
    assert list.append([rye], bap) == [rye, bap]
    assert list.concat([rye], [bap, spelt]) == day
    assert list.flatten([[rye], [], [bap, spelt]]) == day
    assert over_plan(day, [700g, 100g, 800g]) == [true, false, false]
    assert over_plan(day, [700g]) == [true]  // as long as the shorter
}

test "group_by keeps each shelf's batches in baking order" {
    var rye: Batch = Batch {
        name: "Rye"
        weight: 800g
        shelf: 2
        price: 4.20
    }
    var bap: Batch = Batch {
        name: "Bap"
        weight: 90g
        shelf: 1
        price: 0.60
    }
    var spelt: Batch = Batch {
        name: "Spelt"
        weight: 800g
        shelf: 2
        price: 3.80
    }
    var shelves: Map<Shelf, List<Batch>> = by_shelf([rye, bap, spelt])
    assert map.keys(shelves) == [1, 2]
    assert map.get(shelves, 2) == [rye, spelt]
    assert map.get(shelves, 1) == [bap]
    assert map.get(shelves, 3) == none
    assert map.count(by_shelf([])) == 0
}
```

A count or a position that might be negative is `type.argument_negative`
([Errors](standard-library.md#errors)), and a key that gives something with no order, such
as a `Bool`, is `type.ordering_operand`.