↑Programmieren in Rust

Beispiele: Listen

Einfach verkettete Listen

mod list {
    use std::fmt;

    pub struct Node<T> {
        pub item: T,
        pub next: List<T>
    }
    
    pub enum List<T> {
        None,
        Node(Box<Node<T>>)
    }
    
    impl<T> List<T> {
        pub fn node(item: T, next: List<T>) -> List<T> {
            List::Node(Box::new(Node {item, next}))
        }

        pub fn map<U>(&self, f: impl Fn(T)->U) -> List<U>
        where T: Clone
        {
            match self {
                List::Node(node) => List::node(
                    f(node.item.clone()), node.next.map(f)),
                List::None => List::None
            }
        }
    }
    
    pub fn list<T: Clone>(a: &[T]) -> List<T> {
        a.iter().rev().fold(List::None,
            |acc, x| List::node(x.clone(), acc))
    }

    impl<T: fmt::Display> fmt::Display for List<T> {
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
            write!(f, "[")?;
            let mut p = self;
            let mut first = true;
            while let List::Node(node) = p {
                if first {first = false;} else {write!(f, ", ")?;}
                write!(f, "{}", node.item)?;
                p = &node.next;
            }
            write!(f, "]")
        }
    }
}

use list::{List, list};

fn main() {
    let a: List<i32> = list(&[1, 2, 3, 4]);
    println!("{}", a.map(|x| 2*x));
}

Probleme, die hier bewusst offen gelassen wurden:

1. Man müsste die Algorithmen so schreiben, dass alle Trait-Bounds T: Clone verschwinden.
2. Man sollte map besser iterativ formulieren, damit es nicht zu einem Überlauf des Aufrufstapels kommt.
3. Auch der implizit erzeugte Destruktor ist rekursiv, würden also ebenso zum Überlauf des Aufrufstapels führen. Hinzufügen einer iterativen Zerstörung als Implementierung von drop behebt dieses Problem.