Add keyed lists and text comparison

state xs: list of R by field keeps its items in that field's order, each
key once: xs.add(R { ... }) places an item (a taken key fails the event
with exists), xs[key] finds one by halving (its field, or its index),
xs.has(key) asks, xs.remove(key) removes. append and insert are refused
on a keyed list, add on another, and a key field is never assigned.
Texts compare with == != < <= > >= by their bytes.

Checked against a Python model over 3,600 random steps with a text-keyed
and a number-keyed list; 13 diagnostics; examples/tally.aup.

5 files changed, 323 insertions, 14 deletions

diff --git a/README.md b/README.md
index f3358be..f59569e 100644
--- a/README.md
+++ b/README.md
@@ -10,7 +10,7 @@ aup는 [Pure](/srv/git/pure.git) 런타임을 위한 **언어와 툴체인**이�
 | [Vega](/srv/git/vega.git) | aup와 Pure 위의 인터페이스 구현자(TUI·CLI·GUI·NUI) |
 
 상태: v0a(scalar 상태·키 입력·원자적 이벤트·보기), v0b(바이트·영속 문서·메시지·응답·text·커서),
-v0c(레코드·리스트·`index of`·조건식·표 보기·`fn`·`use` 라이브러리) 동작. 그 위의 첫 인터페이스는 [Vega](/srv/git/vega.git)(`use vega`, 목록·표·톤을 TUI·CLI·문장으로).
+v0c(레코드·리스트·`index of`·조건식·표 보기·`fn`·`use` 라이브러리·집계·키 있는 리스트·text 비교) 동작. 그 위의 첫 인터페이스는 [Vega](/srv/git/vega.git)(`use vega`, 목록·표·톤을 TUI·CLI·문장으로).
 [언어 v0](docs/design/001-language-v0.md).
 
 ```sh
diff --git a/docs/design/002-dsl-direction.md b/docs/design/002-dsl-direction.md
index 1432ef6..0e7e8ca 100644
--- a/docs/design/002-dsl-direction.md
+++ b/docs/design/002-dsl-direction.md
@@ -68,7 +68,7 @@ view current = note.line(at)           # 커서가 있는 줄. 복사하지 않�
 |---|---|---|
 | v0a ✅ | 스칼라 상태, 키 입력, 핸들러, 보기 | 워크벤치 엔진과 비트 단위 일치 |
 | v0b ✅ | `bytes`, 키별 영속 문서, `message` 입력, 응답, `require`, `text`(리터럴·보간·`cursor in`·`char`/`line`), `text` 입력 | 기존 편집기 CLI와 바이트 단위 일치, text 편집이 참조 모델과 일치 |
-| v0c | `record`, `list of`, `index of`, 조건식, 항목 투영(`each`), 순수 `fn`, `use` 라이브러리 ✅ / `i64 bool`, `map` | 모든 연산에 실행량 상한, 리스트가 참조 모델과 일치 ✅ |
+| v0c | `record`, `list of`, `index of`, 조건식, 항목 투영(`each`), 순수 `fn`, `use` 라이브러리, 집계, 키 있는 리스트(`map`의 자리), text 비교 ✅ / `i64 bool` | 모든 연산에 실행량 상한, 리스트가 참조 모델과 일치 ✅ |
 | v0d ✅ | `use vega`로 첫 인터페이스 투영(목록·표·커서·톤), [Vega 001](/srv/git/vega.git) | 한 명세가 세 표면(TUI·CLI·NUI 문장)에서 동작, 표면은 보이는 칸만 계산 |
 
 ### 구현된 text (v0b)
@@ -119,7 +119,8 @@ view status = "{at.position + 1}/{tasks.count}"
 - **변경은 되돌릴 수 있다.** 리스트 변경은 이벤트마다 기록되고, 이벤트가 실패하면 모두 되돌린다.
 - **레코드를 바꿔도 데이터가 남는다.** 모듈을 교체할 때 리스트는 이름으로 남고, 레코드가 바뀌었으면 항목마다
   이름과 타입이 같은 필드를 옮기고 새 필드는 기본값을 쓴다. 마이그레이션 스크립트가 필요 없다.
-- 레코드 값(`Task { ... }`)은 아직 `append`/`insert`의 인자로만 쓴다. 레코드 상태, 항목 전체 읽기, 정렬·검색은 없다.
+- 레코드 값(`Task { ... }`)은 아직 `append`/`insert`/`add`의 인자로만 쓴다. 레코드 상태와 항목 전체 읽기는 없다.
+  찾기는 `first(...)`(조건)와 키 있는 리스트의 `xs[키]`(키)로 한다.
 
 한도: 레코드 8개, 레코드당 필드 16개, 전체 필드 64개, 리스트당 항목 65,536개.
 
@@ -180,6 +181,42 @@ view summary = "{count(t in tasks where !t.done)} open of {tasks.count}"
 검증: 무작위 추가·토글·이동·삭제 3,600단계에서 네 집계(조건 있는 것 포함, 빈 max·min, 보간 안의 집계)가 파이썬
 참조 모델과 같다. 진단 7건(중첩, 리스트 아님, text 합, 열의 행, 바깥 매개변수, `dt`, `in` 누락)을 더했다.
 
+### 키 있는 리스트와 text 비교
+
+```text
+record Tally {
+  word: text
+  times = 0
+}
+state tallies: list of Tally by word      # 단어 순서, 단어마다 하나
+
+on typed {
+  if !tallies.has(typed) {
+    tallies.add(Tally { word: typed })    # 키 자리에 넣는다. 이미 있으면 이벤트가 exists로 실패
+  }
+  tallies[typed].times = tallies[typed].times + 1
+  at = tallies[typed]                     # 키로 찾은 인덱스
+}
+on forget.down { tallies.remove(at) }     # 인덱스로도, tallies.remove("pear")처럼 키로도 지운다
+view later = count(t in tallies where t.word > "m")
+```
+
+- **맵을 따로 두지 않는다.** `list of 레코드 by 필드`는 항목을 그 필드의 순서(수는 값, text는 바이트)로 두고 키마다 하나만
+  둔다. 맵, 집합, 정렬된 맵이 한 리스트에 순서 규칙 하나를 더한 것이 된다. 그래서 `each`·걸러진 표·집계·인덱스·저장·
+  교체·Vega 목록이 모두 그대로 쓰이고, 목록은 늘 정렬돼 보인다.
+- **키로 찾는다.** `xs[키]`는 반씩 나눠 찾은 항목이다(`xs[키].필드`로 읽고 쓰며, `xs[키]`만 쓰면 그 인덱스). 없으면
+  `not_found`로 실패하므로 있을지 모를 때는 `xs.has(키)`를 먼저 묻는다. `xs[인덱스]`도 그대로 쓴다.
+- **넣기는 `add`다.** 자리를 고르지 않으므로 `append`와 `insert`는 키 있는 리스트에 쓸 수 없고(컴파일 오류가 `add`를
+  알려 준다), `add`는 키 없는 리스트에 쓸 수 없다. 같은 키가 있으면 이벤트가 `exists`로 실패한다(아무것도 바뀌지 않음).
+- **키는 바뀌지 않는다.** 키 필드에 쓰면 컴파일 오류다(지우고 다시 넣는다). 그래서 순서는 넣기로만 만들어진다.
+- **리스트가 키를 얻으면.** 모듈을 바꾸거나 다시 시작할 때 키 없던 리스트가 키를 얻으면 Pure가 키 순서로 다시 놓고
+  인덱스는 자기 항목을 따라간다. 같은 키가 둘이면 모듈을 받지 않는다. 데이터를 버려 맞추지 않는다.
+- **text 비교.** `==`, `!=`, `<`, `<=`, `>`, `>=`가 text끼리도 된다. 바이트 순서다(UTF-8에서는 코드 포인트 순서와 같다).
+  정규화하지 않는다(`é`의 두 표기는 다르다). 로케일 정렬은 앞으로의 모듈 몫이다.
+
+검증: 무작위 3,600단계(실패 이벤트 약 670건 포함)에서 text 키 리스트(빈 text, 한글, 이모지, 앞이 같은 키)와 수 키
+리스트의 항목·인덱스·보기·실패 종류가 파이썬 모델과 같다. 진단 13건을 더했다. `examples/tally.aup`가 예제다.
+
 ### 구현된 fn과 use (v0c-3)
 
 ```text
