Understanding where clauses and trait constraints

Lately I've been working on a crate functils to make Rust a little more
functional and it's based off Stephen Diehl's
Protolude crate. It has some very
sensible defaults for Haskell after turning off the implicit Prelude
that I enjoy using in my Haskell code. It includes some cool functions
like the identity function:

-- Given a type a return itself
id :: a -> a
id x = x

I implemented that in Rust no problem with generics!

pub fn identity<A>(x:A) -> A {

Well how about this function uncons from protolude? If you know Scheme
or LISP it's the opposite of cons, as I just found out in class today.
Well it's pretty easy in Haskell!

-- Given a list of a return a tuple of the first item of the list and
-- the rest of the list if it exists. Otherwise return Nothing.
uncons :: [a] -> Maybe (a, [a])
-- Pattern matching on an empty list means we return nothing
uncons []     = Nothing
-- x is the head and xs is the rest of the list
uncons (x:xs) = Just (x, xs)

For those unfamiliar with Haskell, Maybe is equivalent to Option in
Rust. Just == Some and Nothing == None. If this is anything like
identity then it should be a breeze to implement in Rust right? Nope.
I was wrong.

Iterating from 0

Here was my first wack at the code, a direct port of Haskell's code to

fn uncons<A>(x: [A]) -> Option<(A,[A])> {
    match x.length {
        0 => None,
        1 => Some((x[0], [])),
        _ => Some((x[0], x[1..(x.length - 1)])),

If you've done generics with slices before or with slices with non
deterministic sizes you know what's going to happen. If you don't here's
the error message:

error: aborting due to 2 previous errors
error: the trait bound `[A]: std::marker::Sized` is not satisfied [--explain E0277]
 --> example.rs:5:1
5 |> fn uncons<A>(x: [A]) -> Option<(A,[A])> {
  |> ^
note: `[A]` does not have a constant size known at compile-time
note: required because it appears within the type `(A, [A])`
note: required by `std::option::Option`

What does this mean? Well slices need to know the size of their elements
and using generics won't let it know how much space to allocate. We could add
a Sized constraint but what if I want to use this on list like things like
Vec or HashSet? This implementation won't do anyways for them. Well what's
one thing that they have in common? Iterators! Let's use them to implement this
function. Here's the first pass I made at the code:

// This isn't implicitly imported so we need to do so ourselves
use std::iter::FromIterator;

// We need B because it won't be something to iterate over but
// an item inside of A
pub fn uncons<A: IntoIterator + FromIterator<A>, B>(x: A) -> Option<(B,A)> {
    // Let's turn our input into an iterator to use!
    let mut iter = x.into_iter();
    // If it has a value let's get it and store it inside of one
    if let Some(one) = iter.next() {
        // We have a value. Wrap the tuple inside Some and use the
        // collect() function to turn it back into the collection
        // without the first value
        Some((one, iter.collect()))
    } else {
        // There's nothing in the iterator! We have an 'empty list'
        // therefore we need to return None.

This should work. This is perfect code. Nothing should go wrong. Oh boy
did it go wrong.

error: aborting due to previous error
error: mismatched types [--explain E0308]
  --> example.rs:16:15
16 |>         Some((one, iter.collect()))
   |>               ^^^ expected type parameter, found associated type
note: expected type `B`
note:    found type `<A as std::iter::IntoIterator>::Item`

error: the trait bound `A: std::iter::FromIterator<<A as std::iter::IntoIterator>::Item>` is not satisfied [--explain E0277]
  --> example.rs:16:25
16 |>         Some((one, iter.collect()))
   |>                         ^^^^^^^
help: consider adding a `where A: std::iter::FromIterator<<A as std::iter::IntoIterator>::Item>` bound

Uhhhhhhhhhhh what? The trait bound whatsit isn't satisfied? Add a where clause?
This is where I realized I had gone into new territory with Rust that I had not
understood yet. I was lost so I did what the compiler said to do. Let's add this where
to the example then.

use std::iter::FromIterator;
pub fn uncons<A: IntoIterator + FromIterator<A>, B>(x: A) -> Option<(B,A)>
  where A: FromIterator<<A as IntoIterator>::Item> {
    let mut iter = x.into_iter();
    if let Some(one) = iter.next() {
        Some((one, iter.collect()))
    } else {

Okay so this didn't solve our problem. We get this error again instead:

error: mismatched types [--explain E0308]
  --> example.rs:11:15
11 |>         Some((one, iter.collect()))
   |>               ^^^ expected type parameter, found associated type
note: expected type `B`
note:    found type `<A as std::iter::IntoIterator>::Item`

error: aborting due to previous error

Let's back it up a bit. What exactly are we trying to tell the compiler?
A is a collection of some sort that can turn into and out of an iterator
and B is the item stored inside of A! If we look at the found type the
compiler is telling us it has this Item type but it doesn't know what to
do with it. We need to tell the compiler that this Item type is actually
B! How though? How? With a where clause actually!

From confusion to understanding. Implementing the where clause.

Let's look at the where clause. where is used to add constraints to
generic types (like we had been doing) and giving the compiler the
information it needs to solve things! Here's what our final version
should look like and what I came to after a lot of work:

use std::iter::FromIterator;
pub fn uncons<A, B>(x: A) -> Option<(B,A)>
    where A: IntoIterator<Item = B> + FromIterator<B> {
    let mut iter = x.into_iter();
    if let Some(one) = iter.next() {
        Some((one, iter.collect()))
    } else {

No errors at all! Alright, lets take a look at the function definition
to see what's going on.

pub fn uncons<A,B>(x: A) -> Option<(B,A)>

This is pretty standard and looks more like what we've done before.
uncons takes an A type called x and turns it into an Option<(B,A)>. Awesome,
so let's look at this where clause because we haven't seen it look like
this before.

where A: IntoIterator<Item = B> + FromIterator<B>

A is constrained with the traits IntoIterator and FromIterator. This is
nothing new but the stuff in the angle brackets is. Look at
IntoIterator. We are saying that the Items inside of it are of the type
B! This means if I did this with Vec<String> then A is Vec and B is
String. The compiler now understands that if A is being
iterated over, then the type inside of it is B for this function! In the
FromIterator we're doing a similar thing but saying that the inner
type implementing it is of type B. In this case it's basically saying
A<B>: FromIterator if that form makes more sense to you (but is
incorrect Rust). This then compiles and if you test it out works exactly as
you would expect!

If you don't believe me you can try this example to see it does:

let empty: Vec<i32> = vec![];
let vec1 = vec![1,2,3];
let vec2 = vec![2,3];
assert_eq!(uncons(empty), None)

So what does where do?

where allows us to define constraints for the types given as generics
and provide more information to the compiler. It allows us to make the
signature of the function look a little neater as well. Rather than

pub fn example<A: Ord + Eq + PartialEq + PartialOrd, B: Iterator>(x: A, y: B) -> bool {

We can put:

pub fn example<A,B>(x: A, y: B) -> bool
  where A: Ord + Eq + PartialEq + PartialOrd
      , B: Iterator

This is a little more compact in my opinion and easier to read like
a list. My final form of the uncons function actually does work with the
inline notation. It just was really long and not as easy to read.

To answer the question: where is syntactic sugar for the inline form
of adding constraints to generics that is easier to read.

Wait what you say?! You said you solved it with a where clause but
it's really just sugar, not an actual solution. Well I did,
sort of. While it turns out to be unnecessary since where is
syntactic sugar it did lead me in the right direction of thinking about
how to solve the problem, mainly what am I trying to tell the compiler?
How do I tell the compiler B is inside of A?


I've walked you through the problems I had while working with traits and
implementing something new and solving it using where and better trait
constraints. I struggled for quite some time before figuring this out because
the documentation was sparse on constraints and the error messages were helpful but
not in the way I thought they'd be and it took a while to reason through them.

I'd love to hear your feedback and corrections if you have any!