Array type in Nim
Recently, I was looking at Nim, and for practice and to get a better taste of the language, I decided to solve a simple algorithmic problem that accepts a matrix as a parameter and transforms it in a certain way. I won't go into details here, it's a fairly trivial problem.
The important point is that the matrix should be square, meaning that the number of rows should be equal to the number of columns. In terms of programming languages where matrices are usually implemented with nested arrays, it means that the number of elements in every sub-array should be equal to the number of sub-arrays. We could validate it by iterating through the array and checking the length of every sub-array.
Sounds simple enough, but with Nim, it's possible to do it in a different (and possibly better) way.
Nim provides two data types that can be compared to arrays in other languages:
- Arrays: fixed length, so they cannot grow or shrink.
- Sequences: dynamic length collections, allocated on the heap, and garbage collected.
If we assume that we know the matrix dimensions at the compile time, we can safely use array
:
array[0..4, int]
0..4
denotes the size and indexation of the array (5 elements in this case, indexed from 0 to 4).
Interestingly enough, if we write:
array[5..9, int]
then the first element of the array will be at index [5]
, and not at [0]
, so this will result in "Out of bounds error":
type
MyArr = array[5..9, int]
let a: MyArr = [1, 2, 3, 4, 5]
echo a[0]
I'm not entirely sure what's the use case for this, but it's cool! I guess it could be used in cases when the index of the array has a certain meaning, and instead of making the index 0-based before accessing the items, we can use it as it is. For example, we could store names of all 12 months and start indexation from 1, not 0:
type
Months = array[1..12, string]
let m = Months(["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"])
let january = m[0]
this will result in "Out of bounds error", since our array starts from 1.
It looks like it's not a very common thing to do, so Nim gives us a shortcut for the regular indexation that starts from 0:
array[5, int] # same as: array[0..4, int]
int
denotes the type of the items of the array.
So if we want to nest arrays, we simply pass the nested array type as the second argument for the parent array type definition:
array[5, array[5, int]]
which reads as array of 5 arrays that contain 5 ints each
.
Now let's define our function. Remember, we accept a matrix, do something with it, and return a matrix with same dimensions. Our function will work with 3x3 matrices:
proc transform(matrix: array[3, array[3, int]]): array[3, array[3, int]] =
# implementation
It's not bad, it enforces the squareness of our matrix, and that we return a matrix with the same dimensions. Obviously, this function is extremely limited, and if we wanted to support other kinds of matrices, we would have to define a new function.
At this point, it's pretty clear that we need to use generics/templates if we want to generalize this function. Nim has both, and we need generics because templates mean something different (I think they're more similar to the macros system of C).
The great thing about an array type definition like the one in Nim is that not only the type of contents is a part of type signature, but the size is as well. This means that the size of the array can be parameterized with generics too!
proc transform[N, T](matrix: array[N, array[N, T]]): array[N, array[N, T]] =
# implementation
If we try to use it with a matrix with wrong dimensions, we get a type error during compilation:
let input = [
[1],
[2]
]
discard transform(input) # => Error: type mismatch
However, if we make our matrix square:
let input = [
[1, 2],
[3, 4]
]
discard transform(input)
we get no type errors!
This might be obvious for someone coming from C, but for me, who mostly used scripting languages like Ruby or TypeScript, this is pretty mind-blowing. I'll use the name "TypeScript" and not "JavaScript" since JS is not statically typed, and so its type system cannot be compared with Nim.
Now, I understand that an array in a language like TypeScript is a very different thing: it can be resized at any time as our program runs, so it makes sense that the "size" is not part of the type. Nim's dynamic arrays are called sequences, and their type signature also lacks the size parameter:
var
x: seq[int]
Still, I think it's pretty nice that Nim has a type like this. Even though in most of the real-world cases a sequence would be used, and that's what I did in my implementation of the algorithm in the end, it's good to have this option for cases when we can get strict type checking for our array sizes (and possibly even shapes), in exchange for the ability to resize them during runtime.
Up next: doing the same thing using TypeScript's type system.