Assignment 4

Many data types have algebraic structure that can be captured by a shared interface. This is a common programming pattern in Haskell, and makes appearances in the Rust standard library. The goal of this problem is to generalize this idea.

All algebraic structures we'll consider in this problem deal with a binary operators. We'll abstract out this operator as part of a generic trait:

trait BinOp<T> {
    fn op(lhs: T, rhs: T) -> T;
}

A semigroup is a set \(X\) together with a binary operation \(\circ : X \to X \to X\) which is associative.

It's possible to define a concatenation operation (mconcat) for any semigroup, which takes a starting value and an iterator, and folds the operator over the values of the iterator:

trait Semigroup<O> where
    O: BinOp<Self>,
    Self: Sized
{
    fn mconcat<I: Iterator<Item=Self>>(start: Self, iter: I) -> Self {
        let mut out = start;
        for item in iter {
            out = O::op(out, item)
        }
        out
    }
}

This trait is generic over operators of a given type. For technical reasons, we also require types on which we define semigroups are Sized.

A monoid is a set \(X\) and an associative binary operator \(\circ : X \to X \to X\) and a designated unit element \(u \in X\).

The tasks for this problem:

• Define a monoid trait in analogy with the Semigroup trait, and so that Semigroup is a supertrait.
• Implement these traits for i32 and String so that the tests below.

Part of this problem is reverse engineering. What kind of thing should Add be? What do you need to do in order to overload terms? I would recommend looking over section on Advanced Traits in RPL for some hints. Note that one of the upshots of this pattern is that we can have multiple algebraic traits for a given type with different operators, and we can have a uniform convention for referring to kinds of operators across types.

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn mconcat_semi_add_i32() {
        let expected = <i32 as Semigroup<Add>>::mconcat(10, vec![1, 2, 3, 4, 5].into_iter());
        assert_eq!(expected, 25)
    }

    #[test]
    fn mconcat_semi_mul_i32() {
        let expected = <i32 as Semigroup<Mul>>::mconcat(10, vec![1, 2, 3, 4, 5].into_iter());
        assert_eq!(expected, 1200)
    }

    #[test]
    fn mconcat_mon_add_i32() {
        let expected = <i32 as Monoid<Add>>::mconcat(vec![1, 2, 3, 4, 5].into_iter());
        assert_eq!(expected, 15)
    }

    #[test]
    fn mconcat_mon_mul_i32() {
        let expected = <i32 as Monoid<Mul>>::mconcat(vec![1, 2, 3, 4, 5].into_iter());
        assert_eq!(expected, 120)
    }

    #[test]
    fn mconcat_semi_str() {
        let s1 = String::from("abc");
        let s2 = String::from("def");
        let s3 = String::from("ghi");
        let expected = <String as Semigroup<Add>>::mconcat(s1, vec![s2, s3].into_iter());
        let actual = String::from("abcdefghi");
        assert_eq!(expected, actual);
    }

    #[test]
    fn mconcat_mon_str() {
        let s1 = String::from("abc");
        let s2 = String::from("def");
        let s3 = String::from("ghi");
        let expected = <String as Monoid<Add>>::mconcat(vec![s1, s2, s3].into_iter());
        let actual = String::from("abcdefghi");
        assert_eq!(expected, actual)
    }
}

One of the deficits of traits as compared to Type classes is the inability to define traits on type constructors. This means it's very difficult to implement things like functors in Rust. That said, it's not impossible. In this problem we'll be hacking functors into Rust.

In rough terms, a functor is a type constructor (formally, a type of kind \(\texttt{Type} \to \texttt{Type}\)) for which it's possible to define a mapping function. We tend to think of functors as "things which hold other things" like Option or Vec. The mapping operation allows you to apply a function to the "inner" thing without disturbing the structure of the "outer" thing. In Haskell, we define the Functor type class as:

class Functor (f :: Type -> Type) where
  fmap :: (a -> b) -> f a -> f b

