A generic type works with a type parameter rather than one fixed element type. That lets an immutable graph use different node types, but it also permits a stranger design: a deque whose middle contains a different type of element from its outer layer. The type system can express the structure of the data, not just the type of its contents. section 8.3 section 3.6
A deque whose types grow inward
For a Deque<char>, the middle is typed IDeque<Deque<char>.IMini>. Its middle has a more deeply nested element type, and the pattern continues. This is unbounded recursion in the type definition, not an infinitely deep deque: a deque of n items has O(log3 n) levels. C++ template expansion can make such growing types troublesome, whereas C# and Java generics reuse generated code to handle many constructed types. section 3.6 section 3.10
Generics also separate an abstraction from its storage. An immutable ImGraph<N> can wrap a multidictionary of N-to-N relationships while exposing graph operations instead of dictionary operations. Its methods maintain the undirected-edge invariant: adding or removing an edge changes both directions. The wrapper can change its storage strategy without forcing callers to adopt a new graph API. section 8.3
Listing 8.2 An immutable undirected graph wrapping a multidictionary
readonly struct ImGraph<N> where N : notnull
{
public static ImGraph<N> Empty = new(ImMulti<N, N>.Empty);
private readonly ImMulti<N, N> nodes;
private ImGraph(ImMulti<N, N> ns) => this.nodes = ns;
public bool IsEmpty => nodes.IsEmpty;
public bool HasNode(N n) => nodes.ContainsKey(n);
public bool HasEdge(N n1, N n2) => nodes.HasValue(n1, n2);
public IEnumerable<N> Nodes => nodes.Keys;
public ImmutableHashSet<N> Edges(N n) => nodes[n];
public ImGraph<N> AddNode(N n) =>
HasNode(n) ?
this :
new(nodes.SetItem(n, ImmutableHashSet<N>.Empty));
public ImGraph<N> AddEdge(N n1, N n2) =>
new(nodes.Add(n1, n2).Add(n2, n1));
public ImGraph<N> RemoveEdge(N n1, N n2) =>
new(nodes.Remove(n1, n2).Remove(n2, n1));
public ImGraph<N> RemoveNode(N n)
{
var result = this;
foreach (var n2 in Edges(n))
result = result.RemoveEdge(n, n2);
return new(result.nodes.Remove(n));
}
public ImGraph<N> AddEdges(N n1, IEnumerable<N> ns)
{
var result = this;
foreach (var n2 in ns)
result = result.AddEdge(n1, n2);
return result;
}
public ImGraph<N> AddClique(IList<N> ns)
{
var result = this;
for(int i = 0; i < ns.Count; i += 1)
for(int j = i + 1 ; j < ns.Count; j += 1)
result = result.AddEdge(ns[i], ns[j]);
return result;
}
}
Inspect the graph wrapper’s type parameter, private multidictionary, and paired edge updates. These choices make the node type flexible while keeping graph rules inside the abstraction. section 8.3
A different use of generics is to add a capability to any underlying T. Nullable<T> adds nullability; Lazy<T> adds deferred computation with caching; Task<T> adds asynchronous computation; IEnumerable<T> produces values on demand. Viewed as monads, such wrappers support workflows that preserve the behavior of functions operating on T while adding the wrapper’s capability. The pattern also has monad laws, though those laws are not developed here. section 11.1 section 11.5
The operations behind that workflow are:
- Unit wraps a T as an M<T>. section 11.1
- Bind applies a function returning M<R> to an M<T>, producing M<R>; Map handles a function returning an ordinary R. section 11.3
- Join removes one level of nesting from M<M<T>> and can be derived from Bind. section 11.3
static Nullable<T> NullableUnit<T> where T : struct (T t) =>
new Nullable<T>(t);
static Lazy<T> LazyUnit<T>(T t) => new Lazy<T>(t);
static Task<T> TaskUnit<T>(T t) => Task.FromResult(t);
static IEnumerable<T> SeqUnit<T>(T t) => [ t ];
Compare the Unit factories for nullable values, lazy values, tasks, and sequences: each wraps one T, but each wrapper offers a different capability. section 11.1
When type arguments are omitted
In a C#-like example, List<B> Frob<A, B>(A a, Func<A, B> f) is called with 1.5 and x => [x]. Treating generic parameters and omitted types as holes turns inference into a unification problem; the resulting type is List<List<double>>. This particular inference does not work quite the same way in C#; it is closer to F# or OCaml inference. section 10.3
