  Parallel programs are frequently modeled as dependency or cost graphs, which
can be used to detect various bugs, or simply to visualize the parallel
structure of the code. However, such graphs reflect just one particular
execution and are typically constructed in a post-hoc manner. Graph types,
which were introduced recently to mitigate this problem, can be assigned
statically to a program by a type system and compactly represent the family of
all graphs that could result from the program. Unfortunately, prior work is
restricted in its treatment of futures, an increasingly common and especially
dynamic form of parallelism. In short, each instance of a future must be
statically paired with a vertex name. Previously, this led to the restriction
that futures could not be placed in collections or be used to construct data
structures. Doing so is not a niche exercise: such structures form the basis of
numerous algorithms that use forms of pipelining to achieve performance not
attainable without futures. All but the most limited of these examples are out
of reach of prior graph type systems. In this paper, we propose a graph type
system that allows for almost arbitrary combinations of futures and recursive
data types. We do so by indexing datatypes with a type-level vertex structure,
a codata structure that supplies unique vertex names to the futures in a data
structure. We prove the soundness of the system in a parallel core calculus
annotated with vertex structures and associated operations. Although the
calculus is annotated, this is merely for convenience in defining the type
system. We prove that it is possible to annotate arbitrary recursive types with
vertex structures, and show using a prototype inference engine that these
annotations can be inferred from OCaml-like source code for several complex
parallel algorithms.
