Chapter 16
An Introduction to LINQ

Kurt Nørmark ©
Department of Computer Science, Aalborg University, Denmark

Abstract
Previous lecture Next lecture
Index References Contents		In this lecture we will introduce LINQ. We will emphasize the historical background of LINQ, and the basic C# ideas and patterns, on top of which LINQ has been built. We will also draw the attention to similarities and differences between LINQ queries and methods in the generic List class, which we discussed in an ealier lecture about collections.

Origin and Rationale
Slide Annotated slide Contents Index
References 

LINQ = Languge Integrated Query

The main ideas behind LINQ come from functional programming languages and database query languages (SQL)

  • LINQ and functional programming

    • Builds on old ideas from Lisp: Map, filter, reduce.

    • Programming without (side)effects

    • Lazy evaluation

  • LINQ and SQL

    • LINQ is a query language

    • LINQ fragments are translated to SQL (via so-called Expression Trees)

LINQ - as used from C# - can both be used on all kinds of .NET collections, and instead of SQL

LINQ Concepts
Slide Annotated slide Contents Index
References 

  • Sequence

    • A collection - of type IEnumerable<T> - that can be traversed by use of an iterator

    • IQueryable<T> is a sub-interface of IEnumerable<T>.

  • Data source

    • The sequence considered the original input to a query

  • Query

    • An expression which (lazily) extracts information from a sequence

  • Query Operator

    • A pure function, defined on Sequence types, and used in a query

  • LINQ Provider

    • An implementation of a number of query operators on a given kind of data source

    • Examples: LINQ to Objects and LINQ to SQL

Map, filter, and reduce
Slide Annotated slide Contents Index
References 

Classical wisdom from functional programming on lists: A large set of problems can be solved by mapping, filtering, and reduction.

  • Mapping

    • Apply a function to each element of a collection and return the resulting collection

    • LINQ: Select

  • Filtering

    • Apply a predicate on each element of a collection, and return those elements that satisfy the predicate

    • LINQ: Where

  • Reduction

    • Apply a binary function on neighbour pairs of collection elements (either from left to right, or right to left), and "boil" down the collection to a single value.

    • LINQ: Aggregate

      • Specialized aggregations: Count, Min, Max, Sum, Average.

Basic LINQ Examples
Slide Annotated slide Contents Index
References 

Queries on a number of Person objects

Program: Sample Data - short form. 
    new List<Person>{
     new Person{FName="Pippi", LName="Pi",   Age=25, Sex = Sex.Female},
     new Person{FName="Lone",  LName="Rho",  Age=51, Sex = Sex.Female},
     new Person{FName="Anni",  LName="Lyng", Age=36, Sex = Sex.Female},
     new Person{FName="Martin",LName="Beck", Age=57, Sex = Sex.Male},
     new Person{FName="Per",   LName="Birk", Age=47, Sex = Sex.Male},
     new Person{FName="Stig",  LName="Malm", Age=50, Sex = Sex.Male} 
   };

Program: Sample data - Class Persons and a collection of persons. 
using System;
using System.Collections.Generic;

public enum Sex {Female, Male}

public class Person{
  public string FName{get; set;}
  public string LName{get; set;}
  public int Age{get; set;}
  public Sex Sex{get; set;}

  public override string ToString(){
    return FName + " " + LName;
  }

  public static List<Person> SomePersons{
  get {
   return
    new List<Person>{
     new Person{FName="Pippi", LName="Pi",   Age=25, Sex = Sex.Female},
     new Person{FName="Lone",  LName="Rho",  Age=51, Sex = Sex.Female},
     new Person{FName="Anni",  LName="Lyng", Age=36, Sex = Sex.Female},
     new Person{FName="Martin",LName="Beck", Age=57, Sex = Sex.Male},
     new Person{FName="Per",   LName="Birk", Age=47, Sex = Sex.Male},
     new Person{FName="Stig",  LName="Malm", Age=50, Sex = Sex.Male} 
   };
  }}

  
}

Program: The average age of all females. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // The average age of all females:

    double result = Person.SomePersons
       .Where(p => p.Sex == Sex.Female)
       .Select(p => p.Age)
       .Average();

   Console.WriteLine("Result = {0}", result);  // Result = 37,3333333333333
  }
}

Program: The average age of all females - basic version. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // The average age of all females - basic version.
    // Uses only Select, Where and Aggregate.

    IEnumerable<int> ages = Person.SomePersons
       .Where(p => p.Sex == Sex.Female)
       .Select(p => p.Age);

    double result =
       ages.Aggregate(0.0, (sum,i) => sum + i) / ages.Count();

   Console.WriteLine("Result = {0}", result);  // Result = 37,3333333333333
  }
}

Program: A comma-separated list of all male first names, youngest first. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // A comma-sep. list of all male first names, youngest first.

    string result = Person.SomePersons
       .Where(p => p.Sex == Sex.Male)
       .OrderBy(p => p.Age)
       .Select(p => p.FName)
       .Aggregate("", (res, nm) => res + " " + nm);

   Console.WriteLine("Result = {0}", result);
                                        // Result =  Per Stig Martin
  }
}