diff --git a/examples/tally.aup b/examples/tally.aup
new file mode 100644
index 0000000..cdff8dd
--- /dev/null
+++ b/examples/tally.aup
@@ -0,0 +1,32 @@
+# Typed words, tallied. A list keyed by the word keeps each word once, in
+# order; tallies[word] finds it by halving, whatever the list's length.
+record Tally {
+  word: text
+  times = 0
+}
+state tallies: list of Tally by word
+state at: index of tallies
+input typed = text
+input forget = key Delete
+input up = key ArrowUp
+input down = key ArrowDown
+
+on typed {
+  if !tallies.has(typed) {
+    tallies.add(Tally { word: typed })
+  }
+  tallies[typed].times = tallies[typed].times + 1
+  at = tallies[typed]
+}
+on forget.down { tallies.remove(at) }
+on up.down { at = at - 1 }
+on down.down { at = at + 1 }
+
+view current = if tallies.count > 0 { "{at.word}: {at.times}" } else { "-" }
+view words = tallies.count
+view typed_total = sum(t.times for t in tallies)
+view most = max(t.times for t in tallies)
+view table = each t in tallies {
+  word = t.word
+  times = t.times
+}
diff --git a/src/compile.c b/src/compile.c
index 8a28384..9e90d26 100644
--- a/src/compile.c
+++ b/src/compile.c
@@ -17,7 +17,7 @@ enum { CONST, LOAD, DT, ADD, SUB, MUL, DIV, NEG, LT, LE, GT, GE, EQ, NE, AND, OR
        CUR_LOAD, CUR_START, CUR_END, CUR_MOVE, CUR_STORE, TEXT_INSERT, TEXT_REMOVE, TEXT_LINE,
        TEXT_SET, TEXT_FROM, BYTES_FROM, CUR_COUNT, LIST_COUNT, LIST_APPEND, LIST_INSERT, LIST_REMOVE,
        ITEM_GET, ITEM_SET, INDEX_LOAD, INDEX_STORE, INDEX_MOVE, INDEX_FIRST, INDEX_LAST, INDEX_NUM, ROW,
-       PICK, SLIDE, FOLD };
+       PICK, SLIDE, FOLD, TEXT_COMPARE, LIST_FIND, LIST_HAS };
 enum { FOLD_COUNT, FOLD_SUM, FOLD_MAX, FOLD_MIN, FOLD_FIRST };
 enum { KIND_KEY = 1, KIND_MESSAGE = 2, KIND_TEXT = 3, FIELD_U32 = 1, FIELD_BYTES = 2 };
 enum { STATE_NUM = 0, STATE_TEXT = 1, STATE_CURSOR = 2, STATE_LIST = 3, STATE_INDEX = 4, UNIT_CHAR = 0, UNIT_LINE = 1 };
