Nil
The end marker of the product, string, and path lists: an empty, constructible list.
Overview
In Context-Generic Programming (CGP), Nil marks the end of a right-nested type-level
list. Where a Cons cell pairs a head with
the rest of the list, Nil is the rest when nothing is left, so a list of any length is a Cons chain
that finishes in Nil. On its own, Nil is the empty list.
The same marker terminates every CGP list except the sum list. It ends the product list built from
Cons, the string list built from Chars, and the path list built from
PathCons. Only the sum list ends differently, in the uninhabited Void. That
difference is the point of both markers. A record, a string, and a path can each be empty and still exist,
so their terminator is a real value.
Definition
Nil is a unit struct:
#[derive(Eq, PartialEq, Clone, Default, Debug)]
pub struct Nil;
It holds nothing. Used as a tail it terminates a chain, and used on its own it is the empty list. It
derives Eq, PartialEq, Clone, Default, and Debug, so a list ending in Nil inherits those
traits structurally, and Nil itself compares equal to Nil. It is not in the prelude, so import
it from cgp::core::field::types.
Behavior
Nil is the base case of every recursion over a list it terminates. An operation that folds over a
product implements the step for Cons<Head, Tail> and the base case for Nil, and the
recursion stops when it reaches Nil. The string and path lists work the same way: a walk over
Chars stops at Nil, and a walk over PathCons stops at Nil.
Because Nil is a real, constructible value, the empty product Product![] is Nil, and the empty
value product![] is the Nil value. The empty string Symbol!("") is Symbol<0, Nil>, and a
unit struct that derives HasFields has Nil as its shape. A
builder or a conversion returns Nil when every field of a shape has been consumed. This is why an
empty record is a value the program can hold. The contrast with Void is exact. A value
with every branch ruled out cannot exist, so a sum ends in an uninhabited marker, while a record
ends in this inhabited one.
Examples
Each list ends in Nil, and the empty product, the empty string, and a unit struct's shape are all
Nil:
use cgp::core::base::types::PathCons;
use cgp::core::field::traits::ToFields;
use cgp::core::field::types::{Chars, Cons, Nil, Symbol};
use cgp::prelude::*;
#[derive(HasFields)]
pub struct Marker;
pub fn demo() {
// Each list ends in `Nil`; the annotations are the check.
let _row: PhantomData<Cons<u32, Cons<bool, Nil>>> = PhantomData::<Product![u32, bool]>;
let _name: PhantomData<Symbol<2, Chars<'h', Chars<'i', Nil>>>> =
PhantomData::<Symbol!("hi")>;
let _path: PhantomData<PathCons<Symbol!("a"), PathCons<Symbol!("b"), Nil>>> =
PhantomData::<Path!(@a.b)>;
// The empty product, the empty string, and a unit struct's shape are all `Nil`.
let empty: Product![] = product![];
assert_eq!(empty, Nil);
let _empty_name: PhantomData<Symbol<0, Nil>> = PhantomData::<Symbol!("")>;
let fields: Nil = Marker.to_fields();
assert_eq!(fields, Nil);
}
Each PhantomData annotation compiles only if the macro on its right expands to the chain on its
left.
When to use it
You read Nil at the end of a chain, and you write it as the base case of a fold. The macros
produce it everywhere else.
- Read
Nilas "the list ends here." In an expandedCons,Chars, orPathConschain, theNilis the terminator and marks the count of cells before it. - Implement a trait for
Nilas the base case when you fold over a product, beside the impl forCons<Head, Tail>. - Expect
Nil, notVoid, at the end of a record, a string, or a path. A sum ends inVoid, and the other lists end inNil. The wrong terminator in an error usually means the product and sum families have been mixed up.
Common Mistakes
Nil is inhabited, and Void is not. Nil is the real value of the empty product,
while Void is the uninhabited type of an empty choice. They are not interchangeable: variant
extraction relies on Void being uninhabited, which Nil is not.
Nil terminates the string and path lists as well as the product list. A Nil at the end of a
Chars chain or a PathCons chain is the same marker doing the same job, so
it is expected outside a record.
Related constructs
Cons: the head-and-tail cell this marker terminates in a record.Void: the sum list's uninhabited end marker, the counterpart to this one.CharsandPathCons: the string and path listsNilalso terminates.Product!: the macro whose empty form isNil.
The ideas behind it:
- Extensible records: where the empty and terminating record shape matters.
Source
An AI agent wrote this page using the CGP knowledge base. Its content was verified against the library's source. See How AI is used in this project.