Generics

Generics are Nim’s means to parametrize procs, iterators or types with type parameters. Depending on context, the brackets are used either to introduce type parameters or to instantiate a generic proc, iterator or type.

The following example shows a generic binary tree can be modelled:

  1. type
  2.   BinaryTree*[T] = ref object # BinaryTree is a generic type with
  3.                               # generic param ``T``
  4.     le, ri: BinaryTree[T]     # left and right subtrees; may be nil
  5.     data: T                   # the data stored in a node
  7. proc newNode*[T](data: T): BinaryTree[T] =
  8.   # constructor for a node
  9.   result = BinaryTree[T](le: nil, ri: nil, data: data)
  11. proc add*[T](root: var BinaryTree[T], n: BinaryTree[T]) =
  12.   # insert a node into the tree
  13.   if root == nil:
  14.     root = n
  15.   else:
  16.     var it = root
  17.     while it != nil:
  18.       # compare the data items; uses the generic ``cmp`` proc
  19.       # that works for any type that has a ``==`` and ``<`` operator
  20.       var c = cmp(it.data, n.data)
  21.       if c < 0:
  22.         if it.le == nil:
  23.           it.le = n
  24.           return
  25.         it = it.le
  26.       else:
  27.         if it.ri == nil:
  28.           it.ri = n
  29.           return
  30.         it = it.ri
  32. proc add*[T](root: var BinaryTree[T], data: T) =
  33.   # convenience proc:
  34.   add(root, newNode(data))
  36. iterator preorder*[T](root: BinaryTree[T]): T =
  37.   # Preorder traversal of a binary tree.
  38.   # Since recursive iterators are not yet implemented,
  39.   # this uses an explicit stack (which is more efficient anyway):
  40.   var stack: seq[BinaryTree[T]] = @[root]
  41.   while stack.len > 0:
  42.     var n = stack.pop()
  43.     while n != nil:
  44.       yield n.data
  45.       add(stack, n.ri)  # push right subtree onto the stack
  46.       n = n.le          # and follow the left pointer
  48. var
  49.   root: BinaryTree[string] # instantiate a BinaryTree with ``string``
  50. add(root, newNode("hello")) # instantiates ``newNode`` and ``add``
  51. add(root, "world")          # instantiates the second ``add`` proc
  52. for str in preorder(root):
  53.   stdout.writeLine(str)

The T is called a generic type parameter or a type variable.