@@ -60,7 +60,7 @@ typedef struct Expr {
     size_t size;
 } Expr;
 
-typedef enum { S_ASSIGN, S_IF, S_REPLACE, S_REPLY, S_REQUIRE, S_INSERT, S_REMOVE, S_APPEND, S_SET } StmtKind;
+typedef enum { S_ASSIGN, S_IF, S_REPLACE, S_REPLY, S_REQUIRE, S_INSERT, S_REMOVE, S_APPEND, S_ADD, S_SET } StmtKind;
 typedef struct Stmt {
     StmtKind kind;
     int line, column;
@@ -122,6 +122,9 @@ typedef struct {
     char state_names[STATES][NAME], state_target[STATES][NAME];
     int state_types[STATES], state_line[STATES], state_column[STATES];
     bool state_stays[STATES]; /* a mark: a cursor that stays before text inserted at it */
+    /* A keyed list: the field named after by, and once resolved, that field + 1. */
+    char state_key[STATES][NAME];
+    int state_key_line[STATES], state_key_column[STATES], list_key[STATES];
     double initial[STATES];
     Expr *state_text[STATES];
     unsigned states;
@@ -872,12 +875,12 @@ static Stmt *statement(Compiler *c, unsigned depth) {
                 s->last = expression(c, 0, true);
                 newlines(c);
             }
-        } else if (!strcmp(method.text, "append")) {
-            s->kind = S_APPEND;
+        } else if (!strcmp(method.text, "append") || !strcmp(method.text, "add")) {
+            s->kind = method.text[1] == 'p' ? S_APPEND : S_ADD;
             s->value = inserted(c);
             newlines(c);
         } else fail_at(c, method.line, method.column,
-                       "a text supports insert and remove; a list supports append, insert and remove");
+                       "a text supports insert and remove; a list supports append, insert and remove (add when keyed)");
         expect(c, ")", "')'");
         return s;
     }
