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

Follow
Oops, something didn't work.

Try again?

Sign In to be begin to follow this thread

What does this mean?
Following an item on Channel 9 allows you to watch for new content and comments that you are interested in. You need to be signed in to Channel 9 to use this feature.

Getting "follow" information

Stop following this thread

Start following this thread

What does this mean?
Following an item on Channel 9 allows you to watch for new content and comments that you are interested in and view them all on your notifications page.

Removing your "follow"

Setting up your "follow"

Did you know you can
sign up for email notifications?
- Subscribe to this feed

reddit

Tweet

eddwo Wheres my head at?

Nov 26, 2007 at 8:55 AM

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

Nov 26, 2007 at 10:03 AM

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!

Nov 26, 2007 at 10:32 AM

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?

Nov 26, 2007 at 4:54 PM

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
Nov 26, 2007 at 5:41 PM
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

Nov 26, 2007 at 5:56 PM

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?

Nov 27, 2007 at 12:39 AM

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!
Nov 27, 2007 at 5:00 PM
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 <3 Seattle

Nov 28, 2007 at 12:55 AM

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

Thread Closed

This thread is kinda stale and has been closed but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.

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

What does this mean?

What does this mean?

Thread Closed