What's the functional programming / Linq form of this? | Tech Off

eddwo
Wheres my head at?

I seem to be forever coming across the following situation.

I have a set of key-value mapping of type List<KeyValuePair<K,V>>

eg: { a -> 5, b-> 7, c -> 12, d -> 7, e -> 5, f -> 12, g -> 9 }

which I then need to invert so that I can retrieve the set of unique values with their associated keys.

List<KeyValuePair<V,List<K>>

eg: { 5 -> {a,e}, 7 -> {b,d}, 9 -> {g}, 12 -> {c,f} }

(sort order of result is unimportant, just shown sorted for readability)

With C# 2.0 I'll usually have something like

//where Type V implements IComparable
SortedList<V,List<K>> Invert(List<KeyValuePair<K,V>> list)
{
   SortedList<V,List<K>> output = new SortedList<V,List<K>>;
   foreach(KeyValuePair<K,V> pair in list)
   {
      if (!output.ContainsKey(pair.Value))
      {
         List<K> keyset = new List<K>();
         set.Add(pair.Key);
         output.Add(pair.Value,keyset);
      }
      else
      {
           output[pair.Value].Add(pair.Key);
      }
   }
   return output;
}

I'm sure  there must be a much better a way of expressing this transformation in Linq or in other functional programming languages as a simple expression with a lambda for supplying the value equality comparison function.

I don't know what its called or how to go looking for it, but it must be a pretty common operation for other people in all sorts of situations, and something that would probably be fairly parallelizable.

figuerres
???

eddwo wrote:

I seem to be forever coming across the following situation.

I have a set of key-value mapping of type List<KeyValuePair<K,V>>

eg: { a -> 5, b-> 7, c -> 12, d -> 7, e -> 5, f -> 12, g -> 9 }

which I then need to invert so that I can retrieve the set of unique values with their associated keys.

List<KeyValuePair<V,List<K>>

eg: { 5 -> {a,e}, 7 -> {b,d}, 9 -> {g}, 12 -> {c,f} }

(sort order of result is unimportant, just shown sorted for readability)

With C# 2.0 I'll usually have something like

//where Type V implements IComparable
SortedList<V,List<K>>> Invert(List<KeyValuePair<K,V>> list)
{
   SortedList<V,List<K>> output = new SortedList<V,List<K>>;
   foreach(KeyValuePair<K,V> pair in list)
   {
      if (!output.ContainsKey(pair.Value))
      {
         List<K> set = new List<K>();
         set.Add(pair.Key);
         output.Add(pair.Value,set);
      }
      else
      {
           output[pair.Value].Add(pair.Key);
      }
   }
   return output;
}

I'm sure  there must be a much better a way of expressing this transformation in Linq or in other functional programming languages as a simple expression with a lambda for supplying the value equality comparison function.

I don't know what its called or how to go looking for it, but it must be a pretty common operation for other people in all sorts of situations, and something that would probably be fairly parallelisable.

I do not have a nice code sample but to start with in linq:

your "list" can be used in a query as it it was a sql table, so you can
do
from ____
Where _____
select ____

that will handle the main for loop for you.
linq has grouping and the select can allow a new() that can return a new "shape" of data.
in linq you can say something like:
new { a = foo.y, b = foo.bar, c = foo.duh }
and if you started with
var subset = from ....
then you can do stuff like:

foreach ( var item in subset )
{
}

or whatever ...

the var [name] behaves like a list / collection and has a .tolist() method.

look at the blogs by scott gu for more info:
http://weblogs.asp.net/scottgu/archive/2007/09/07/linq-to-sql-part-9-using-a-custom-linq-expression-with-the-lt-asp-linqdatasource-gt-control.aspx

while his set is on dlinq it's almost all the same stuff...

just think in terms of set operations, try to let linq do the for loops.

I hope that helps you get started...

odujosh
Need Microsoft SUX now!

eddwo wrote:

I seem to be forever coming across the following situation.

I have a set of key-value mapping of type List<KeyValuePair<K,V>>

eg: { a -> 5, b-> 7, c -> 12, d -> 7, e -> 5, f -> 12, g -> 9 }

which I then need to invert so that I can retrieve the set of unique values with their associated keys.

List<KeyValuePair<V,List<K>>

eg: { 5 -> {a,e}, 7 -> {b,d}, 9 -> {g}, 12 -> {c,f} }

(sort order of result is unimportant, just shown sorted for readability)

With C# 2.0 I'll usually have something like

//where Type V implements IComparable
SortedList<V,List<K>>> Invert(List<KeyValuePair<K,V>> list)
{
   SortedList<V,List<K>> output = new SortedList<V,List<K>>;
   foreach(KeyValuePair<K,V> pair in list)
   {
      if (!output.ContainsKey(pair.Value))
      {
         List<K> set = new List<K>();
         set.Add(pair.Key);
         output.Add(pair.Value,set);
      }
      else
      {
           output[pair.Value].Add(pair.Key);
      }
   }
   return output;
}

