Invert object using only pure functions

Question

Assume you have an object like this:

{
  a: [1,2,3],
  b: [2],
  c: [1,4]
}

and you need to convert it to:

{
  1: ['a', 'c'],
  2: ['a', 'b'],
  3: ['a'],
  4: ['c']
}

It's simple to do this using imperative way and mutable data structures:

function convert (obj) {
  var key, values
    , result = {};

  for (key in obj) {
    values = obj[key];
    values.forEach(function (value) {
      result[value] = result[value] || []; // bad — mutability :(
      result[value].push(key); // bad — mutability :(
    });
  }

  return result;
}

But is there any way of doing this by using only pure functions and without using any assignments? Usage of some library for functional programming is allowed.

Answer 1

well, its a pure data transformation, so you can definitely do it without using mutable variables. Let's do it in Haskell, which gives us a static guarantee that there is no explicit mutation. We start with an example:

d :: [(Char, [Integer])]
d = [('a', [1,2,3]), ('b', [2]), ('c', [1,4])]

Ok, so what are the keys of the new structure? They're the unique elements of the first structure:

> import Data.List
> let keys = sort . nub . concatMap snd $ d
[1,2,3,4]

and then we need to know in which column each value appeared. So pair each value with its key:

> let pairs = concatMap (\(k,v) -> map (,k) v) d
[(1,'a'),(2,'a'),(3,'a'),(2,'b'),(1,'c'),(4,'c')]

Now we can build the result:

 > [ (k, map snd . filter ((== k) . fst) $ pairs ) | k <- keys ]
 [(1,"ac"),(2,"ab"),(3,"a"),(4,"c")]

In its full glory:

{-# LANGUAGE TupleSections #-}

import Data.List

rotate d = [ (k, map snd . filter ((== k) . fst) $ pairs ) | k <- keys ]
    where
        keys  = sort . nub . concatMap snd $ d
        pairs = concatMap (\(k,v) -> map (,k) v) d

E.g.

*A> rotate [('a', [1,2,3]), ('b', [2]), ('c', [1,4])]
[(1,"ac"),(2,"ab"),(3,"a"),(4,"c")]

Or a point-free version with no named intermediate structures:

rotate2  = map (\x -> (head (map fst x), map snd x))
         . groupBy ((==) `on` fst)
         . sortBy (comparing fst)
         . concatMap (\(k,v) -> map (,k) v)

Good little interview question :)