I'm trying to make an implementation of a graph-like data structure in Nim. For that I need object types which are referencing each other (each node needs to have references to its edges, and each edge needs references to nodes it connects).
As stated in the manual, it can be easily done, because Nim supports mutually recursive types:
type
Node = ref object
someEdge: Edge
Edge = ref object
someNode: Node
var x = Node() # Works
echo repr(x)
However, when I try to introduce generics here, it won't compile anymore:
type
GenericNode[E] = ref object
someEdge: E
GenericEdge[N] = ref object
someNode: N
type
Node = GenericNode[Edge]
Edge = GenericEdge[Node]
var x = Node() # Error: invalid type: 'Edge' in this context: 'Node' for var
echo repr(x)
In case of a non-mutually recursive type I get another error:
type
GenA[T] = ref object
field: T
type
A = GenA[A]
var x = A() # Error: object constructor needs an object type
echo repr(x)
Am I doing something wrong here or generics are simply cannot be used in this scenario?
aren't you more likely to want something like:
type
GenericNode[N,E] = ref object
weight:N
someEdge:GenericEdge[N,E]
GenericEdge[N,E] = ref object
weight: E
someNode: GenericNode[N,E]
var x = GenericNode[int,string]()
echo x.repr
I want to be able to inherit from GenericNode and GenericEdge, so I can add arbitrary fields to them.
I could add a generic payload: T field instead (and put all extra fields there), but that means I would need to write node.payload.someExtraNodeField each time I want to access it (and also it would require extra memory).
Although I just realized that instantiating a generic type and inheriting from it at the same time is another thing that probably just isn't possible:
type
GenericNode[E] = ref object of RootObj
someEdge: E
GenericEdge[N] = ref object of RootObj
someNode: N
type
Node = ref object of GenericNode[Edge]:
someExtraNodeField: int
Edge = ref object of GenericEdge[Node]:
someExtraEdgeField: int
you don't need to mix generics and inheritance, one or the other should be sufficient
type
BaseNode = ref object of RootObj
someEdge: BaseEdge
BaseEdge = ref object of RootObj
someNode: BaseNode
type
myNode = ref object of BaseNode
extraNodeField: int
myEdge = ref object of BaseEdge
extraEdgeField: int
var v = myNode(extraNodeField: 7)
v.someEdge = myEdge(extraEdgeField: 9)
echo v.repr
I could add a generic payload: T field instead (and put all extra fields there), but that means I would need to write node.payload.someExtraNodeField each time I want to access it (and also it would require extra memory).
you can write templates and procs to reduce boilerplate, overloading the [] operator might be useful
containers don't take up more memory than their contents (modulo padding), inheritable objects have an extra pointer.
type
Container[T] = object
payload: T
Base = object of RootObj
Inherited = object of Base
payload: int
let x = Container[int]()
let y = Inherited()
echo sizeof(x) #8
echo sizeof(y) #16
While these sorts of type system questions may be important for your exact use case, they may also be unimportant. You should be sure of what you need before you get too tangled up in types.
For example, the following program does the union-find (I think "join root" expresses the ideas better...) graph algorithm for connected components using just undirected arc 2-tuples of (likely small) integers:
import tables
template iniTab[K,V](n: auto): auto = initTable[K,V](rightSize(n))
proc root(up: var seq[int], x: int): int {.inline.} =
result = x # Find root defined by parent == self
while up[result] != result:
result = up[result]
var x = x # Compress path afterwards
while up[x] != result: #..by doing up[all x in path] <- result
let up0 = up[x]; up[x] = result; x = up0
proc join(up, sz: var seq[int], x, y: int) {.inline.} =
let x = up.root(x) # Join/union by size
let y = up.root(y)
if x == y: return # x & y are already joined
if sz[x] < sz[y]: # Attach smaller tree..
up[x] = y #..to root of larger
sz[y] += sz[x] # and update size of larger
else: # Mirror case of above
up[y] = x
sz[x] += sz[y]
iterator components*(arcs: openArray[tuple[x, y: int]], nV: int): seq[int] =
## yields connected components given arcs and number of unique vertices
var up = newSeq[int](nV) # vtxId -> parent id
for i in 0 ..< nV: up[i] = i # initial parents all self
var sz = newSeq[int](nV) # vtxId -> sz
for i in 0 ..< nV: sz[i] = 1 # initial sizes all 1
for arc in arcs: # Incorp arcs via union-find/join-root
join up, sz, arc.x, arc.y # Post loop up.root(i)==component label
var cs = iniTab[int, seq[int]](nV) # component id -> all members
for i in 0 ..< nV: # for each unique vertex:
cs.mgetOrPut(up.root(i), @[]).add i # update root[id] => members map
for c in cs.values: yield c # Then yield blocks of components
proc vtxId*[T](vi: var Table[T, int]; vn: var seq[T]; vo: T): int {.inline.} =
## Return a vertex id for maybe-already-seen obj `vo`, updating `vi` & `vn`.
try : result = vi[vo] # Already known => done
except: result = vn.len; vi[vo] = result; vn.add vo # Put into nm->id & id->nm
when isMainModule:
import cligen
proc conncomp(idelim='\t', odelim="\t") =
## Print connected components of the graph of arcs/edges on stdin.
var vi = iniTab[string, int](4096) # vertex name -> int id number
var vn = newSeqOfCap[string](4096) # vertex int id -> name
var arcs = newSeqOfCap[tuple[x, y: int]](4096)
for ln in lines(stdin): # Parse input, assign vertex ids,
let cs = ln.split(idelim) #..and load up `arcs`.
arcs.add (vtxId(vi, vn, cs[0]), vtxId(vi, vn, cs[1]))
for c in components(arcs, vn.len): # Emit output
for i, e in c: stdout.write vn[e], if i < c.len - 1: odelim else: ""
stdout.write "\n"
dispatch(conncomp, help = { "idelim": "arc delimiter",
"odelim": "in-cluster delimiter" })
Anyway, that is just an example I happened to have lying around that seemed small enough to just Forum-post to maybe lubricate some creativity in the solution of your actual problem with simpler type requirements. E.g. as per your above mentioned concern, node[idx].someExtraField may be enough, depending upon what your ultimate/actual problem is.
The problem with inheritance is that my base algorithm (operating on BaseNode/BaseEdge) should be able to create instances of them without knowing about the exact descendants.
For now I decided just to pass "constructors" (procs which return instances of base objects) to that algorithm.
Another problem is that the base algorithm returns a Graph object, which in turn contains lists of BaseNode/BaseEdge. So if I want to access extra fields in those nodes and edges, I need to write something like myNode(graph.nodes[0]).extraNodeField = 123 (i.e. type conversion is required).
But you're right, using procs and templates to reduce that boilerplate seems more reasonable idea than generics.