@@ -1088,6 +1091,13 @@ static void state_declaration(Compiler *c) {
             expect_word(c, "of");
             Token target = expect_name(c, type.text[0] == 'l' ? "a record" : "a list state");
             memcpy(c->state_target[index], target.text, NAME);
+            if (type.text[0] == 'l' && word(c, "by")) { /* keyed: items in key order, each key once */
+                take(c);
+                Token key = expect_name(c, "a field of the record");
+                memcpy(c->state_key[index], key.text, NAME);
+                c->state_key_line[index] = key.line;
+                c->state_key_column[index] = key.column;
+            }
         } else fail_at(c, type.line, type.column,
                        "state types are numbers, text, cursor or mark in a text, list of a record, index of a list, "
                        "and bytes by key");
@@ -1409,6 +1419,31 @@ static void index_of(Compiler *c, const Expr *e, bool handler, int height, int l
                 c->state_names[list]);
 }
 
+/* The item name[e] names: e is an index of the list, or for a keyed list a
+ * key, found by LIST_FIND. */
+static void item_of(Compiler *c, const Expr *e, bool handler, int height, int list) {
+    Kind kind = value(c, e, handler, height);
+    int key = c->list_key[list] - 1;
+    if (kind.type != INDEX && key >= 0) {
+        const Record *r = record_of(c, list);
+        Type type = r->field_text[key] ? TEXT : NUM;
+        if (kind.type != type)
+            fail_at(c, e->line, e->column, "'%s' is keyed by %s, %s: expected %s or an index, not %s", c->state_names[list],
+                    r->field_names[key], type_name(type), type_name(type), type_name(kind.type));
+        emit(c, e->line, e->column, LIST_FIND, (uint32_t)list, 0);
+        return;
+    }
+    expect_kind(c, e, kind, INDEX);
+    if (kind.owner != list)
+        fail_at(c, e->line, e->column, "an index of '%s' cannot point into '%s'", c->state_names[kind.owner],
+                c->state_names[list]);
+}
+
+/* The key field of a keyed list, or NULL. */
+static const char *keyed_by(const Compiler *c, int list) {
+    return c->list_key[list] ? c->state_key[list] : NULL;
+}
+
 /* A fn inlined: its arguments go on the stack once, the body reads them with
  * PICK, and SLIDE leaves only the result. e names the call (E_FN), or is the
  * name of a fn without parameters. */
