rust-list

Implementation of a singly linked list in Rust. It is the recursively defined list that is introduced in Chapter 15 of the Rust Book. While the linked list is disfavored in Rust, it's a familiar structure to many functional programmers.

This crate extends the implementation of the basic cons list found straight out of the Rust Book to offer some conveniences similar to those implemented for the Vec. Specifically, a list! macro for easy instantiation and manual implementations of the following traits:

• Display
• Iterator
• IntoIterator
• FromIterator

Derived traits:

• Debug
• Default
• PartialEq
• PartialOrd

Definition

The type definition is lifted straight out of the Book.

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

Usage

Creating a new list

A macro list! is defined to allow for easy instantiation. Otherwise the cons() and nil() functions are provided as an alternative.

  use rust_list::{List, list, nil, cons};
  use rust_list::List::{Cons, Nil};

  let xs = list![1, 2, 3];
  let ys = cons(1, cons(2, cons(3, nil())));
  assert_eq!(xs, ys);
  assert_eq!("list![1, 2, 3]", xs.to_string());

  // Defined manually
  assert_eq!(xs, Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil)))))));

Manipulation

  let mut xs = list![1, 2, 3];
  xs.push(0);
  assert_eq!(xs, list![0, 1, 2, 3]);
  assert_eq!(Some(&3), xs.last());

  assert_eq!(xs.len(), 4);
  assert_eq!(xs.is_empty(), false);

  xs.pop();
  assert_eq!(xs, list![1, 2, 3]);

  xs.append(list![4, 5, 6]);
  assert_eq!(xs, list![1, 2, 3, 4, 5, 6]);
  assert_eq!("list![1, 2, 3, 4, 5, 6]", xs.to_string());

  xs.reverse();
  assert_eq!(xs, list![6, 5, 4, 3, 2, 1]);

  let ys: List<_> = xs.map(|x| x * 2).collect();
  assert_eq!(ys, list![12, 10, 8, 6, 4, 2]);

  let zs: List<_> = xs.into_iter().filter(|x| *x < 4).collect();
  assert_eq!(zs, list![3, 2, 1]);

  assert_eq!(zs.fold(0, |acc, x| acc + x * 2), 12);

  let id = list![1, 2, 3].rfold(Nil, |xs, x| cons(x, xs));
  assert_eq!(id, list![1, 2, 3]);