Return a concrete Iterator type in a child struct


#1

I have the following code

#[derive(Clone, Debug)]
pub struct SwiftContext {
    name: String,
}


pub trait RDD {
    type Item;

    fn compute<T: Iterator>(&self, part: u32) -> T;

    fn get_context(&self) -> SwiftContext;

    fn map<B, F>(self, f: F) -> MappedRDD<Self, F> where
        Self: Sized, F: FnMut(Self::Item) -> B {
        MappedRDD {sc: self.get_context(), prev: self, f: f}
    }
}

pub struct MappedRDD<P, F> {
    pub sc: SwiftContext,
    prev: P,
    f: F,
}


impl<B, P: RDD, F> RDD for MappedRDD<P, F> where F: FnMut(P::Item) -> B {
    type Item = B;
 
    fn compute<T: Iterator>(&self, part: u32) -> T { // error
        self.prev.compute(part).map(self.f)
    }

    fn get_context(&self) -> SwiftContext {
        self.sc.clone()
    }

}

The problem is in the compute method, because I need to return a concrete type. what I want to solve is introduce a new type in the trait. something like following

pub trait RDD {
    type Item;
    type computeType: Iterator; //new

    fn compute(&self, part: u32) -> Self::computeType;

    fn get_context(&self) -> SwiftContext;

    fn map<B, F>(self, f: F) -> MappedRDD<Self, F> where
        Self: Sized, F: FnMut(Self::Item) -> B {
        MappedRDD {sc: self.get_context(), prev: self, f: f}
    }
}

impl<B, P: RDD, F> RDD for MappedRDD<P, F> where F: FnMut(P::Item) -> B {
    type Item = B;
    type computeType = Map<P::computeType, F>; // error

    fn compute(&self, part: u32) -> Self::computeType {
        self.prev.compute(part).map(self.f)
    }


    fn get_context(&self) -> SwiftContext {
        self.sc.clone()
    }

}

But I do not know how to write the computeType in the MappedRDD.
I find the source code in the Map use the Self, but my MappedRDD do not implement the Iterator trait.

Any advice is thankful!


#2

I believe you want something like:

use std::iter::Map;

#[derive(Clone, Debug)]
pub struct SwiftContext {
    name: String,
}


pub trait RDD {
    type Item;
    type ComputeType: Iterator<Item=Self::Item>;

    fn compute(&self, part: u32) -> Self::ComputeType;

    fn get_context(&self) -> SwiftContext;

    fn map<B, F>(self, f: F) -> MappedRDD<Self, F> where
        Self: Sized, F: FnMut(Self::Item) -> B {
        MappedRDD {sc: self.get_context(), prev: self, f: f}
    }
}

pub struct MappedRDD<P, F> {
    pub sc: SwiftContext,
    prev: P,
    f: F,
}


impl<B, P: RDD, F> RDD for MappedRDD<P, F> where F: FnMut(P::Item) -> B {
    type Item = B;
    type ComputeType = Map<P::ComputeType, F>;
 
    fn compute(&self, part: u32) -> Self::ComputeType {
        self.prev.compute(part).map(self.f)
    }

    fn get_context(&self) -> SwiftContext {
        self.sc.clone()
    }

}

Unfortunately, this tries to copy the function self.f. One would like to be able to borrow the function but rust doesn’t let you do that right now (it requires HKT):

use std::iter::Map;

#[derive(Clone, Debug)]
pub struct SwiftContext {
    name: String,
}


pub trait RDD {
    type Item;
    type ComputeType<'a>: Iterator<Item=Self::Item>; // Parametrize ComputeType over some lifetime 'a

    fn compute<'a>(&'a self, part: u32) -> Self::ComputeType<'a>; // Allow compute to borrow self.

    fn get_context(&self) -> SwiftContext;

    fn map<B, F>(self, f: F) -> MappedRDD<Self, F> where
        Self: Sized, F: FnMut(Self::Item) -> B {
        MappedRDD {sc: self.get_context(), prev: self, f: f}
    }
}

pub struct MappedRDD<P, F> {
    pub sc: SwiftContext,
    prev: P,
    f: F,
}


impl<B, P: RDD, F> RDD for MappedRDD<P, F> where F: Fn(P::Item) -> B {
    type Item = B;
    type ComputeType<'a> = Map<P::ComputeType, &'a F>;
 
