A list of your own

qdx has no generic types, so there is no one list that holds anything. The standard library has a list of bytes, bytes_list. For any other type, you declare a list yourself. It takes one line.

union int_list { no_ints(), int_then(first: int, rest: int_list) }

fn sum(items: int_list, total: int) -> int {
  match items {
    no_ints() => total,
    int_then(first, rest) => sum(rest, total + first)
  }
}

fn doubled(items: int_list) -> int_list {
  match items {
    no_ints() => no_ints(),
    int_then(first, rest) => int_then(first: first * 2, rest: doubled(rest))
  }
}

fn reversed_ints(items: int_list, done: int_list) -> int_list {
  match items {
    no_ints() => done,
    int_then(first, rest) => reversed_ints(rest, int_then(first: first, rest: done))
  }
}

fn text_of(items: int_list, done: bytes) -> bytes {
  match items {
    no_ints() => done,
    int_then(first, rest) => text_of(rest, concat3(done, " ", int_to_text(first)))
  }
}

fn main() -> int {
  let rolls = int_then(first: 3, rest: int_then(first: 5, rest: int_then(first: 6,
    rest: no_ints())));
  print(concat5(int_to_text(sum(rolls, 0)), " /", text_of(doubled(rolls), ""), " /",
    text_of(reversed_ints(rolls, no_ints()), "")));
  print("\n")
}

bootstrap/qdx run std/*.qdx rolls.qdx

14 / 6 10 12 / 6 5 3

The shape

A list is a union with two cases: one for the empty list, and one holding an item and the rest of the list. Every function over it is a match with one arm for each.

Three ways to walk it

• Fold it into one value. sum carries the answer in a parameter and calls itself last, so it runs in constant stack however long the list is.
• Build a new list of the same length. doubled makes a new item, then the rest. The call to itself is not last here, because the result still has to be wrapped, so it uses stack in proportion to the length. That is fine for lists of thousands of items.
• Build a list backwards. reversed_ints moves items one at a time onto a second list. It runs in constant stack.

For a very long list, build the result backwards with a carried parameter, then reverse it once at the end.

Naming

Case names are shared across the whole program, so two lists cannot both call their empty case empty. Put the item type in the names, as no_ints and int_then do.