@@ -1580,6 +1615,22 @@ static Kind value(Compiler *c, const Expr *e, bool handler, int height) {
         if (!*e->member) return inline_fn(c, e, c->module, e->name, handler, height);
         int library = parameter(c, e->member) < 0 ? used_library(c, c->module, e->member) : -1;
         if (library >= 0) return inline_fn(c, e, library, e->name, handler, height);
+        int list = state_index(c, e->member);
+        if (!strcmp(e->name, "has") && list >= 0 && c->state_types[list] == STATE_LIST) {
+            /* people.has("bob"): whether a keyed list holds that key. */
+            app_name(c, e, e->member);
+            const char *key = keyed_by(c, list);
+            if (!key) fail_at(c, e->line, e->column, "'%s' has no key; declare it as list of %s by a field to ask has",
+                              e->member, record_of(c, list)->name);
+            if (e->count != 1) fail_at(c, e->line, e->column, "%s.has takes one key", e->member);
+            Type type = record_of(c, list)->field_text[c->list_key[list] - 1] ? TEXT : NUM;
+            Kind given = value(c, e->args[0], handler, height);
+            if (given.type != type)
+                fail_at(c, e->args[0]->line, e->args[0]->column, "'%s' is keyed by %s, %s: expected %s, not %s", e->member, key,
+                        type_name(type), type_name(type), type_name(given.type));
+            emit(c, e->line, e->column, LIST_HAS, (uint32_t)list, 0);
+            return (Kind){NUM, -1};
+        }
         if (strcmp(e->name, "line")) fail_at(c, e->line, e->column, "unknown library '%s'; write use %s first", e->member, e->member);
         /* note.line(at): the line a cursor is on. */
         app_name(c, e, e->member);
@@ -1610,9 +1661,18 @@ static Kind value(Compiler *c, const Expr *e, bool handler, int height) {
         app_name(c, e, e->name);
         int list = list_state(c, e->name, e->line, e->column, e->args[0]);
         const Record *r = record_of(c, list);
-        if (!*e->member) fail_at(c, e->line, e->column, "read a field of the item, as in %s[index].%s", e->name, r->field_names[0]);
+        if (!*e->member) {
+            /* people["bob"]: the index of the item with that key. */
+            if (!keyed_by(c, list))
+                fail_at(c, e->line, e->column, "read a field of the item, as in %s[index].%s", e->name, r->field_names[0]);
+            item_of(c, e->args[0], handler, height, list);
+            if (c->code[c->code_count - 1].op != LIST_FIND)
+                fail_at(c, e->line, e->column, "%s[index] is the index itself; read a field, as in %s[index].%s", e->name,
+                        e->name, r->field_names[0]);
+            return (Kind){INDEX, list};
+        }
         unsigned field = record_field(c, r, e->member, e->line, e->column);
-        index_of(c, e->args[0], handler, height, list);
+        item_of(c, e->args[0], handler, height, list);
         emit(c, e->line, e->column, ITEM_GET, (uint32_t)list | field << 16, 0);
         return (Kind){r->field_text[field] ? TEXT : NUM, -1};
     }
@@ -1699,6 +1759,19 @@ static Kind value(Compiler *c, const Expr *e, bool handler, int height) {
             else emit(c, e->line, e->column, INDEX_MOVE, 0, 0);
             return left;
         }
+        if (e->op >= LT && e->op <= NE) {
+            /* Texts compare by their bytes; numbers as numbers. */
+            Kind left = value(c, e->args[0], handler, height);
+            if (left.type == TEXT) {
+                expect_kind(c, e->args[1], value(c, e->args[1], handler, height + 1), TEXT);
+                emit(c, e->line, e->column, TEXT_COMPARE, (uint32_t)(e->op - LT), 0);
+                return (Kind){NUM, -1};
+            }
+            expect_kind(c, e->args[0], left, NUM);
+            number(c, e->args[1], handler, height + 1);
+            emit(c, e->line, e->column, (uint8_t)e->op, 0, 0);
+            return (Kind){NUM, -1};
+        }
         /* fall through */
     default:
         for (unsigned i = 0; i < e->count; ++i) number(c, e->args[i], handler, height + (int)i);
@@ -1768,7 +1841,11 @@ static void statements(Compiler *c, const Stmt *s) {
             int list = state_index(c, s->name);
             if (list >= 0 && c->state_types[list] == STATE_LIST) {
                 if (s->last) fail_at(c, s->last->line, s->last->column, "a list removes one item, as in %s.remove(index)", s->name);
-                index_of(c, s->first, true, 0, list);
+                if (s->kind == S_INSERT && keyed_by(c, list))
+                    fail_at(c, s->line, s->column, "'%s' is keyed by %s: %s.add(%s { ... }) places an item by its key", s->name,
+                            keyed_by(c, list), s->name, record_of(c, list)->name);
+                if (s->kind == S_REMOVE) item_of(c, s->first, true, 0, list);
+                else index_of(c, s->first, true, 0, list);
                 if (s->kind == S_INSERT) record_fields(c, s->value, list, 1);
                 emit(c, s->line, s->column, s->kind == S_INSERT ? LIST_INSERT : LIST_REMOVE, (uint32_t)list, 0);
                 break;
@@ -1785,8 +1862,16 @@ static void statements(Compiler *c, const Stmt *s) {
             emit(c, s->line, s->column, TEXT_REMOVE, (uint32_t)text, 0);
             break;
         }
-        case S_APPEND: {
+        case S_APPEND: case S_ADD: {
+            /* A keyed list places an added item by its key (it fails if the key is there); others append. */
             int list = list_state(c, s->name, s->line, s->column, NULL);
+            const char *key = keyed_by(c, list), *record = record_of(c, list)->name;
+            if (s->kind == S_APPEND && key)
+                fail_at(c, s->line, s->column, "'%s' is keyed by %s: %s.add(%s { ... }) places an item by its key", s->name,
+                        key, s->name, record);
+            if (s->kind == S_ADD && !key)
+                fail_at(c, s->line, s->column, "'%s' has no key: append or insert places its items (add needs list of %s by a field)",
+                        s->name, record);
             record_fields(c, s->value, list, 0);
             emit(c, s->line, s->column, LIST_APPEND, (uint32_t)list, 0);
             break;
@@ -1800,7 +1885,9 @@ static void statements(Compiler *c, const Stmt *s) {
             }
             const Record *r = record_of(c, list);
             unsigned field = record_field(c, r, s->member, s->line, s->column);
-            if (*s->name) index_of(c, s->first, true, 0, list);
+            if (c->list_key[list] == (int)field + 1)
+                fail_at(c, s->line, s->column, "the key of '%s' does not change; remove the item and add it again", c->state_names[list]);
+            if (*s->name) item_of(c, s->first, true, 0, list);
             expect_kind(c, s->value, value(c, s->value, true, 1), r->field_text[field] ? TEXT : NUM);
             emit(c, s->line, s->column, ITEM_SET, (uint32_t)list | field << 16, 0);
             break;
@@ -1890,6 +1977,9 @@ static void generate(Compiler *c, unsigned char **module, size_t *size) {
             if (record < 0)
                 fail_at(c, c->state_line[i], c->state_column[i], "a list holds a record; '%s' is not one", c->state_target[i]);
             state_ref[i] = (uint32_t)record;
+            if (*c->state_key[i])
+                c->list_key[i] = 1 + (int)record_field(c, &c->records[record], c->state_key[i], c->state_key_line[i],
+                                                       c->state_key_column[i]);
         }
     }
     for (unsigned i = 0; i < c->record_count; ++i) {
@@ -2001,7 +2091,10 @@ static void generate(Compiler *c, unsigned char **module, size_t *size) {
         p = put32(p, state_name[i]);
         p = put32(p, (uint32_t)c->state_types[i]);
         if (c->state_types[i] == STATE_NUM) p = put_double(p, c->initial[i]);
-        else { p = put32(p, state_ref[i]); p = put32(p, c->state_stays[i] ? 1 : 0); } /* 1: the cursor stays */
+        else { /* flags: a mark (1: the cursor stays), or a keyed list's key field + 1 */
+            p = put32(p, state_ref[i]);
+            p = put32(p, c->state_types[i] == STATE_LIST ? (uint32_t)c->list_key[i] : c->state_stays[i] ? 1 : 0);
+        }
     }
     for (unsigned i = 0; i < c->collections; ++i) { p = put32(p, collection_name[i]); p = put32(p, 1); p = put32(p, 1); }
     unsigned first = 0;
diff --git a/tests/check.py b/tests/check.py
index 4cd63c5..39c102a 100644
--- a/tests/check.py
+++ b/tests/check.py
@@ -52,6 +52,8 @@ ROOT = HERE.parent
 RECORD = 'record T {\n  a = 0\n}\n'
 ON_K = 'input k = key KeyK\non k.down {\n'
 LIST = RECORD + 'state xs: list of T\nstate at: index of xs\n'
+KEYED = 'record T {\n  a = 0\n  s: text\n}\n'
+KEYED_LIST = KEYED + 'state xs: list of T by s\nstate at: index of xs\n'
 
 DIAGNOSTICS = [
     ('state x = 1\nstate x = 2\n', '2:7', "already declared as a state"),
@@ -185,6 +187,21 @@ DIAGNOSTICS = [
     (LIST + 'view v = first(x in xs)\n', '6:10', 'a view is a number or text, not an index'),
     (LIST + 'view w = each r in xs where count(y in xs) > 0 {\n  n = r.a\n}\n', '6:29',
      "a table's where cannot hold a count, sum, max or min"),
+    # Keyed lists: a key field of the record, placed by add, found by key, never changed.
+    (KEYED + 'state xs: list of T by missing\n', '5:24', "record 'T' has no field 'missing'"),
+    (KEYED_LIST + ON_K + '  xs.append(T { s: "a" })\n}\n', '9:3', "'xs' is keyed by s: xs.add(T { ... }) places an item by its key"),
+    (KEYED_LIST + ON_K + '  xs.insert(at, T { s: "a" })\n}\n', '9:3', "'xs' is keyed by s: xs.add(T { ... })"),
+    (LIST + ON_K + '  xs.add(T { a: 1 })\n}\n', '8:3', "'xs' has no key: append or insert places its items (add needs list of T by a field)"),
+    (KEYED_LIST + ON_K + '  at.s = "b"\n}\n', '9:3', "the key of 'xs' does not change; remove the item and add it again"),
+    (KEYED_LIST + ON_K + '  xs["a"].s = "b"\n}\n', '9:3', "the key of 'xs' does not change"),
+    (LIST + 'view v = xs.has(1)\n', '6:13', "'xs' has no key; declare it as list of T by a field to ask has"),
+    (KEYED_LIST + 'view v = xs[1].a\n', '7:13', "'xs' is keyed by s, text: expected text or an index, not a number"),
+    (KEYED_LIST + 'view v = xs.has(1)\n', '7:17', "'xs' is keyed by s, text: expected text, not a number"),
+    (KEYED_LIST + 'view v = xs.has("a", "b")\n', '7:13', 'xs.has takes one key'),
+    (KEYED_LIST + ON_K + '  at = xs[at]\n}\n', '9:8', 'xs[index] is the index itself; read a field, as in xs[index].a'),
+    # Texts compare with texts, by their bytes.
+    ('view v = "a" < 1\n', '1:16', 'expected text, not a number'),
+    ('view v = 1 < "a"\n', '1:14', 'expected a number, not text'),
 ]
 
 ACCEPTED = [
@@ -230,6 +247,9 @@ ACCEPTED = [
     'fn later(cursor, n) = cursor + n char\ninput k = key KeyK\n'
     'on k.down {\n  xs.append(T { a: clip(xs.count), s: "q" })\n  c = later(c, 2)\n}\n'
     'view board = each r in xs {\n  tag = tag(r)\n}\nview cur = if xs.count > 0 { tag(at) } else { "-" }\n',
+    # A keyed list: added, found, changed, asked and removed by key; texts ordered by bytes.
+    KEYED_LIST + ON_K + '  xs.add(T { s: "q" })\n  at = xs["q"]\n  xs["q"].a = xs["q"].a + 1\n  xs.remove("q")\n}\n'
+    'view v = if xs.has("q") { 1 } else { 0 }\nview w = "a" < "b" && "b" >= "b" && "a" != "ab"\n',
 ]
 
 
@@ -1009,6 +1029,132 @@ view open_list = each t in tasks where !t.done {
 """
 
 
+KEYED_SOURCE = """record Person {
+  name: text
+  visits = 0
+}
+record Score {
+  value = 0
+  label: text
+}
+state people: list of Person by name
+state at: index of people
+state known = 0
+state n = 0
+state scores: list of Score by value
+input join = text
+input visit = text
+input ask = text
+input drop = key Delete
+input up = key ArrowUp
+input more = key KeyN
+input less = key KeyP
+input keep = key KeyM
+input forget = key KeyR
+on join {
+  people.add(Person { name: join })
+  at = people[join]
+}
+on visit {
+  if !people.has(visit) { people.add(Person { name: visit }) }
+  people[visit].visits = people[visit].visits + 1
+  at = people[visit]
+}
+on ask { known = people.has(ask) }
+on drop.down { people.remove(at) }
+on up.down { at = at - 1 }
+on more.down { n = n + 3 }
+on less.down { n = n - 5 }
+on keep.down { scores.add(Score { value: n, label: "{n}" }) }
+on forget.down { scores.remove(n) }
+view current = at.name
+view position = at.position
+view total = sum(p.visits for p in people)
+view after_m = count(p in people where p.name > "m")
+view lowest = if people.count > 0 { people.first.name } else { "-" }
+view labels = each s in scores {
+  label = s.label
+}
+view board = each p in people where p.visits > 0 {
+  label = "{p.name} ({p.visits})"
+}
+"""
+
+
+def keyed(aup, pure_run, work, seeds, steps=300):
+    """A list keyed by a text and one keyed by a number, against a Python
+    model: items in key order (texts by their bytes), each key once (a second
+    add fails with exists and changes nothing), found by key, asked with has,
+    removed by key; indices follow their items; texts compare by bytes."""
+    source = work / 'keyed.aup'
+    source.write_text(KEYED_SOURCE)
+    compile_module(aup, source, work / 'keyed.pmod')
+    words = ['m', 'b', 'zed', 'a', 'ab', '', '가', 'Z', 'm2', '😀', 'b\n']
+    compared = failures = 0
+    for seed in seeds:
+        rng, people, at, known, n, scores = random.Random(seed + 7700), [], 0, 0, 0, []
+        commands, expected, faults = [], [], []
+        key = lambda name: name.encode()
+
+        def place(name):
+            """Insert a person in key order; the index follows its item."""
+            nonlocal at
+            position = sum(1 for p in people if key(p['name']) < key(name))
+            people.insert(position, {'name': name, 'visits': 0})
+            if len(people) > 1 and at >= position: at += 1
+            return position
+
+        for _ in range(steps):
+            roll, fault = rng.random(), 'none'
+            names = [p['name'] for p in people]
+            if roll < 0.45:
+                name, word = rng.choice(['join', 'visit', 'ask']), rng.choice(words)
+                commands.append(f'type {name} ' + (word.encode().hex() or '-'))
+                if name == 'join':
+                    if word in names: fault = 'exists'
+                    else: at = place(word)
+                elif name == 'visit':
+                    if word not in names: place(word)
+                    at = [p['name'] for p in people].index(word)
+                    people[at]['visits'] += 1
+                else: known = int(word in names)
+            else:
+                name = rng.choice(['drop', 'up', 'more', 'less', 'keep', 'forget'])
+                commands.append(f'down {name}')
+                if name == 'drop':
+                    if not people: fault = 'not_found'
+                    else:
+                        del people[at]
+                        at = min(at, max(len(people) - 1, 0))
+                elif name == 'up': at = max(at - 1, 0)
+                elif name == 'more': n += 3
+                elif name == 'less': n -= 5
+                elif name == 'keep':
+                    if any(s['value'] == n for s in scores): fault = 'exists'
+                    else: scores.append({'value': n, 'label': str(n)}); scores.sort(key=lambda s: s['value'])
+                elif not any(s['value'] == n for s in scores): fault = 'not_found'
+                else: scores = [s for s in scores if s['value'] != n]
+            faults.append(fault)
+            expected.append(({'people': [dict(p) for p in people], 'at': at, 'known': known, 'n': n,
+                              'scores': [dict(s) for s in scores]},
+                             {'current': people[at]['name'] if people else None, 'position': at,
+                              'total': sum(p['visits'] for p in people),
+                              'after_m': sum(1 for p in people if key(p['name']) > b'm'),
+                              'lowest': people[0]['name'] if people else '-',
+                              'labels': [{'label': s['label']} for s in scores],
+                              'board': [{'label': f"{p['name']} ({p['visits']})"} for p in people if p['visits'] > 0]}))
+        lines = run(pure_run, work / 'keyed.pmod', stdin='\n'.join(commands) + '\n', check=False).stdout.splitlines()
+        shown = [json.loads(line) for line in lines]
+        assert [(s['states'], s['views']) for s in shown] == expected, \
+            (seed, next(i for i, (s, e) in enumerate(zip(shown, expected)) if (s['states'], s['views']) != e))
+        # A failed event leaves the last fault; a later success does not clear it, so compare where it is set.
+        got = [s['fault'] if s['error'] else 'none' for s in shown]
+        assert got == faults, (seed, [(i, a, b) for i, (a, b) in enumerate(zip(got, faults)) if a != b][:3])
+        compared += len(shown)
+        failures += sum(1 for f in faults if f != 'none')
+    return compared, failures
+
+
 def folds(aup, pure_run, work, seeds, steps=300):
     """count, sum, max and min over a list, and a table filtered by a where,
     against a Python model after random adds, toggles, moves and removals (an
@@ -1265,6 +1411,7 @@ def main():
         report['conditional_snapshots'] = conditionals(aup, pure_run, work)
         report['watched_builds'] = watching(aup, pure_run, work)
         report['fold_snapshots'] = folds(aup, pure_run, work, range(args.seeds if hasattr(args, 'seeds') else 8))
+        report['keyed_snapshots'], report['keyed_failed_events'] = keyed(aup, pure_run, work, range(args.seeds))
         report['stored_snapshots'], report['stored_restarts'] = stored_runs(aup, pure_run, work, range(args.text_seeds))
         report['library_programs'], report['library_diagnostics'] = libraries(aup, pure_run, work)
         report['editor_parity_operations'], report['editor_parity_outcomes'] = \