Program: A sequence of female-male pairs sequences. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // A collection of all possible combination of female-male pairs

    IEnumerable<Person> males = Person.SomePersons
       .Where(p => p.Sex == Sex.Male);

    IEnumerable<Person> females = Person.SomePersons
       .Where(p => p.Sex == Sex.Female);

    var pairsPerMale = males               // A sequence of sequences
      .Select(m => females
                    .Select(f => new{First=f, Second=m}));

    foreach(var pairs in pairsPerMale){    
        foreach(var pair in pairs)
          Console.WriteLine("{0} <-> {1}", pair.First, pair.Second);
    }
  }
}

Program: Same - using flattening SelecteMany. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // A collection of all possible combination of female-male pairs

    IEnumerable<Person> males = Person.SomePersons
       .Where(p => p.Sex == Sex.Male);

    IEnumerable<Person> females = Person.SomePersons
       .Where(p => p.Sex == Sex.Female);

    var pairs = males     // SelectMany flattens the nested sequences
      .SelectMany(m => females
                    .Select(f => new{First=f, Second=m}));

    foreach(var pair in pairs)
          Console.WriteLine("{0} <-> {1}", pair.First, pair.Second);
  }
}

Program: Equivalent output of last two programs: all femal-male pairs. 
Pippi Pi <-> Martin Beck
Lone Rho <-> Martin Beck
Anni Lyng <-> Martin Beck
Pippi Pi <-> Per Birk
Lone Rho <-> Per Birk
Anni Lyng <-> Per Birk
Pippi Pi <-> Stig Malm
Lone Rho <-> Stig Malm
Anni Lyng <-> Stig Malm

An overview of some LINQ Query Operators
Slide Annotated slide Contents Index
References 

  • Operators that return sequences s

    • s.Select(Func)         Func is an arbitrary element function

    • s.Where(Func)         Func is a predicate element

    • s.Distinct()         Removes duplicates

    • s.Take(int)

    • s.Intersect(Sequence)

    • s.Union(Sequence)

    • s.Concat(Sequence)

    • s.OrderBy(Func)         Func is key selector

  • Operators that return an element

    • s.Aggregate(Func) ,     s.Aggregate(seed, Func)

    • S.First()

    • S.Last()

    • S.Max()

    • S.Min()

    • S.ElementAt(int)

    • s.Single()       Returns the only element.

  • Predicates (return boolean)

    • s.Any()       Returns if there is at least one element

    • s.Contains(element)

  • Operators that return an other type of object

    • S.Count()

See the extension methods in the generic interface System.Collections.Generic.IEnumerable<T> and, even better, in the static class System.Linq.Enumerable

LINQ Query Operations vs List<T> methods.
Slide Annotated slide Contents Index
References 

Many important methods in List<T> mutate the list

The similar LINQ query operations are pure functions - they return a new modified copy of the list

  • Traversal of collections

    • List<T>:   list.ForEach(Action);

    • LINQ:   newList = list.Select(Func);

  • Removal form collections

    • List<T>:   list.RemoveAll(Predicate);

    • LINQ:   newList = list.Where(negated Predicate);

  • Appending collections

    • List<T>:   list.AddRange(otherList);

    • LINQ:   newList = list.Concat(otherList);

  • Reversing collections

    • List<T>:   list.Reverse();

    • LINQ:   newList = list.Reverse();

  • Sorting collections

    • List<T>:   list.Sort(comparerMethod);

    • LINQ:   sortedList = list.OrderBy(KeySelector);

Exercise 16.2. List og Linq?

Get some practical experience with the List and LINQ operations described on the accompanying slide.

You may, for instance, activate the operations on a simple collection of numbers.

Be sure to understand the difference between an imperative solution (the state of the collection is affected, the collection is mutable) and a functional solution (the collection is not modified, immutable).

How a LINQ Query Operation works
Slide Annotated slide Contents Index
References 

LINQ Query Operations are extension methods in the generic interface IEnumerable<T>.

Program: Reproduction of some central query operations. 
using System;
using System.Collections.Generic;

public static class LinqQueryOperations{

  public static IEnumerable<TTarget> MySelect<TSource,TTarget>
    (this IEnumerable<TSource> source, Func<TSource,TTarget> selector){
    foreach(TSource el in source)
      yield return selector(el);
  }

  public static IEnumerable<TSource> MyWhere<TSource>
    (this IEnumerable<TSource> source, Func<TSource,bool> predicate){
    foreach(TSource el in source)
      if (predicate (el)) yield return el;
  }

  public static TSource MyAggregate<TSource>
    (this IEnumerable<TSource> source, 
     Func<TSource,TSource,TSource> reducer){
     IEnumerator<TSource> e = source.GetEnumerator();
     bool sourceNotEmpty = e.MoveNext(); 
     if (sourceNotEmpty){
       TSource result = e.Current;
       while(e.MoveNext())  
          result = reducer(result, e.Current);       
       return result;
    } 
    else throw new InvalidOperationException("Source must be non-empty");
  }

