Generics

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

The following example shows how a generic binary tree can be modeled:

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

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