I'm sure  there must be a much better a way of expressing this transformation in Linq or in other functional programming languages as a simple expression with a lambda for supplying the value equality comparison function.

I don't know what its called or how to go looking for it, but it must be a pretty common operation for other people in all sorts of situations, and something that would probably be fairly parallelisable.

Query and function call:
var Q = (from pair in list
where !output.ContainsKey( pair.Key)
select pair).Distinct();

-OR-

var Q =
list
.Where(pair => !output.ContainsKey( pair.Key))
.Distinct();

Both produce the same result. Second is more explicit. You are passing your predicate (your where statement) as a lambda expression.

Read as given a pair item which is implicitly type give me only ones that the output does not yet contain. A predicate is function that takes some parameters and gives you back bool.

eddwo
Wheres my head at?

Wow, I'd never have believed the answer could be so simple!

class Pair<K, V>
{
   public K Key { get; set; }
   public V Value { get; set; }
}



var data = new List<Pair<string,int>> { new Pair<string,int> { Key = "a", Value= 5},
                                        new Pair<string,int> { Key = "b", Value= 7},
                                        new Pair<string,int> { Key = "c", Value= 12},
                                        new Pair<string,int> { Key = "d", Value= 7},
                                        new Pair<string,int> { Key = "e", Value= 5},
                                        new Pair<string,int> { Key = "f", Value= 12},
                                        new Pair<string,int> { Key = "g", Value= 9} };

var invert = data.GroupBy(v => v.Value, k => k.Key);

//The first lambda extracts keys from the input values,
//The second extracts values from the input keys,
//and it uses the default equality comparer unless you specify one as another lambda in an overload.

amotif
No Silver Bullet

Here's an alternative for deriving invert:

    var invert = from pair in data
                 group pair by pair.Value;

Anyone know how to format this to "5=>a,e" etc. in a linq-esque fashion?

amotif
No Silver Bullet

amotif wrote:

Anyone know how to format this to "5=>a,e" etc. in a linq-esque fashion?

Okay, I think I've settled on this:

    var result = from pair in data
                 group pair by pair.Value into g
                 select g.FormatReverseMapping();

    foreach (string s in result)
        Console.WriteLine(s);

with an extension method:

    internal static string FormatReverseMapping(this IGrouping> grouping)
    {
        StringBuilder buffer = new StringBuilder();

        buffer.Append(grouping.Key);
        buffer.Append("=>");
        foreach (var x in grouping)
            buffer.Append(x.Key);

        return buffer.ToString();
    }

(psst-- take a look at Systems.Collections.Generic.KeyValuePair.)

eddwo
Wheres my head at?

To format the output what I did was this:

static void Dump<K,V> (IEnumerable<IGrouping<V,K>> output )
{
   foreach (var group in output)
   {
      var keystr = string.Join(", ",group.Select(s => s.ToString()).ToArray());
      Console.WriteLine(string.format("{0} -> {{{1}}}",group.Key,keystr));
   }
}

Which worked fairly well.

Yes I know about KeyValuePair<K,V>, I just invented Pair<K,V> coz I wanted to try out the object initialiser syntax, and KeyValuePair's Key is readonly.

odujosh
Need Microsoft SUX now!

amotif wrote:
Here's an alternative for deriving invert:
    var invert = from pair in data
                 group pair by pair.Value;
Anyone know how to format this to "5=>a,e" etc. in a linq-esque fashion?

var

invert = data.GroupBy(pair => pair.Value);

littleguru
allein, allein,... allein, allein!

eddwo wrote:

Wow, I'd never have believed the answer could be so simple!

class Pair<K, V>
{
   public K Key { get; set; }
   public V Value { get; set; }
}



var data = new List<Pair<string,int>> { new Pair<string,int> { Key = "a", Value= 5},
                                        new Pair<string,int> { Key = "b", Value= 7},
                                        new Pair<string,int> { Key = "c", Value= 12},
                                        new Pair<string,int> { Key = "d", Value= 7},
                                        new Pair<string,int> { Key = "e", Value= 5},
                                        new Pair<string,int> { Key = "f", Value= 12},
                                        new Pair<string,int> { Key = "g", Value= 9} };

var invert = data.GroupBy(v => v.Value, k => k.Key);

//The first lambda extracts keys from the input values,
//The second extracts values from the input keys,
//and it uses the default equality comparer unless you specify one as another lambda in an overload.

Ever tried this (notice: i didn't define any pair class at all):

var data = new[] {
    new { Key = "a", Value = 5 },
    new { Key = "b", Value = 4 },
    new { Key = "c", Value = 3 },
    new { Key = "d", Value = 2 },
    new { Key = "e", Value = 1 },
    new { Key = "f", Value = 0 } };

you know, just for fun Big Smile