Cons in Rust

2026-03-30

Ownership

Usually the ownership rules are

Each value in Rust has an owner.
There can only be one owner at a time.
When the owner goes out of scope, the value will be dropped.

Each value in Rust has an owner.

This rule is easy to understand, a segment

let x = <expr>;

creates a binding x to an object, which has value that the calculate result of <expr> (such as vx). We say the name x is the owner of this object vx.

There can only be one owner at a time.

Consider this code segment

let s1 = String::from("hello");
let s2 = s1;

If the object from expression String::from("hello") is vs, then at line 1. s1 is the owner of vs, and line 2. will let s2 the owner of vs, so s1 will lost its identity, then

println!("{s1}, world!")

will produce an error

error[E0382]: borrow of moved value: `s1`

When the owner goes out of scope, the value will be dropped.

Let’s see the implement of std::mem::drop function in the standard library:

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
#[rustc_const_unstable(feature = "const_destruct", issue = "133214")]
#[rustc_diagnostic_item = "mem_drop"]
pub const fn drop<T>(_x: T)
where
    T: [const] Destruct,
{
}

this is not a macro with builtin attribute #[rustc_builtin_macro]

#[rustc_builtin_macro]
macro_rules! drop {
    ($name:expr $(,)?) => {{ /* compiler built-in */ }};
}

or a function with attribute #[cfg(feature = "compiler-builtins")], the document comment clearly said

/// existing comments...
///
/// This function is not magic; it is literally defined as
///
/// ```
/// pub fn drop<T>(_x: T) {}
/// ```
///
/// Because `_x` is moved into the function, it is automatically [dropped][drop] before
/// the function returns.
///
/// existing comments...

so when the function called drop(x), then x are passed in the function body

drop(x);
/* ========================= */
pub fn drop<T>(_x: T) {     // <- `x` are passed in
    // empty                // <- `x` are here when `drop(x)` called
                            // but `x` is statis in here
}                           // out of the function body, `x` cannot be carried out
                            // so `x` will lost while the function stack poped

Cons in Lisp

Cons can be easily defined in the S-expression form:

(defun (cons (x y)) (lambda (m) (funcall m x y)))
(defun (car (p)) (funcall p (lambda (x y) x)))
(defun (cdr (p)) (funcall p (lambda (x y) x)))

that means (cons x y) is a function (lambda (m) (m x y)), or mathematically

\operatorname{cons}(x,y)(m)=m(x,y)

so consider a nest cons, such as (cons x1 (cons x2 null)), then

\operatorname{cons}(x_1, \operatorname{cons}(x_2, \varnothing)(m_2))(m_1)=m_1(x_1, m_2(x_2, \varnothing))

the function parameter $m_1$ and $m_2$ is not matter, it only holds two value as a container. If we denote $m_k(x,y)$ as $x\to_k y$ , then we can see that the cons actually constructed a linked list

\operatorname{cons}(x_1, \operatorname{cons}(x_2, \varnothing)(m_2))(m_1)=x_1\to_1(x_2\to_2\varnothing)

The car and cdr is defined as

\operatorname{car}(p)=p((x,y)\mapsto x),\qquad \operatorname{cdr}(p)=p((x,y)\mapsto y)

that’s the prototype of head and tail function in FP(functional programming) language. For a cons, we have

\operatorname{car}(\operatorname{cons}(x_1, x_2))=\operatorname{cons}(x_1, x_2)(u)\big|_{u(x,y)=x}=u(x_1,x_2)\big|_{u(x,y)=x}=x_1

and similar $\operatorname{cdr}(\operatorname{cons}(x_1, x_2))=x_2$ .

In fact, commonly FP language such as Haskell, OCaml and so on, their list is actually a cons-like structure. Such as Haskell, their List actually is

data List a = [] | a : (List a)

this definition are same naturally with the definition of cons, where a : (List a) can be written as (m, x, y) where x :: a and y :: List a. A list [x1, x2] can be written as

x1 : x2 : []

just like $x_1\to_1(x_2\to_2\varnothing)$ .

So, in FP language, their list is actually linked-list in real-world practice.

Linked List and Cons

Let’s think about the linked list recursively. A linked list is an abstract concept, so we cannot define the ADS directly in IP(imperative programming) language. A linked list is a sequence of linked list node, which holds a pointer direct to next node, so

template<typename T>
class Node {
    public:
        Node(T val): val(val), next(nullptr) {};
        Node(T val, Node<T>* next): val(val), next(next) {};
    private:
        T val;
        Node<T>* next;
};

so what a Node is? Is a value T and a pointer with type Node<T>*, this is the model of Cons cons(x, y) where x is T val and y is Node<T>* next. This inspires us to use enumeration to modelling the cons functionally.

Implement Cons in Rust

Sized Cons Type

So our first model is

enum List<T> {
    Cons(T, List<T>),
    Nil,
}

emm… there is a question, the second part of cons is the reference of next cons (and in the C++ model we can see it is implemented by pointer), so we should fix it

enum List<'a, T> {
    Cons(T, &'a List<'a, T>),
    Nil,
}

