Type Signature of Function passed to Fold, Reference or Value

help
1

STRING:

use std::collections::HashMap;

pub fn foo(strs: Vec<String>) -> i32 {
    let (roots, ranks) : (HashMap<&String,&String>, HashMap<&String,i32>) = strs.iter().fold(
        (HashMap::new(), HashMap::new()),
        |(mut roots, mut ranks), s| {
            roots.insert(s,s);
            ranks.insert(s,1);
            (roots, ranks)
                
        }
    );
    0
}

(Playground)

GENERIC:

use std::collections::HashMap;
use std::slice::Iter;

//This is forcing me to learn rust's generics and fight with lifespans
struct UnionFind<T> {
    roots: HashMap<T, T>,
    ranks: HashMap<T, usize>,
    len: usize 
}
impl<T: std::cmp::Eq + std::hash::Hash + Copy> UnionFind<T> {
    //Constructors
    pub fn from_iter( v: Iter<T>) -> Self {
        let ( roots, ranks ): (HashMap::<T,T>, HashMap::<T,usize>) = v.fold(
            (HashMap::new(), HashMap::new()),
            |(mut roots, mut ranks), **&**t| {
                roots.insert(t,t);
                ranks.insert(t,1 as usize);
                (roots,ranks)
            }
        );
        UnionFind {
            len: roots.len(),
            roots: roots,
            ranks: ranks,
        }
    }
}

(Playground

Hi,

I'm looking for some clarification on what appears to be inconsistent behavior with the accumulator function provided to a fold call, though I'm sure its my lack of understanding.

When calling fold on a Iterator of &String (see the first example above), it appears that the accumulator function provided to the fold call also takes the type &String, indicating that the value is passed to the accumulator function. This is what I expected.

My confusion occurs when I try to abstract out the fold call via generics. In this example (see the second example above) the only way I can get my code to compile is if I dereference the generic type T, indicating that &T is the type that is provided to the accumulator function provided to my fold call.

All in all, its not that big of a deal (I can get it to compile with one extra character), but it does indicate that I'm not understanding something that seems pretty fundamental. If someone could help me out and explain why the string call to fold does not act as a reference (ie &&String) but the generic does (ie &T) it would be greatly appreciated.

Thanks!

2

First, do this:

#![deny(elided_lifetimes_in_paths)]

This will force you to annotate places where lifetimes appear that would otherwise be invisible:

error: hidden lifetime parameters in types are deprecated
  --> src/lib.rs:14:30
   |
14 |     pub fn from_iter( v: Iter<T>) -> Self {
   |                          ----^-- expected lifetime parameter

Here's the signature after fixing the error:

    pub fn from_iter( v: Iter<'_, T>) -> Self {

Now it's more clear that there's some sort of borrowing going on with Iter. Let's take a look at its Iterator implementation:

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    // ...
}

The Items of Iter<'_, T> are &T, and fold takes Iter::Item, so in your function fold is taking &Ts.

In case it was part of your confusion: generics and associated types like Iterator::Item can resolve to references. See misconception #1 here.

3

Appreciate the help. I have a followup if you don't mind.

If that were the case, then why does the code below resolve to String and not &String for s? Similarly, wouldn't all iterators give references to their items and not the items themselves? Is there some sort of dereference when next is called?

strs.into_iter().fold(
    (HashMap::new(), HashMap::new()),
    |(mut roots, mut ranks), s| {
        roots.insert(s,s);
        ranks.insert(s,1);
        (roots, ranks)

I feel like I'm pretty solid on T being a reference, what I'm confused about is how I can access T(a reference) directly without accessing a reference to the reference.

4

It resolves to &String. You're creating HashMaps with &String as keys.

    let (roots, ranks) : (HashMap<&String,&String>, HashMap<&String,i32>) = strs.iter().fold(
1 Like
5

I linked to a playground below and it looks like they resolve to String. Is there something else going on?

[Rust Playground]

6

You've changed the code from the OP. Calling into_iter is not the same thing as calling iter. You have a different type of iterator where Item = String now.

7

Sorry, didnt mean to be sneaky about it.

That's my confusion though. Why in both of these examples when Item = String or Item = &String does the fold accumulator function take what Item is, but when Item = T, the accumulator function takes &T instead of T?

8

It always takes whatever the item is.

Are you still talking about this playground? Item = &T there. Here's a way to check that:

        // Deliberately assign the wrong type to get the
        // compiler to tell us what the actual type is
        let _: <Iter<T> as Iterator>::Item = ();

error[E0308]: mismatched types
  --> src/lib.rs:13:46
   |
13 |         let _: <Iter<T> as Iterator>::Item = ();
   |                ---------------------------   ^^ expected `&T`, found `()`
   |                |
   |                expected due to this
   |
   = note: expected reference `&T`
              found unit type `()`

Or see the documentation from earlier.

9

Maybe I'm asking the wrong question then. If Iter makes Item=&T then how do I declare a function with a iterator with Item=T in its type signature?

10

Ah yes, I think we probably have been talking about the wrong thing.

Instead of taking a specific iterator type...

    //                  vvvvvvv
    pub fn from_iter(v: Iter<T>) -> Self

Take any iterator over the items you want:

    //               vvvvvvvvvvvvvvvvvvvvv
    pub fn from_iter<I: Iterator<Item = T>>(v: I) -> Self { ... }

    // Same thing, written differently
    pub fn from_iter<I>(v: I) -> Self
    where
        I: Iterator<Item = T>,
    {
        ...
    }

Or to be even more flexible, use IntoIterator instead...

    pub fn from_iter<I>(v: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let v = v.into_iter();
        // ...
    }

...at which point you're recreating the FromIterator trait. So ultimately I would suggest implementing that trait:

impl<I> FromIterator<I> for UnionFind<I>
where
    I: Hash + Eq + Clone,
{
    fn from_iter<T: IntoIterator<Item = I>>(iter: T) -> Self {
        let iter = iter.into_iter();
        let (roots, ranks): (HashMap<I, I>, HashMap<I, usize>) = iter.fold(
            (HashMap::new(), HashMap::new()),
            |(mut roots, mut ranks), item| {
                roots.insert(item.clone(), item.clone());
                ranks.insert(item, 1 as usize);
                (roots, ranks)
            },
        );
        UnionFind {
            len: roots.len(),
            roots: roots,
            ranks: ranks,
        }
    }
}
4 Likes
11

This does it.

Huge thank you for both your knowledge and patience. It is very much helpful and appreciated.

12

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.