list4.rs

use std::fmt;
use List::{Cons, Nil};
use std::sync::Arc;
 
#[derive(PartialEq, Clone)]
enum List<T> {
  Cons(T, Arc<List<T>>),
  Nil
}
 
impl<T> fmt::Display for List<T> where T : fmt::Display {
  fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
    match *self {
      Cons(ref head, ref tail) => 
        {
          write!(f, "{head} :: ", head = head);
          write!(f, "{tail} ", tail = tail)
        }
      Nil => write!(f, "Nil")
    }
  }
}

fn flat_map<T, U>(list: &List<T>, f: &Fn(T) -> List<U>) -> List<U> where T: Copy, T: Sized, T: Copy, T: PartialEq, U: Copy, U: Sized, U: PartialEq {
  match *list {
    Cons(ref head, ref tail) => concat(&f(*head), flat_map(tail, f)),
    Nil => Nil
  }
}

fn concat<T>(list: &List<T>, b: List<T>) -> List<T> where T: Copy, T: Sized {
  fold_right(list, b, &|x, y| Cons(x, Arc::new(y)))
}
 
fn fold_right<T, U>(list: &List<T>, result: U, f: &Fn(T, U) -> U) -> U where T: Copy, T: Sized {
  match *list {
    Cons(ref head, ref tail) => 
      f(*head, fold_right(tail, result, f)),
    Nil => result
  }
}

fn fold_left<T, U>(list: &List<T>, result: U, f: &Fn(U, T) -> U) -> U where T: Copy, T: Sized {
  match *list {
    Cons(ref head, ref tail) => fold_left(tail, f(result, *head), f), 
    Nil => result
  }
}
 
fn map<T, U>(list: &List<T>, f: &Fn(T) -> U) -> List<U> where T: Copy , U: Copy {
  fold_right(list, Nil, &|x, y| Cons(f(x), Arc::new(y)))
}
 
fn new_list<T>(args: Vec<T>) -> List<T> where T: Copy {
  let mut vec = args;
  let mut x: List<T> = Nil;
  while vec.len() > 0 {
    match vec.pop() {
      Some(e) => x = Cons(e, Arc::new(x)),
      None => {}
    }
  }
  x
}
 
fn main() {
  let list = new_list(vec![1, 2, 3, 4, 5]);
  println!("{list}", list = flat_map(&list, &|x| new_list(vec![x, x])));
}

result.txt

>rustc list4.rs
<std macros>:2:1: 2:54 warning: unused result which must be used, #[warn(unused_must_use)] on by default
<std macros>:2 $ dst . write_fmt ( format_args ! ( $ ( $ arg ) * ) ) )
               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<std macros>:1:1: 2:56 note: in expansion of write!
list4.rs:16:11: 16:48 note: expansion site
list4.rs:43:1: 48:2 warning: function is never used: `fold_left`, #[warn(dead_code)] on by default
list4.rs:43 fn fold_left<T, U>(list: &List<T>, result: U, f: &Fn(U, T) -> U) -> U where T: Copy, T: Sized {
list4.rs:44   match *list {
list4.rs:45     Cons(ref head, ref tail) => fold_left(tail, f(result, *head), f),
list4.rs:46     Nil => result
list4.rs:47   }
list4.rs:48 }
list4.rs:50:1: 52:2 warning: function is never used: `map`, #[warn(dead_code)] on by default
list4.rs:50 fn map<T, U>(list: &List<T>, f: &Fn(T) -> U) -> List<U> where T: Copy , U: Copy {
list4.rs:51   fold_right(list, Nil, &|x, y| Cons(f(x), Arc::new(y)))
list4.rs:52 }

>list4.exe
1 :: 1 :: 2 :: 2 :: 3 :: 3 :: 4 :: 4 :: 5 :: 5 :: Nil