In principle, if we strict coping the next cons to the second parameter in the constructor Cons(), the result is theoretical right. But, if we write this code, the enum List<T> cannot be created because the compiler cannot calculate the real size of the enum, because the type definition is recursive:

|L|=\begin{dcases} |T|+|L'|,&L=\operatorname{Cons}(T, L')\\ |\operatorname{Nil}|,&L=\mathrm{Nil} \end{dcases}

but if we use reference, the real size can be calculated determinately

|L|=\begin{dcases} |T|+|\&|,&L=\operatorname{Cons}(T, \&L')\\ |\operatorname{Nil}|,&L=\mathrm{Nil} \end{dcases}

so List<T> can be a Sized type.

Box Pointer

Cons(T, &List<T>) doesn’t holds the ownership of tail, is just a reference to tail. Consider an example

fn a_scope() -> List<i32> {
    let tail = List::Nil;
    let xs = List::Cons(1, &tail);
    xs
}

xs still holds a reference to tail, but tail are dropped when function returned, so xs will holds a dangling reference:

error[E0515]: cannot return value referencing local variable `tail`
 --> src/main.rs:4:5
  |
3 |     let xs = List::Cons(1, &tail);
  |                            ----- `tail` is borrowed here
4 |     xs
  |     ^^ returns a value referencing data owned by the current function

So we can use Box pointer to holds the tail, because List holds the ownership of the Box, and Box holds the reference to tail, so List can reference tail since the whole life cycle of itself:

enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

and if use Box, you should explicit boxing when you construct a List:

let tail = List::Nil;
let xs = List::Cons(1, Box::new(tail));
//                     -------- you should explicit boxing
//                              when you use `List::Cons()`

We know the linked list can be used to construct tree ADT from leaves to root, such as a tree

R\to N_1\to\begin{dcases}N_{11}\to\begin{dcases}L_{111}\\ L_{112}\end{dcases}\\ N_{12}\to L_{121}\end{dcases}

it can be expressed reversely as some linked lists

\begin{aligned} C_0=(R\to\varnothing), ~ C_1=(N_1\to R), ~ C_{11}=(N_{11}\to C_1), ~ C_{12}=(N_{12}\to C_1)\\ C_{111}=(L_{111}\to C_{11}), ~ C_{112}=(L_{112}\to C_{11}), ~ C_{121}=(L_{121}\to N_{12}) \end{aligned}

but Cons(T, Box<List<T>>) holds the ownership of the box Box<List<T>>, so another Cons can not use the tail-box, such as this code

let tail = Box::new(List::Nil);

let a = List::Cons(1, tail);
let b = List::Cons(2, tail);

will produce an error

error[E0382]: use of moved value: `tail`
 --> src/main.rs:4:27
  |
1 |     let tail = Box::new(List::Nil);
  |         ---- move occurs because `tail` has type `Box<List<i32>>`, which does not implement the `Copy` trait
2 |
3 |     let a = List::Cons(1, tail);
  |                           ---- value moved here
4 |     let b = List::Cons(2, tail);
  |                           ^^^^ value used here after move

Rc Pointer

To fix the question, we should not holds the ownership of box, so we use the reference counter pointer to boxing the tail

use std::rc::Rc;

enum List<T> {
    Cons(T, Rc<List<T>>),
    Nil,
}

then we can let to cons share a common tail

let tail = Rc::new(List::Nil);

let a = List::Cons(1, Rc::clone(&tail));
let b = List::Cons(2, Rc::clone(&tail));

the Rc::clone function is to clone the Rc pointer, is not to clone the tail itself, that’s why we use Rc::clone(&tail) instead the equivalent expression tail.clone() (because tail is just a Rc pointer let tail = Rc::new(List::Nil)).

So, what’s the cost? The Rc<> box cannot holds the ownership of tail, so you can’t take the tail out with its’ ownership, such as

fn take_tail<T>(list: List<T>) -> List<T> {
    match list {
        List::Cons(_, tail) => *tail,
        List::Nil => List::Nil,
    }
}

this code can compiled for Box cons-list, and cannot compiled for Rc cons-list.

Result

use std::rc::Rc;
use std::fmt;

pub enum List<T> {
    Cons(T, Rc<List<T>>),
    Nil,
}

impl<T: fmt::Display> List<T> {
    fn to_str(&self) -> String {
        match self {
            List::Cons(x, cons) => fmt::format(format_args!("{} -> {}", x, cons.to_str())),
            List::Nil => "<Nil>".to_string(),
        }
    }
}

impl<T: fmt::Display> fmt::Display for List<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.to_str())
    }
}

pub use crate::List::Cons;
pub use crate::List::Nil;

References

cons. Wikipedia. Jan 18, 2026. Available at https://en.wikipedia.org/wiki/Cons .
Steve Klabnik, Carol Nichols, Chris Krycho, with contributions from the Rust Community. The Rust Programming Language. Feb 3, 2026 (Commit 05d1142). Available at https://doc.rust-lang.org/book/ .