Skip to content

Instantly share code, notes, and snippets.

@lalaithion
Created March 14, 2019 01:14
Embed
What would you like to do?
use std::rc::Rc;
use std::fmt::{Display, Debug, Error, Formatter};
/// Because we are dealing with immutable data, we shouldn't ever need the
/// owned variant of Lazy or the mutable version of Thunk.
use thunk::LazyRef;
use thunk::Thunk;
use crate::ListCell::*;
/// This macro constructs a thunk from a value. This needs to be a macro,
/// and not a function, because functions will evaluate their arguments
/// before invoking the function, and we explicitly don't want this to happen,
/// hence the macro and wrapping the value in a zero-argument function
/// before passing it to Thunk::defer. We also wrap the Thunk in an Rc, because
/// ownership + persistent data structures aren't very compatible concepts.
macro_rules! lazy {
( $x:expr ) => {
Rc::new(Thunk::defer(|| $x))
};
}
/// Each cell in the list contains either nothing, or a value and a reference
/// to the rest of the list.
enum ListCell<T> {
Nil,
Cell(Rc<T>, List<T>),
}
/// This type adds the laziness, by making each list a thunk instead of a strict value,
/// and also allows the internal thunk to be private, only accessable through member
/// functions.
struct List<T>(Rc<Thunk<ListCell<T>>>);
/// Since List wraps Rc, which implements Clone, it's easy and useful to implement Clone
/// on Lists too.
impl<T> Clone for List<T> {
fn clone(&self) -> Self {
List(Rc::clone(&self.0))
}
}
/// The implementation of various useful methods on Lists. Most of these are taken in
/// both name and behavior from Haskell's Data.List module (http://hackage.haskell.org/package/base-4.12.0.0/docs/Data-List.html)
impl<'a, T> List<T> {
fn empty() -> List<T> {
List(lazy!(Nil))
}
/// Returns a new list equivalent to the old one, but with a new
/// value prepended to the beginning of the list. I don't quite
/// like this notation, because ls.cons(x) puts x at the beginning
/// of the list. O(1).
fn cons(&self, value: T) -> List<T> {
List(lazy!(Cell(Rc::new(value), self.clone())))
}
fn cons_rc(&self, value: &Rc<T>) -> List<T> {
List(lazy!(Cell(value.clone(), self.clone())))
}
/// Returns the first element of the list, or None if the list is empty.
/// in Haskell, this is a partial function, which is widely considered
/// to be a mistake. O(1).
fn head(&self) -> Option<&T> {
match **self.0 {
Nil => None,
Cell(ref v, _) => Some(v),
}
}
/// Returns every element of the list except the first. In the case where the
/// list is empty, this returns the empty list. (Specifically, it returns itself.)
/// O(1)
fn tail(&self) -> List<T> {
match **self.0 {
Nil => self.clone(),
Cell(_, ref ls) => ls.clone(),
}
}
/// Returns every element but the last. In the case where the list is empty,
/// this returns the empty list. Amortized O(1), where looping over the List
/// uses a bit more processing, because for every element it must check if this element would
/// be the last, and if so, ignore it.
fn init(&self) -> List<T> {
match **self.0 {
Nil => self.clone(),
Cell(_, ref ls) => match **ls.0 {
Nil => ls.clone(),
Cell(ref v, ref ls) => List(lazy!(Cell(v.clone(), ls.init()))),
}
}
}
/// Returns the last element of the list, or None if the list is empty. O(n), as it must
/// strictly scan the entire list to find the last element.
fn last(&self) -> Option<&T> {
match **self.0 {
Nil => None,
Cell(ref v, ref ls) => match **ls.0 {
Nil => Some(v),
_ => ls.last(),
}
}
}
/// Concatenates two lists. Unintuitively, this is Amortized O(1).
/// The second list won't be touched until you finish traversing the first.
fn concat(&self, other: &List<T>) -> List<T> {
match **self.0 {
Nil => other.clone(),
Cell(ref v, ref ls) => List(lazy!(Cell(v.clone(), ls.concat(other)))),
}
}
/// Allows you to get the head and tail of a list with one operation.
/// Nice for pattern matching.
fn uncons(&self) -> (Option<&T>, List<T>) {
(self.head(), self.tail())
}
fn iter(&self) -> ListIterator<T> {
ListIterator(&self.0)
}
}
/// Iterator for iterating over references to values.
struct ListIterator<'a, T: 'a> (&'a ListCell<T>);
impl<'a, T> Iterator for ListIterator<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
match self.0 {
Nil => None,
Cell(t, ls) => { self.0 = &ls.0; Some(t) }
}
}
}
/// Iterator for iterating over cloned values.
/// Iterators must be mutable, so our ListIterator wraps a traditional list,
/// and simply replaces it's internal value with the tail of the list
struct ListCloneIterator<T> (List<T>);
impl<T: Clone> Iterator for ListCloneIterator<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
let curr = self.0.head().map(|x| x.clone());
self.0 = self.0.tail();
match curr {
None => None,
Some(v) => Some(v.clone()),
}
}
}
impl<T: Clone> IntoIterator for List<T> {
type Item = T;
type IntoIter = ListCloneIterator<T>;
fn into_iter(self) -> ListCloneIterator<T> {
ListCloneIterator(self)
}
}
/// People might want to Display lists, occasionally. Forces the entire list to display it.
impl<T: Display> Display for List<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
write!(f, "[")?;
for item in self.iter() {
write!(f, "{},", item)?;
}
write!(f, "]")?;
Ok(())
}
}
/// People might want to Debug lists, occasionally. Forces the entire list to debug it.
impl<T: Debug> Debug for List<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
write!(f, "[")?;
for item in self.iter() {
write!(f, "{:?},", item)?;
}
write!(f, "]")?;
Ok(())
}
}
/// People might want to test lists for Equality, occasionally. Forces the lists to their first
/// unequal element, or the entire list if equal.
impl<T: PartialEq> PartialEq for List<T> {
/// TODO(izaakweiss): I believe this can be rewritten using ListIterator and
/// made slightly easier to read, as well as non-recursive, and hence slightly faster.
fn eq(&self, other: &List<T>) -> bool {
match (self.uncons(), other.uncons()) {
((None, _), (None, _)) => true,
((None, _), (Some(_), _)) => false,
((Some(_), _), (None, _)) => false,
((Some(r), rs), (Some(l), ls)) => if r == l { rs == ls } else { false }
}
}
}
/// People might want to test lists for Equality, occasionally. Forces the lists to their first
/// unequal element, or the entire list if equal.
impl<T: Eq> Eq for List<T> {}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn it_works() {
let x: List<i32> = List::empty();
let y = x.cons(4);
let z = y.cons(7);
assert_eq!(z.tail(), y);
assert_eq!(y.tail(), x);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment