Can I construct HashMap from Vector and modify while constructing with functional way?

Question

Here is the exercise on the exercism

I just wanted to learn functional way.

use std::collections::HashMap;

pub fn can_construct_note(magazine: &[&str], note: &[&str]) -> bool {
    let mut words: HashMap<&str, i32> = HashMap::new();

    magazine.iter().map(|&w|
        words.entry(w)
            .and_modify(|e| *e += 1)
            .or_insert(1)
    );

    println!("{:?}", words);

    false
}

But I got this weird error and googled but I can't solve.
I understand that it can't be done by this way.

I want to know the correct way to do this.
Thanks.

error: captured variable cannot escape `FnMut` closure body
  --> src/lib.rs:11:9
   |
8  |       let mut words: HashMap<&str, i32> = HashMap::new();
   |           --------- variable defined here
9  | 
10 |       let mut t = magazine.iter().map(|&w|
   |                                          - inferred to be a `FnMut` closure
11 |           words.entry(w)
   |           ^----
   |           |
   |  _________variable captured here
   | |
12 | |             .and_modify(|e| *e += 1)
13 | |             .or_insert(1)
   | |_________________________^ returns a reference to a captured variable which escapes the closure body
   |
   = note: `FnMut` closures only have access to their captured variables while they are executing...
   = note: ...therefore, they cannot allow references to captured variables to escape

error: aborting due to previous error

error: could not compile `magazine_cutout`

To learn more, run the command again with --verbose.

Answer 1

Functional programming is a way of approaching problems. It's not about syntax. Using map to modify an external mutable HashMap isn't functional programming. It's just an abuse of map (mapping should have no side-effects). There is nothing functional at all about for_each. It's just another syntax for for...in (and IMO an inferior syntax in most cases).

Broadly, functional programming avoids mutation, and thinking about problems recursively rather than by looping. Ömer Erden's solution is good in that it encapsulates the mutation inside the fold, but it's still basically a fancy loop. There's not a lot "functional" about that.

A functional way to think about this problem is recursively. Sort the words in both lists. Then the core mechanic is: Look at the first word in each list. If they match, recurse on the next word in each list. If they don't, recurse on the same goal list, and the next word on the source list. If the goal list is empty: success. If the source list is empty: fail. Notice that there was never a "count" step in there, and there's no HashMap. So I'm skipping your direct question and focusing on solving the full problem (since you said you wanted to explore functional approaches).

The first step towards that is to sort the words. There's no non-mutating sorted method in std, but there is one in IterTools. Still, I can make a simple (and extremely sloppy and special-case) one.

fn sorted<'a>(items: &[&'a str]) -> Vec<&'a str> {
    let mut v = Vec::from(items);
    v.sort();
    v
}

Note that this function is not internally "functional." But it provides a functional interface. This is very common in FP. Functional approaches are sometimes slower than imperative/mutating approaches. We can keep the value of FP while improving performance by encapsulating mutation.

But with that in place, I can build a fully functional solution. Notice the lack of any mut.

pub fn can_construct_note(magazine: &[&str], note: &[&str]) -> bool {

    // source and goal are sorted
    fn f(source: &[&str], goal: &[&str]) -> bool {

        // Split the source and goal into their heads and tails
        // Consider just the first elements.
        match (source.split_first(), goal.split_first()) {
            (_, None) => true,          // Can make nothing from anything

            (None, Some(_)) => false,   // Can't make something from nothing

            (Some((s, s_rest)), Some((g, g_rest))) => {
                match s.cmp(g) {
                    // If they match, then recurse on the tails
                    Ordering::Equal => f(s_rest, g_rest),

                    // If source < goal, they may match eventually, recurse with the next source element
                    Ordering::Less => f(s_rest, goal),

                    // If source > goal, it'll never work
                    Ordering::Greater => false,
                }
            }
        }
    }

    // Sort the initial lists
    let source = sorted(magazine);
    let goal = sorted(note);

    // And kick it off and return its result
    f(&source[..], &goal[..])
}

This is a very functional way to solve the problem, to the point of being a text-book example. But notice there's not a single map, reduce, fold, or filter anywhere. Those are really important tools in functional programming, but they're not what it means to be functional.

It's not really great Rust. If these lists are very long, then this will likely crash the stack because Rust does not have tail-call optimization (which is a critical optimization for recursion to be really workable).

Recursion can always be turned into a loop, however. So at the cost of a small amount of visible mutation, this can be rewritten. Rather than recursively calling f(...), this changes source and goal and loops.

pub fn can_construct_note(magazine: &[&str], note: &[&str]) -> bool {
    let mut source = &sorted(magazine)[..];
    let mut goal = &sorted(note)[..];

    // source and goal are sorted
    loop {
        // Split the source and goal into their heads and tails
        match (source.split_first(), goal.split_first()) {
            (_, None) => return true,          // Can make nothing from anything

            (None, Some(_)) => return false,   // Can't make something from nothing

            (Some((s, s_rest)), Some((g, g_rest))) => {
                match s.cmp(g) {
                    // If they match, then recurse on the tails
                    Ordering::Equal => {
                        source = s_rest;
                        goal = g_rest;
                        continue;
                    }

                    // If source < goal, they may match eventually, recurse with the next source element
                    Ordering::Less => {
                        source = s_rest;
                        continue;
                    }

                    // If source > goal, it'll never work
                    Ordering::Greater => return false,
                }
            }
        }
    }
}

---

To Ömer's comments below, this is how you would create the HashMap itself in a functional way. This requires +nightly for the GroupBy.

#![feature(slice_group_by)]
use std::iter::FromIterator;

fn word_count<'a>(strings: &[&'a str]) -> HashMap<&'a str, usize> {
    let sorted_strings = sorted(strings);
    let groups = sorted_strings
        .group_by(|a, b| a == b)
        .map(|g| (g[0], g.len()));
    HashMap::from_iter(groups)
}

I'm not worried about careful lifetime management here. I'm just focused on how to think in FP. This approach sorts the strings, then groups the strings by equality, and then maps those groups into a tuple of "the string" and "the number of copies." That list of tuples is then turned into a HashMap. There's no need for any mutable variables.

Answer 2

If you want really functional way you should do this:

use std::collections::HashMap;
fn main() {
    let s = "aasasdasdasdasdasdasdasdfesrewr";
    let map = s.chars().fold(HashMap::new(), |mut acc, c| {
        acc.entry(c).and_modify(|x| *x += 1).or_insert(1i32);
        acc
    });
    println!("{:?}", map);
}

Answer 3

One problem with your code is that Iterator::map() is lazy and converts the iterator to another iterator without actually iterating over either. Because of that ending the expression with map() is not very useful, you need to do something that will exhaust the iterator. If you want to do it the functional way, you probably want for_each().

The other problem is that Entry::or_insert() returns a mutable reference to the inserted/retrieved value. This is normally used to chain operations that modify the value, such as or_insert(vec![]).push(item). Your closure doesn't end with ;, so its return value is the reference returned by or_insert(). Rust interprets such map() invocation as intending to transform the iterator over words to an iterator over mutable references to their counts. You would then be free to do whatever you want with those references, perhaps collect them in a vector. This is of course a big problem, as you're not allowed to have more than one mutable reference to anything inside the hashmap at once. This is why the borrow checker complains of the reference leaking out of the closure. To fix this, just add the braces and use a ;, so the closure returns () (which is incidentally the only valid return type of for_each()).

This compiles:

use std::collections::HashMap;

pub fn can_construct_note(magazine: &[&str], note: &[&str]) -> bool {
    let mut words: HashMap<&str, i32> = HashMap::new();

    magazine.iter().for_each(|&w| {
        words.entry(w).and_modify(|e| *e += 1).or_insert(1);
    });

    println!("{:?}", words);

    false
}

Playground

As others pointed out in the comments, an even more functional approach would be to use Iterator::fold(), which wouldn't require a mutating capture of the hashmap.