# 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>>)?

``````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

``````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`

5 Likes

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
})
}
``````
2 Likes

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?

Your answer need a little edit since it does not work on the playground, according to one feedback from StackOverflow. 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();
``````
2 Likes

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> { … }
``````

``````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)))
})
}
``````

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 `HashMap`s.

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.

3 Likes

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.

1 Like

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.