Without getting into the Haskell of it all, the idea is that fmap is a higher-order function that takes a function and "lifts" it to a function to the level of the "outer" thing. The benefit of this that we can define functions against this interface, and derive code that generalizes across a wide range of types.

Rust has a hard-coded implementation of map for Option:

fn map<U, F>(self, f: F) -> Option<U> where
    F: FnOnce(T) -> U,
{
    match self {
        Some(x) => Some(f(x)),
        None => None,
    }
}

But there is no mechanism to generalize this in the Rust standard library. Again, the problem is that we can't define a trait for the type constructor Option, only for type Option<T> where T is a concrete type or a type parameterized in the implementation.

We're going to get around this with a collection of tricks using associated types. Our first issue is that we can't refer to the "type that a functor is holding" or "types which are the same up to what they're holding." We can get around this (in a circuitous way) by defining for every type a trait which keeps track of these things as associated types.

trait FunctorTypes {
    type Inner;
    type Outer<T>;
}

// Example for Option
impl<T> FunctorTypes for Option<T> {
    type Inner = T;
    type Outer<S> = Option<S>;
}

This is not terribly elegant, but its the kind of thing that could be automated with a macro. Inner will always match the type parameter of the functor and Outer will match the functor up to parameter. Note that we're using a fancy trick here: associated types can be generic.

We can then define our Functor trait in terms of these associated types:

trait Functor: FunctorTypes {
    fn fmap<T>(self, f: impl Fn(Self::Inner) -> T) -> Self::Outer<T>;
}

// Example for Option
impl<S> Functor for Option<S> {
    fn fmap<T>(self, f: impl Fn(S) -> T) -> Option<T> {
        match self {
            None => None,
            Some(x) => Some(f(x)),
        }
    }
}

The implementation is identical to the above standard library implementation (modulo the weaker assumption on the type of the closure) but the types in the trait itself are wonky. We're using the FunctorTypes trait to glean the information we can't get directly from the given types.

The tasks for this problem: Add a default implementation of the function funzip to Functor. This function should take a functor value with holding a pair and turn it into a pair of functor values. The Rust standard library has a hard-coded version for Option:

fn unzip(self) -> (Option<T>, Option<U>) {
      match self {
          Some((a, b)) => (Some(a), Some(b)),
          None => (None, None),
      }
}

A couple hints:

