Можно ли уменьшить количество клонирований?

[Mike Potanin]

 Добрый день!
Снова пытаюсь реализовать комбинаторные парсеры - в них активно используются замыкания.
Столкнулся с тем, что приходится часто использовать clone и требовать реализации Clone от используемых типов. Особенно смущает требование Clone от анализируемой строки.
Подозреваю, что надо изменить тип данных представления результата. Сейчас это Vec<(T,S)>, где T - результат, S - строка. Пробовал добавлять в разные места Box - уменьшить число клонирований не помогло.
Может быть есть более хитрые способы?

Исходник (онлайн-компилятором на данный момент не собирается, но на вчерашней и сегодняшней сборке работает):

pub trait Seq<T> {
//    fn empty() -> Self;
//    fn push(&self, t: T) -> Seq<T>;
    fn pop(&self) -> Option<(T, Self)>;
}

impl<'a> Seq<char> for &'a str {
  fn pop(&self) -> Option<(char,&'a str)> {
   if self.is_empty() {
     None
   } else {
     Some((self.char_at(0), self.slice_from(1)))
   }
  }
}

type ParseResult<S /*:Seq<C>*/,T> = Vec<(T,S)>;
type Parser<S /*:Seq<C>*/,T> = Box<Fn<(S,), ParseResult<S,T>> + 'static>;

fn preturn<T:Clone+'static,S>(v:T) -> Parser<S,T> {
  box move |s:S| vec![(v.clone(),s)]
}

fn elem<T,S:Seq<T>>(s:S) -> ParseResult<S, T> {
  match s.pop() {
    Some(r) => vec![r],
    None => Vec::new()
  }
}

fn pseq<T1:Clone,T2:Clone,C,S:Seq<C>+Clone>(p1:Parser<S,T1>, p2:Parser<S,T2>) -> Parser<S,(T1,T2)> {
  box move |s:S| {
     p1.call((s,)).iter().fold(Vec::new(), |a, r| match r.clone() { (r,s) => {
                             let mut m = Vec::new();
                             m.push_all(a.as_slice());
                             for r1 in p2.call((s,)).iter() {
                               match r1.clone() {
                                 (r1,s) => m.push(((r.clone(),r1),s))
                               }
                             }
                             m
                           }})
  }
}

fn main() {
  let s = "123456";
  println!("{}", pseq(box elem, preturn(1i32)).call((s,)));
  println!("{}", preturn(1i32).call((s,)));
}