What is the most elegant way to transform a list of 3-tuples (Iterator<Item = (K0, K1, V)>) into a map of maps (HashMap<K0, HashMap<K1, V>>)?

[KSXGitHub]

fn transform<K0, K1, V, I>(input: I) -> HashMap<K0, HashMap<K1, V>>
where
  K0: Hash + Eq,
  K1: Hash + Eq,
  I: IntoIterator<Item = (K0, K1, V)>,
{
  // what is the most elegant (preferably functional) way to do this?
}

---

The question is also posted on StackOverflow

[Hyeonu]

fn transform<K0, K1, V, I>(input: I) -> HashMap<K0, HashMap<K1, V>>
where
  K0: Hash + Eq,
  K1: Hash + Eq,
  I: IntoIterator<Item = (K0, K1, V)>,
{
    let mut m: HashMap<_, HashMap<_, _>> = HashMap::new();
    for (k0, k1, v) in input {
        m.entry(k0).or_default().insert(k1, v);
    }
    m
}

Edit: specified the type of the m

[SDX]

If you want to make it even more functional:

use std::hash::Hash;
use std::collections::HashMap;
fn transform<K0, K1, V, I>(input: I) -> HashMap<K0, HashMap<K1, V>>
where
  K0: Hash + Eq,
  K1: Hash + Eq,
  I: IntoIterator<Item = (K0, K1, V)>,
{
  input.into_iter()
    .fold(HashMap::new(), |mut a, x| {
      a.entry(x.0).or_default().insert(x.1, x.2); a
    })
}

[KSXGitHub]

The solutions are quite elegant, but still not functional enough (as compare to, say, Haskell). Is there any method in the itertools crate that might help?

[KSXGitHub]

Your answer need a little edit since it does not work on the playground, according to one feedback from StackOverflow.

[Hyeonu]

I checked the SO answer and compile it om the playground. The V: Default is irrelevant as you don't need to construct its value out of the thin air. What you need is to add some type annotation to the variable m.

let mut m: HashMap<_, HashMap<_, _>> = HashMap::new();

[steffahn]

@KSXGitHub

The solutions are quite elegant, but still not functional enough (as compare to, say, Haskell).

Well, we can compare to Haskell if you like. The “equivalent” of

fn transform<K0, K1, V, I>(input: I) -> HashMap<K0, HashMap<K1, V>>
where
  K0: Hash + Eq,
  K1: Hash + Eq,
  I: IntoIterator<Item = (K0, K1, V)>,

would be either

transform :: (Ord k1, Ord k2) => [(k1, k2, v)] -> Map k1 (Map k2 v)

or

transform :: (Foldable f, Ord k1, Ord k2) => f (k1, k2, v) -> Map k1 (Map k2 v)

Since Haskell doesn’t have mutable references, functions such insert, do fn(T, …) -> T instead of fn(&mut T, …), so you have that small advantage that that already fits better with what fold expects. Also for the same reason, Haskell doesn’t have an entry-API, the closest thing is probably alter.

In Rust-terms, alter is something like

fn alter<K: Hash + Eq, V>(m: HashMap<K, V>, k: K, f: impl FnOnce(Option<V>) -> Option<V>) -> HashMap<K, V> { … }

(which is actually hard to implement properly/efficiently in Rust)
Edit: ah, it can work with API only present in hashbrown.

If I also give myself a non-method and &mut-free insert function

fn insert<K: Hash + Eq, V>(mut m: HashMap<K, V>, k: K, v: V) -> HashMap<K, V> { … }

then I can sketch a Haskell solution in Rust already

fn transform<K0, K1, V, I>(input: I) -> HashMap<K0, HashMap<K1, V>>
where
    K0: Hash + Eq,
    K1: Hash + Eq,
    I: IntoIterator<Item = (K0, K1, V)>,
{
    input.into_iter().fold(HashMap::new(), |m, (x, y, z)| {
        alter(m, x, |v| Some(insert(v.unwrap_or_else(HashMap::new), y, z)))
    })
}

(playground)

In Haskell, the order of arguments for alter/insert is different, and Option/Some/None are called Maybe/Just/Nothing, and we can use partial application / eta-reduction, as well as function composition (‘.’); here’s the code

import qualified Data.Map as M
import Data.Map (Map)
import Data.Foldable
import Data.Maybe

transform :: (Foldable f, Ord k1, Ord k2) => f (k1, k2, v) -> Map k1 (Map k2 v)
transform = foldl'
  (\m (x, y, z) -> M.alter (Just . M.insert y z . fromMaybe M.empty) x m)
  M.empty

Another approach I could come up with is to always create new (singleton) maps and them combine them with union

transform :: (Ord a, Ord b) => [(a, b, c)] -> Map a (Map b c)
transform = M.fromListWith M.union . map (\(x, y, z) -> (x, M.singleton y z))

or, if you want to keep the polymorphic type

transform :: (Foldable f, Ord a, Ord b) => f (a, b, c) -> Map a (Map b c)
transform = M.fromListWith M.union . map (\(x, y, z) -> (x, M.singleton y z)) . toList

In Rust, there’s no equivalent for fromListWith AFAICT; and also people wouldn’t like the creation of all those singleton HashMaps.

In any case, I don’t see much that’s significantly “more elegant” in these approaches in Haskell, compared to the Rust solutions already presented above. The “elegance” of “functional” approaches aside, the

let mut m = HashMap::new();
for (k0, k1, v) in input {
    m.entry(k0).or_default().insert(k1, v);
}
m

solution is probably still the one with highest clarity.

[erelde]

If your access pattern is so that you will always have k0 and k1 simultaneously, you could use the type HashMap<(K0, K1), V> rather. That would reduce indirection a bit.

input.into_iter()
    .map(|(k0, k1, value)| ((k0, k1), value))
    .collect()

Of course, if this doesn't match your access pattern, disregard entirely. For example if you wanted to iterate on all matches of a given k0 that wouldn't work.