How do I implement an O(n) time and O(1) space FromIterator implementation for a linked list in safe code?

Question

I have a Cons list:

#[derive(Debug)]
pub enum Cons {
    Empty,
    Pair(i64, Box<Cons>),
}

I want to implement FromIterator<i64> for this type, in an efficient manner.

Attempt one is straightforward: implement a push method which recursively traverses the list and transforms a Cons::Empty into a Cons::Pair(x, Box::new(Cons::Empty)); repeatedly call this push method. This operation is O(n^2) in time and O(n) in temporary space for the stack frames.

Attempt two will combine the recursion with the iterator to improve the time performance: by pulling a single item from the iterator to construct a Cons::Pair and then recursing to construct the remainder of the list, we now construct the list in O(n) time and O(n) temporary space:

impl FromIterator<i64> for Cons {
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = i64>,
    {
        let mut iter = iter.into_iter();
        match iter.next() {
            Some(x) => Cons::Pair(x, Box::new(iter.collect())),
            None => Cons::Empty,
        }
    }
}

In C, it would be possible to implement this method using O(n) operations and O(1) working space size. However, I cannot translate it into Rust. The idea is simple, but it requires storing two mutable pointers to the same value; something that Rust forbids. A failed attempt:

impl FromIterator<i64> for Cons {
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = i64>,
    {
        let mut iter = iter.into_iter();
        let ret = Box::new(Cons::Empty);
        let mut cursor = ret;
        loop {
            match iter.next() {
                Some(x) => {
                    let mut next = Box::new(Cons::Empty);
                    *cursor = Cons::Pair(x, next);
                    cursor = next;
                }
                None => break,
            }
        }
        return *ret;
    }
}

error[E0382]: use of moved value: `next`
  --> src/lib.rs:20:30
   |
18 |                     let mut next = Box::new(Cons::Empty);
   |                         -------- move occurs because `next` has type `Box<Cons>`, which does not implement the `Copy` trait
19 |                     *cursor = Cons::Pair(x, next);
   |                                             ---- value moved here
20 |                     cursor = next;
   |                              ^^^^ value used here after move

error[E0382]: use of moved value: `*ret`
  --> src/lib.rs:25:16
   |
13 |         let ret = Box::new(Cons::Empty);
   |             --- move occurs because `ret` has type `Box<Cons>`, which does not implement the `Copy` trait
14 |         let mut cursor = ret;
   |                          --- value moved here
...
25 |         return *ret;
   |                ^^^^ value used here after move

Is it possible to perform this algorithm in safe Rust? How else could I implement an efficient FromIterator for my Cons type? I understand that I may be able to make some headway by switching Box to Rc, but I'd like to avoid this if possible.

[Please don't use linked lists](https://rust-unofficial.github.io/too-many-lists/) — Shepmaster, Feb 25 '22 at 19:26
@PitaJ the failing Rust code appears to be a straightforward port of the expected C implementation. — Shepmaster, Feb 25 '22 at 19:29

Shepmaster · Accepted Answer · 2022-02-28T02:57:53.133

You are attempting to have two owners of a single variable, but Rust only allows a single owner. You do this twice: once for ret and once for next. Instead, use mutable references.

I chose to introduce a last() method which can be used in an implementation of Extend and participate in more abstractions.

#[derive(Debug)]
pub enum Cons {
    Empty,
    Pair(i64, Box<Cons>),
}

impl Cons {
    fn last(&mut self) -> &mut Self {
        let mut this = self;
        loop {
            eprintln!("1 loop turn");

            match this {
                Cons::Empty => return this,
                Cons::Pair(_, next) => this = next,
            }
        }
    }
}

impl FromIterator<i64> for Cons {
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = i64>,
    {
        let mut this = Cons::Empty;
        this.extend(iter);
        this
    }
}

impl Extend<i64> for Cons {
    fn extend<I>(&mut self, iter: I)
    where
        I: IntoIterator<Item = i64>,
    {
        let mut this = self.last();
        for i in iter {
            eprintln!("1 loop turn");

            *this = Cons::Pair(i, Box::new(Cons::Empty));
            this = match this {
                Cons::Empty => unreachable!(),
                Cons::Pair(_, next) => next,
            };
        }
    }
}

fn main() {
    dbg!(Cons::from_iter(0..10));
}

This produces

Pair(0, Pair(1, Pair(2, Pair(3, Pair(4, Pair(5, Pair(6, Pair(7, Pair(8, Pair(9, Empty))))))))))

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> ⏚

How do I implement an O(n) time and O(1) space FromIterator implementation for a linked list in safe code?

1 Answers1