• Your implementation won't look like this, it will have to use fmap on self
• You will need to add a trait bound requiring that the underlying functor value is clonable (you'll see when you try to implement the function).
• You'll also have to include a trait bound letting the compiler know that the inner type of Self is a pair. Again, make sure to take a look at RPL on associated types to see how to specify an associated type.

Your implementation should be able to pass the following tests:

#[test]
fn option_fmap() {
    let expected = Some(100).fmap(|x| x + 1);
    assert_eq!(expected, Some(101));
}

#[test]
fn option_funzip() {
    let expected =  Some((vec![1, 2, 3], 4)).funzip();
    assert_eq!(expected.0, Some(vec![1, 2, 3]));
    assert_eq!(expected.1, Some(4))
}

#[test]
fn option_functor_none() {
    let none : Option<(i32, i32)> = None;
    assert_eq!(none.fmap(|p| p.0 + p.1), None);
    assert_eq!(none.funzip(), (None, None))
}

Things can get a lot more complicated once we start generalizing past functors.

An applicative functor is a functor together with a function pure that can "convert a thing into a held thing" and app which can "apply a held function to a held thing." This gives us the following trait:

trait Applicative: Functor {
    fn pure(x: Self::Inner) -> Self;
    fn app<T, U>(self, ax: Self::Outer<T>) -> Self::Outer<U> where
        T: Clone,
        Self::Inner: Fn(T) -> U;
}

Again, there's some weird stuff going on with the types. We have a trait bound which requires the inner type of Self to be a closure, so that self is a "thing holding a function" and the input is a "thing holding a T" written with Outer associated type.

The task for this problem: Implement the Applicative trait for Option, in analogy with the implementation of Functor.

• The pure function should take a value and wrap it in a Some constructor.
• The app function should apply the held function to the held value if both are not None.

Your implementation should pass the following tests:

#[test]
fn option_pure() {
    assert_eq!(Option::pure(vec![1, 2, 3]), Some(vec![1, 2, 3]))
}

#[test]
fn option_app() {
    let mut f = Some(|x| x + 1);
    assert_eq!(f.app(Some(10)), Some(11));
    assert_eq!(f.app(None), None);
    f = None;
    assert_eq!(f.app(Some(10)), None);
    assert_eq!(f.app(None), None);
}

Challenge (Optional): Give a default implementation of a method app2 which can be applied when the inner value is a Curried binary function, and which "runs" app twice. It should pass the following test:

#[test]
fn option_app2() {
    let f = Some(|x| move |y| x + y);
    assert_eq!(f.app2(Some(3), Some(4)), Some(7));
    assert_eq!(f.app2(Some(3), None), None);
    assert_eq!(f.app2(None, Some(3)), None);
    assert_eq!(f.app2(None, None), None);
}

Getting the trait bounds right for app2 is messy…

We can't define all these nice traits for vectors, but we can wrap vectors in a new structure:

#[derive(Clone, PartialEq, Debug)]
struct VVec<T>(Vec<T>);

You can call the struct whatever you want. You access the inner vector using tuple accessor notation:

let v = VVec(vec![1, 2, 3]);
assert_eq!(v.0[0], 1)

Working with these wrapped vectors requires some ugly boilerplate, but at least now we can implement traits for VVec<T>…

The task for this problem: Implement Semigroup, Monoid, Functor and Applicative for VVec.

Some hints:

• The concatenation operation on vectors is just vector concatenation.
• The mapping operation on vectors applies the given closure to every element of the vector.
• The pure operation creates a singleton.
• The app operation is a bit complicated: given a vector of closures and a vector of values, map each function onto the vector of values and concatenate the results.

Your implementation should pass the following tests:

#[test]
fn mconcat_semi() {
    let v1 = VVec(vec![1, 2, 3]);
    let v2 = VVec(vec![4, 5, 6]);
    let v3 = vec![v1, v2];
    let expected =<VVec<i32> as Semigroup<Add>>::mconcat(VVec(vec![0]), v3.into_iter());
    let actual = VVec(vec![0, 1, 2, 3, 4, 5, 6]);
    assert_eq!(expected, actual);
}

#[test]
fn mconcat_mon() {
    let v1 = VVec(vec![1, 2, 3]);
    let v2 = VVec(vec![4, 5, 6]);
    let v3 = vec![v1, v2];
    let expected =<VVec<i32> as Monoid<Add>>::mconcat(v3.into_iter());
    let actual = VVec(vec![1, 2, 3, 4, 5, 6]);
    assert_eq!(expected, actual);
}

#[test]
fn fmap_vvec() {
    let v = VVec(vec![1, 2, 3]);
    let expected = v.fmap(|x| x + 1);
    assert_eq!(expected, VVec(vec![2, 3, 4]))
}

#[test]
fn funzip_vvec() {
    let v = VVec(vec![(1, 2), (3, 4), (5, 6)]);
    let expected = v.funzip();
    let v1 = VVec(vec![1, 3, 5]);
    let v2 = VVec(vec![2, 4, 6]);
    assert_eq!(expected, (v1, v2))
}

#[test]
fn pure_vvec() {
    assert_eq!(VVec::pure(1), VVec(vec![1]));
}

#[test]
fn app_vvec() {
    let v1 = VVec(vec![|x| x + 1, |x| x + 2]);
    let v2 = VVec(vec![1, 3, 5]);
    assert_eq!(v1.app(v2).0, vec![2, 4, 6, 3, 5, 7])
}