Tech Off Thread

9 posts

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

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

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.