Tech Off Thread

9 posts

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

Back to Forum: Tech Off
  • User profile image
    eddwo

    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.

  • User profile image
    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...

  • User profile image
    odujosh

    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.

  • User profile image
    eddwo

    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.

  • User profile image
    amotif

    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?


  • User profile image
    amotif

    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();
        }
    

    Smiley

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

  • User profile image
    eddwo

    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.

  • User profile image
    odujosh

    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);

  • User profile image
    littleguru

    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

Comments closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums, or Contact Us and let us know.