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.

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 pass.

Part of this problem is reverse engineering (e.g., what kind of thing should Add be?) 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 monoid_tests {
    use super::*;

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

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

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

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

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

In addition implement, a function count_units which takes as input an iterator over values from a Monoid and returns a count of the number of unit elements. The challenge here will be correctly defining the trait bounds.

Your implementation should pass the following tests; note the ::<...> syntax.

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

    #[test]
    fn count_units_add_i32() {
        let expected = 3;
        let actual = count_units::<Add, _, _>(vec![1, 0, 1, 0, 0, 5, -1].into_iter());
        assert_eq!(expected, actual);
    }

    #[test]
    fn count_units_mul_i32() {
        let expected = 2;
        let actual = count_units::<Mul, _, _>(vec![1, 0, 1, 0, 0, 5, -1].into_iter());
        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 isn't terribly elegant, but its the kind of thing that could be automated. 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:

#[cfg(test)]
mod funzip_tests {
    use super::*;
    #[test]
    fn option_fmap() {
        let actual = Some(100).fmap(|x| x + 1);
        assert_eq!(Some(101), actual);
    }

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

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

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 the 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.

Finally, give a default implementation of a method app2 which can be applied when the inner value is a Curried binary closure, and which "runs" app twice. Getting the trait bounds right for app2 is a bit messy, let the compiler guide you…

Your implementation should pass the following tests:

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

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

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

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