Verbose lifetime annotation in "too many linked list"

I am going over the great write up by @Gankra to mainly learn Box, Rc and Arc concepts.

In his third iteration of linked list: Persistent Stack, I was trying to understand the type of variables that is being passed around closures so I tried to annotate their arguments.

Particularly the head() function in that chapter reads:

pub fn head(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem )
}

If I try to explicitly annotate the arg of map method like so:

pub fn head(&self) -> Option<&T> {
    self.head.as_ref().map(|node: &Rc<Node<T>>| &node.elem)
}

on top of getting cannot infer appropriate lifetime error, I would get this interesting bit:
expected std::option::Option<&T>, found std::option::Option<&T> !!!

I naively tried to solve the issue by adding lifetime parameters like this which didn't help:

pub fn head<'a, 'b>(&'a self) -> Option<&'b T> {
    self.head.as_ref().map(|node: &'b Rc<Node<T>>| &node.elem)
}

So my question is what is the correct way of annotating that function with lifetimes?
I am hoping I can better understand the relationship between self's lifetime and head()'s return lifetime

pub fn head<'a>(&'a self) -> Option<&'a T> {
    self.head.as_ref().map(|node: &'a Rc<Node<T>>| &node.elem)
}

The lifetime of the returned value from the function must have the same or shorter lifetime as the inputted list, otherwise there wouldn't be a guarantee that the list would outlive the reference that head generates, so the return type lifetime must be outlived by the parameter lifetime. The lifetime that the closure must return must have the same lifetime as the return time ('a), so the parameter that the closure takes must have an equal or longer lifetime, so you just give it 'a there as well.

This also works:

pub fn head<'a: 'b, 'b>(&'a self) -> Option<&'b T> {
    self.head.as_ref().map(|node: &'b Rc<Node<T>>| &node.elem)
}

because 'a: 'b tells the compiler than 'a will outlive 'b, so it can then properly deduce that the returned reference will not outlive 'a. You could even do this:

pub fn head<'a: 'b, 'b: 'c, 'c>(&'a self) -> Option<&'c T> {
    self.head.as_ref().map(|node: &'b Rc<Node<T>>| &node.elem)
}

because each lifetime is guaranteed to be equal or shorter than the previous one. However, the first one is the recommended approach because it's much easier to read and understand than these two

1 Like