    fn compute<'a>(&'a self, part: u32) -> Self::ComputeType<'a> {
        self.prev.compute(part).map(self.f)
    }

    fn get_context(&self) -> SwiftContext {
        self.sc.clone()
    }

}

Alternatively, one could write:

use std::iter::Map;
use std::rc::Rc;

#[derive(Clone, Debug)]
pub struct SwiftContext {
    name: String,
}


pub trait RDD {
    type Item;
    type ComputeType: Iterator<Item=Self::Item>;

    fn compute(&self, part: u32) -> Self::ComputeType;

    fn get_context(&self) -> SwiftContext;

    fn map<B, F>(self, f: F) -> MappedRDD<Self, F> where
        Self: Sized, F: FnMut(Self::Item) -> B {
        MappedRDD {sc: self.get_context(), prev: self, f: Rc::new(f)}
    }
}

pub struct MappedRDD<P, F> {
    pub sc: SwiftContext,
    prev: P,
    f: Rc<F>,
}


impl<B, P: RDD, F> RDD for MappedRDD<P, F> where F: Fn(P::Item) -> B {
    type Item = B;
    type ComputeType = Map<P::ComputeType, Rc<F>>;
 
    fn compute(&self, part: u32) -> Self::ComputeType {
        self.prev.compute(part).map(self.f.clone())
    }

    fn get_context(&self) -> SwiftContext {
        self.sc.clone()
    }

}

… If rust implemented Fn for Rc<F> where F: Fn. But it doesn’t…

Regardless, this isn’t a general solution as compute will, in general, want to borrow the RDD… There are some nasty ways to get this to work (maybe) but hopefully someone else has a better solution.


#3

Thanks for your reply!

But after I try to use the last method: using the Rc<F>, there is still an error:

the trait bound std:rc::Rc<F>: std::ops:FnMut(<P as rdd::RDD>::Item) is not satisfied [E0277]

In fact, I do know whether introduce the ComputeType is th right way.

What I want is return an Iterator from the compute method.


#4

However, my post was still pretty awful (I was in a bit of a rush). Basically, there are two problems here:

First, it’s hard to name closures. See:

Second, associated types can’t depend on the lifetime of self (the second bad solution I gave). The latest proposal to fix this is here:

… but it lacks on implementation.

The actual solution is to return a concrete Box<Iterator> instead of using an associated type:

#[derive(Clone, Debug)]
pub struct SwiftContext {
    name: String,
}

pub trait RDD {
    type Item;

    fn compute<'a>(&'a self, part: u32) -> Box<Iterator<Item=Self::Item> + 'a>;

    fn get_context(&self) -> SwiftContext;

    fn map<B, F>(self, f: F) -> MappedRDD<Self, F> where
        Self: Sized, F: FnMut(Self::Item) -> B {
        MappedRDD {sc: self.get_context(), prev: self, f: f}
    }
}

pub struct MappedRDD<P, F> {
    pub sc: SwiftContext,
    prev: P,
    f: F,
}


impl<B, P: RDD, F> RDD for MappedRDD<P, F>
    where F: Fn(P::Item) -> B
{
    type Item = B;

    fn compute<'a>(&'a self, part: u32) -> Box<Iterator<Item=Self::Item> + 'a> {
        Box::new(self.prev.compute(part).map(&self.f))
    }

    fn get_context(&self) -> SwiftContext {
        self.sc.clone()
    }

}

Note: I had to change FnMut to Fn because this solution borrows it (closures can’t be cloned at the moment).


#5

Thanks! this works now.

Btw: The polymorphism in rust is really hard to use, and there are few material about it. I really do not know how people begin study it.


#6

For me, practice and reading RFCs discussions has helped but that’s not really a good solution. We really need better docs, blog posts, books, etc. on how to get the most out of rust’s type system. Unfortunately, most docs focus either on getting started with rust or doing unsafe things in rust but not many focus on software patterns in rust. To be fair, there isn’t really a consensus on software patterns in rust at the moment anyways.


#7

Is there any schedule to stable the software patterns in rust?


#8

Software patterns mature as a language matures, there’s no way to set a scheduled. For now, all we can do is document how the rust type system works (e.g., the rust book); it’s hard to say how it should be used due to lack of experience.


#9

Yes, Software patterns should learn from experience. Thanks!