Arrays and Iteration

Array Sum (Linear Scan)

Walk an array once, accumulating each element into a running total. This is the canonical single-pass linear scan and the simplest possible loop invariant: after step i, total equals the sum of arr[0..i].

Algorithm

The canonical input from the lesson spec is arr=(3 1 4 1 5 9 2 6). After eight passes the running total is 31.

linear scan Visit each element exactly once in index order.
running total `total` accumulates the sum as the loop advances.

Basic Implementation

basic.sql
Replay: real traced execution (multi-file project)
.mode list
.headers off
CREATE TABLE arr(idx INTEGER PRIMARY KEY, val INTEGER);
INSERT INTO arr(idx, val) VALUES
  (0, 3), (1, 1), (2, 4), (3, 1), (4, 5), (5, 9), (6, 2), (7, 6);
WITH RECURSIVE walk(idx, total) AS (
  SELECT 0, 0
  UNION ALL
  SELECT walk.idx + 1, walk.total + arr.val
  FROM walk JOIN arr ON arr.idx = walk.idx
)
SELECT total FROM walk WHERE idx = (SELECT COUNT(*) FROM arr);

  1. arr ← (empty)

    1.mode list2.headers off
    values this step(empty)arr

  2. arr ← [3, 1, 4, 1, 5, 9, 2, 6]

    1.mode list2.headers off
    values this step(empty) → [3, 1, 4, 1, 5, 9, 2, 6]arr

  3. walk.idx ← 0, walk.total ← 0

    1.mode list2.headers off
    values this step0walk.idx0walk.total[3, 1, 4, 1, 5, 9, 2, 6]arr

  4. walk.idx ← 1, walk.total ← 3

    1.mode list2.headers off
    values this step0 → 1walk.idx0 → 3walk.total3arr.val

  5. walk.idx ← 2, walk.total ← 4

    1.mode list2.headers off
    values this step1 → 2walk.idx3 → 4walk.total1arr.val

  6. walk.idx ← 3, walk.total ← 8

    1.mode list2.headers off
    values this step2 → 3walk.idx4 → 8walk.total4arr.val

  7. walk.idx ← 4, walk.total ← 9

    1.mode list2.headers off
    values this step3 → 4walk.idx8 → 9walk.total1arr.val

  8. walk.idx ← 5, walk.total ← 14

    1.mode list2.headers off
    values this step4 → 5walk.idx9 → 14walk.total5arr.val

  9. walk.idx ← 6, walk.total ← 23

    1.mode list2.headers off
    values this step5 → 6walk.idx14 → 23walk.total9arr.val

  10. walk.idx ← 7, walk.total ← 25

    1.mode list2.headers off
    values this step6 → 7walk.idx23 → 25walk.total2arr.val

  11. walk.idx ← 8, walk.total ← 31

    1.mode list2.headers off
    values this step7 → 8walk.idx25 → 31walk.total6arr.val

  12. stdout ← 31

    1.mode list2.headers off
    values this step31stdout31walk.total

Trace Output

trace.sql
Replay: real traced execution (multi-file project)
.mode list
.headers off
CREATE TABLE arr(idx INTEGER PRIMARY KEY, val INTEGER);
INSERT INTO arr(idx, val) VALUES
  (0, 3), (1, 1), (2, 4), (3, 1), (4, 5), (5, 9), (6, 2), (7, 6);
WITH RECURSIVE walk(step, before_total, val, total) AS (
  SELECT 1, 0, arr.val, arr.val FROM arr WHERE arr.idx = 0
  UNION ALL
  SELECT walk.step + 1, walk.total, arr.val, walk.total + arr.val
  FROM walk JOIN arr ON arr.idx = walk.step
)
SELECT line FROM (
  SELECT step AS k,
         'step ' || (step - 1) || ': arr(' || (step - 1) || ')='
         || val || ' total ' || before_total || ' -> ' || total AS line
  FROM walk
  UNION ALL
  SELECT 999, 'final total = ' || total FROM walk
  WHERE step = (SELECT COUNT(*) FROM arr)
)
ORDER BY k;

  1. arr ← (empty)

    1.mode list2.headers off
    values this step(empty)arr

  2. arr ← [3, 1, 4, 1, 5, 9, 2, 6]

    1.mode list2.headers off
    values this step(empty) → [3, 1, 4, 1, 5, 9, 2, 6]arr

  3. walk.total ← 3, stdout ← step 0: arr(0)=3 total 0 -> 3

    1.mode list2.headers off
    values this step3walk.totalstep 0: arr(0)=3 total 0 -> 3stdout0step3arr.val0before_total

  4. walk.total ← 4, stdout ← step 1: arr(1)=1 total 3 -> 4

    1.mode list2.headers off
    values this step4walk.totalstep 1: arr(1)=1 total 3 -> 4stdout1step1arr.val3before_total

  5. walk.total ← 8, stdout ← step 2: arr(2)=4 total 4 -> 8

    1.mode list2.headers off
    values this step8walk.totalstep 2: arr(2)=4 total 4 -> 8stdout2step4arr.val4before_total

  6. walk.total ← 9, stdout ← step 3: arr(3)=1 total 8 -> 9

    1.mode list2.headers off
    values this step9walk.totalstep 3: arr(3)=1 total 8 -> 9stdout3step1arr.val8before_total

  7. walk.total ← 14, stdout ← step 4: arr(4)=5 total 9 -> 14

    1.mode list2.headers off
    values this step14walk.totalstep 4: arr(4)=5 total 9 -> 14stdout4step5arr.val9before_total

  8. walk.total ← 23, stdout ← step 5: arr(5)=9 total 14 -> 23

    1.mode list2.headers off
    values this step23walk.totalstep 5: arr(5)=9 total 14 -> 23stdout5step9arr.val14before_total

  9. walk.total ← 25, stdout ← step 6: arr(6)=2 total 23 -> 25

    1.mode list2.headers off
    values this step25walk.totalstep 6: arr(6)=2 total 23 -> 25stdout6step2arr.val23before_total

  10. walk.total ← 31, stdout ← step 7: arr(7)=6 total 25 -> 31

    1.mode list2.headers off
    values this step31walk.totalstep 7: arr(7)=6 total 25 -> 31stdout7step6arr.val25before_total

  11. stdout ← final total = 31

    1.mode list2.headers off
    values this stepfinal total = 31stdout31walk.total

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • SQL: the array is modeled as a two-column table arr(idx INTEGER PRIMARY KEY, val INTEGER) so the loop index is the table's primary key and a WITH RECURSIVE CTE can step through the rows one at a time. SELECT SUM(val) FROM arr would jump straight to 31 without the running update the lesson is teaching, so the recursive CTE visits indices 0..7 explicitly and carries (idx, total) forward.
  • The CTE seed SELECT 0, 0 produces the empty-prefix invariant; the recursive arm joins walk to arr on arr.idx = walk.idx to read the current element, increments the index, and adds the value.
  • The final SELECT total FROM walk WHERE idx = (SELECT COUNT(*) FROM arr) picks the row produced after the last addition. SQLite emits 31 under .mode list with no headers, so the output is stable across releases.
  • trace.sql reuses the same WITH RECURSIVE shape but carries (step, before_total, val, total) so each frame prints step i: arr(i)=V total B -> T. The final line prints the canonical final total = 31 summary.