  public static int MyCount<TSource>
    (this IEnumerable<TSource> source){
    return source
            .MySelect(p => 1)
            .MyAggregate((r,i) => r + i);
  }

}

Program: Using the reproduced query operations. 
using System;
using System.Collections.Generic;
// NOT using System.Linq;

public class Example1{
  
  public static void Main(){

    // The average age of all females - basic version

    IEnumerable<int> ageSum = Person.SomePersons
       .MyWhere(p => p.Sex == Sex.Female)
       .MySelect(p => p.Age);

    double result =
       (double)(ageSum.MyAggregate((sum,i) => sum + i)) / 
       ageSum.MyCount();

   Console.WriteLine("Result = {0}", result);  // Result = 37,3333333333333
  }
}

It is possible to program the fundamental query operations in a simple and straightforward way

Deferred Execution
Slide Annotated slide Contents Index
References 

An object of type IEnumerable<T> is not evaluated and expanded before it is traversed, typically in a foreach statement.

LINQ query operators return a linear list of iterators that decorates the data source

The Decorator design pattern

Reference

Compression and buffering decoration of a FileStream

The technical basis of LINQ
Slide Annotated slide Contents Index
References 

Most elements of C# 3.0 are invented as the technical basis of LINQ

  • Crucial prerequisites for LINQ:

    • Extension methods

    • Lambda expressions

    • Anonymous types

    • Implicitly typed local variables

    • Object initializers

Reference

Query Syntax versus Method Syntax
Slide Annotated slide Contents Index
References 

Query Syntax is syntactic sugar on top of the Method syntax, which we have introduced above

Program: The average age of all females - revisited. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // The average age of all females:

    double result = Person.SomePersons
       .Where(p => p.Sex == Sex.Female)
       .Select(p => p.Age)
       .Average();

   Console.WriteLine("Result = {0}", result);  // Result = 37,3333333333333
  }
}

Program: Same program with use of query syntax. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // The average age of all females:

    IEnumerable<int> ages =
        from   p in Person.SomePersons
        where  p.Sex == Sex.Female
        select p.Age;

    double result = ages.Average();

   Console.WriteLine("Result = {0}", result);  // Result = 37,3333333333333
  }
}

Program: A comma-separated list of all male first names, youngest first - revisited. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // A comma-sep. list of all male first names, youngest first.

    string result = Person.SomePersons
       .Where(p => p.Sex == Sex.Male)
       .OrderBy(p => p.Age)
       .Select(p => p.FName)
       .Aggregate("", (res, nm) => res + " " + nm);

   Console.WriteLine("Result = {0}", result);
                                        // Result =  Per Stig Martin
  }
}

Program: Same program with use of query syntax. 
using System;
using System.Collections.Generic;
using System.Linq;

public class Example1{
  
  public static void Main(){

    // A comma-sep. list of all male first names, youngest first.

    IEnumerable<string> names =  
       from p in Person.SomePersons
       where p.Sex == Sex.Male
       orderby p.Age
       select p.FName;

    string result = 
       names.Aggregate("", (res, nm) => res + " " + nm);

   Console.WriteLine("Result = {0}", result);
                                        // Result =  Per Stig Martin
  }
}

A Final Example: Sieve of Eratosthenes.
Slide Annotated slide Contents Index
References 

An simple and elegant way of finding prime numbers

Program: The Sieve query operator. 
using System;
using System.Collections.Generic;
using System.Linq;

public static class IEnumerableExtension {

  public static IEnumerable<long> Sieve(this IEnumerable<long> source){
      long first = source.First();
      yield return first;
      foreach (long i in source.Where(n => n % first != 0)
                               .Sieve()){
         yield return i;
      }
  }

}

Program: An application of the Sieve query operator. 
using System;
using System.Collections.Generic;
using System.Linq;

class Program{

    static void Main(string[] args){
        IEnumerable<long> naturalNumbers = 2L.AdInfinitum(),
                          primes = naturalNumbers.Sieve();
        foreach (long i in primes.Take(100))
           Console.WriteLine(i);

        Console.ReadLine();
    }

}

Program: The AdInfinitum extension method in type long. 
using System;
using System.Collections.Generic;

static public class LongExtension{

   public static IEnumerable<long> AdInfinitum(this long from){
      for (long i = from; true; i++)
            yield return i;
   }

}

Program: The program output - the first 100 primes. 
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
211
223
227
229
233
239
241
251
257
263
269
271
277
281
283
293
307
311
313
317
331
337
347
349
353
359
367
373
379
383
389
397
401
409
419
421
431
433
439
443
449
457
461
463
467
479
487
491
499
503
509
521
523
541

Collected references
Contents Index
The Decorator Design pattern
Basic LINQ Examples

 

Chapter 16: An Introduction to LINQ
Course home     Author home     About producing this web     Previous lecture (top)     Next lecture (top)     Previous lecture (bund)     Next lecture (bund)     
Generated: February 7, 2011, 12:24:18