Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 36 ยท Collections and Strings

Arrays and Sequences (seq)

Learn Nim's fixed-size arrays and growable seq: literals, indexing, slices, ^ indexes, add, insert, delete, sorting, map and filter, copying rules and bounds errors.

Lists of values are everywhere. Nim has two built-in list types: the array, whose length is fixed and known at compile time, and the sequence (seq), which can grow and shrink while the program runs. If you are coming from Python, seq is your everyday list; if you are coming from C, an array is the one you already know.

Nim code here is read-only (no Nim compiler on this site). A C stand-in demonstrates how a growable sequence works internally.

Arrays

NIM
var scores: array[5, int]                 # five zeros
let primes = [2, 3, 5, 7, 11]             # type array[5, int]
var grid: array[3, array[3, int]]         # 3x3 table

scores[0] = 90
scores[4] = 75
echo scores                               # [90, 0, 0, 0, 75]
echo primes.len                           # 5
echo primes.high                          # 4 (the last valid index)

The size is part of the type: array[5, int] and array[6, int] are different types. The elements live directly inside the variable (on the stack for a local), so arrays are very fast and need no allocation.

Arrays can have other index ranges, even enums:

NIM
var temps: array[1 .. 12, float]          # index 1..12 (months)
temps[1] = -2.5

type Size = enum small, medium, large
var stock: array[Size, int]               # one slot per enum value
stock[medium] = 30

Arrays are value types: assigning one array to another copies every element.

Sequences

NIM
var names = @["Ann", "Bo", "Cy"]          # @[...] builds a seq
var numbers: seq[int]                     # empty (not nil)
var zeros = newSeq[int](5)                # five zeros

Basic operations:

NIM
names.add "Di"                            # append
names.insert("Zed", 0)                    # insert at index 0
echo names.len                            # 5
echo names[0]                             # Zed
echo names.pop()                          # removes and returns "Di"
names.delete(1)                           # removes index 1, keeps order (O(n))
names.del(0)                              # removes index 0, swaps in the last (O(1), order changes)
echo "Bo" in names                        # membership test

Indexing starts at 0. Reading outside the range raises an IndexDefect in checked builds. The two removal procedures trade order for speed: use delete when order matters and del when it does not.

Slices and ^ indexes

NIM
let letters = @['a', 'b', 'c', 'd', 'e']
echo letters[1 .. 3]       # @['b', 'c', 'd']  (inclusive)
echo letters[1 ..< 3]      # @['b', 'c']
echo letters[^1]           # 'e'   (last element)
echo letters[^2]           # 'd'
echo letters[2 .. ^1]      # @['c', 'd', 'e']

^1 counts from the end: the last element, ^2 the second to last. A slice returns a new seq (a copy).

Copy semantics

Sequences are also value types: var b = a makes an independent copy, so changing b does not affect a. (Nim optimizes copies away when it can prove they are unnecessary, and a move happens when a is no longer used.)

NIM
var a = @[1, 2, 3]
var b = a
b.add 4
echo a, b          # @[1, 2, 3]@[1, 2, 3, 4]

The sequtils and algorithm modules

NIM
import std/[sequtils, algorithm, sugar, strutils]

let nums = @[5, 3, 8, 1]
echo nums.sorted()                     # @[1, 3, 5, 8]  (new seq)
echo nums.sorted(Descending)           # @[8, 5, 3, 1]
echo nums.map(x => x * 2)              # @[10, 6, 16, 2]
echo nums.filter(x => x > 2)           # @[5, 3, 8]
echo nums.foldl(a + b)                 # 17
echo nums.mapIt($it).join(", ")     
echo nums.reversed()                   # @[1, 8, 3, 5]
echo zip(nums, nums.map(x => x * x))   # @[(5, 25), (3, 9), (8, 64), (1, 1)]

var inPlace = nums
inPlace.sort()                         # sorts the variable itself

sorted returns a new sequence; sort changes the one you have. Many helpers come in pairs like this. Other handy procedures: count, find, deduplicate, concat, toSeq, anyIt, allIt, min, max, sum (from std/math).

flowchart LR
  A["array<br/>fixed size, on the stack"] -- "toSeq / @" --> S["seq<br/>growable, on the heap"]
  S -- "[0 ..< 5] / copy to array" --> A
  S --> O["add, insert, delete,<br/>pop, sort, map, filter"]

Caption: arrays are fixed and stack-friendly; sequences grow and live on the heap.

Choosing between them

Need Use
Size known at compile time, speed-critical array[N, T]
Size changes at run time seq[T]
Read-only parameter accepting either openArray[T]
Sorted lookups or key-value pairs Table (next lessons)

Stand-in: how a growable sequence works

A seq stores its elements in one block of heap memory with a length and a capacity. When add finds the block full, it allocates a bigger one and moves the elements. This C stand-in implements that with doubling (a common strategy; real implementations tune the details).

C Stand-in: a growable int sequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Appending is cheap on average because growth is rare: this is called amortized constant time.

Stand-in: delete versus del

C Stand-in: ordered delete versus swap-with-last

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The first result keeps the order 10 30 40 50; the second is faster but gives 10 50 30 40.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the difference between array[5, int] and seq[int]?

    The array's size is part of its type; a seq is a growable heap-backed list.
  2. 2. What does letters[^1] give?

    ^1 counts from the end, so it names the last element.
  3. 3. Which procedure removes an element and preserves the order of the rest?

    delete shifts later elements left; del swaps the last element in and is faster but reorders.
  4. 4. After var b = a for sequences, then b.add 4, what happens to a?

    Sequences have value semantics, so b is an independent copy.

Summary

  • array[N, T] has a fixed size in its type; seq[T] grows and is created with @[...] or newSeq.
  • Index from 0, count from the end with ^, slice with a .. b or a ..< b.
  • add, insert, pop, delete, del change a sequence; sorted, map, filter return new ones.
  • Both are value types: assignment copies.

Next: Tables and sets