fork download 
  1. enum List<T> {
  2. 	Cons(T, Box<List<T>>),
  3. 	Nil,
  4. }
  5. impl<T: Copy + PartialOrd> List<T> {
  6. 	fn nil() -> Self {List::Nil}
  7. 	fn prepend(self, x: T) -> Self {
  8. 		List::Cons(x, Box::new(self))
  9. 	}
  10. 	fn each<F>(&self, f: F) where F: Fn(&T) {
  11. 		self.fold(|(), x| f(x), ());
  12. 	}
  13. 	fn fold<F, U>(&self, f: F, acc: U) -> U where F: Fn(U, &T) -> U {
  14. 		match self {
  15. 			List::Nil => acc,
  16. 			List::Cons(x, xs) => {
  17. 				let acc = f(acc, x);
  18. 				xs.fold(f, acc)
  19. 			}
  20. 		}
  21. 	}
  22. 	fn rev(&self) -> Self {
  23. 		self.fold(|acc, &x| acc.prepend(x), List::<T>::nil())
  24. 	}
  25. 	fn concat(&self, other: &Self) -> Self {
  26. 		self.rev().fold(|acc, &x| acc.prepend(x), other.rev().fold(|acc, &x| acc.prepend(x), List::<T>::nil()))
  27. 	}
  28. 	fn partition<F>(&self, f: F) -> (Self, Self) where F: Fn(&T) -> bool {
  29. 		self.rev().fold(
  30. 			|(ts, fs), x| if f(x) {(ts.prepend(*x), fs)} else {(ts, fs.prepend(*x))},
  31. 			(List::<T>::nil(), List::<T>::nil())
  32. 		)
  33. 	}
  34. 	fn qsort(&self) -> Self {
  35. 		match self {
  36. 			List::Nil => List::Nil,
  37. 			List::Cons(pivot, tail) => {
  38. 				let (smaller, rest) = tail.partition(|x| *x < *pivot);
  39. 				smaller.qsort().concat(&rest.qsort().prepend(*pivot))
  40. 			}
  41. 		}
  42. 	}
  43. }
  44. fn main() {
  45. 	let list = List::<i32>::nil().prepend(4).prepend(8).prepend(8).prepend(3).rev();
  46. 	list.each(|n| print!("{}", n));println!("");
  47. 	list.qsort().each(|n| print!("{}", n));println!("");
  48. }
  49.  
Success #stdin #stdout 0.01s 5448KB
comments (?)
stdin 
Standard input is empty
stdout 
4883
3488
https://ideone.com/0Ro48L
language:
Rust (rust 1.56)
created:
225 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!