rust / intermediate
Snippet
Rekursive Enum-Varianten für Listenoperationen
Rekursive Enums ermöglichen elegante verkettete Listen-Implementierungen, bei denen jede Variante sich selbst enthalten kann. Box<T> ist hier entscheidend, da der Compiler die Größe jeder Variante zur Kompilierzeit kennen muss. Ohne Indirektion würde ein rekursiver Typ eine unendliche Größe haben. Die Cons-Variante hält Daten plus einen geboxten Zeiger auf das nächste Element, während Nil als Terminalfall dient. Dieses Muster zeigt, wie Rusts Typsystem rekursive Datenstrukturen natürlich ausdrückt und dabei Speichersicherheit durch Heap-Allokation gewährleistet.
snippet.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
enum List<T> {Cons(T, Box<List<T>>),Nil,}impl<T> List<T> {fn new() -> Self { List::Nil }fn prepend(self, elem: T) -> Self {List::Cons(elem, Box::new(self))}fn len(&self) -> usize {match self {List::Cons(_, tail) => 1 + tail.len(),List::Nil => 0,}}fn map<U, F>(self, f: F) -> List<U>where F: FnOnce(T) -> U {match self {List::Cons(head, tail) => f(head).prepend(*tail.map(f)),List::Nil => List::Nil,}}}fn main() {let list = List::Nil.prepend(3).prepend(2).prepend(1);println!("Length: {}", list.len());let doubled = list.map(|x| x * 2);}
Erklärung
1
enum List<T> {
Generische Enum-Deklaration mit Typparameter T
2
Cons(T, Box<List<T>>),
Cons hält Wert und Zeiger auf nächste Element
3
Nil,
Terminalvariante für leere Liste
4
fn prepend(self, elem: T) -> Self {
Konsumiert self um neue Liste mit Element vorne zu erstellen
5
1 + tail.len()
Rekursiver Aufruf durchläuft Liste und zählt Elemente