Na první pohled to zní jako nesmysl, protože paměť počítače je konečná a tak se do ní nekonečná datová struktura přece nemůže vejít.
To je samozřejmě pravda, ale funkcionální programování (ze kterého LINQ vychází) zná pojem "lazy evaluation", který práci s nekonečnými strukturami umožňuje. Podívejme se na následující příklad:
using System; using System.Collections.Generic; using System.Linq; // Hledání prvočísel - Erasthotenovo síto pro C# 3.0 a LINQ // založeno na učebním algoritmu Erasthotenova síta v jazyce Haskell // (c) Jan Stoklasa 2008 static class SieveOfErasthotenes { static void Main() { foreach (var i in primes().Take(100)) //vytiskne prvních 100 prvočísel { Console.WriteLine(i); } } public static IEnumerable<int> primes() { return sieve(integersFrom(2)); } //"Nekonečná" datová struktura //Nekonečný cyklus generuje všechna přirozená čísla od start včetně public static IEnumerable<int> integersFrom(int start) { for (int i = start; true; i++) { yield return i; } } //Erasthotenovo síto //První prvek seznamu xs je prvočíslo. Přidáme ho do výsledku, //přeskočíme ho a v seznamu necháme pouze čísla která nejsou dělitelná //prvním prvočíslem public static IEnumerable<int> sieve(IEnumerable<int> xs) { int prime=xs.First(); yield return prime; foreach(var i in sieve(xs.Skip(1).Where( a => a % prime > 0))) { yield return i; } } }
Program funguje tak že metoda integersFrom vrací "nekonečný" seznam všech celých čísel od zadaného parametru a metoda sieve filtruje tento seznam a nechává v něm pouze "všechna" prvočísla.
V metodě integersFrom je nekonečný cyklus for (int i = start; true; i++) a to vypadá hodně podezřele. Testovací podmínka tohoto for cyklu je vždycky true a tak se zdá že budeme pořád zvětšovat i o jedničku, a pořád, a pořád, a nikdy neskončíme.
Zkusme to - pokud ale program spustíme, řádně doběhne a vytiskne prvních 100 prvočísel. To je zvláštní, vždyť program který se dostane do nekonečného cyklu přece nikdy normálně neskončí! To se každý učil v základním kurzu programování a každý si jednou napsal program který donekonečna vypisuje "Hello World".
Jak je to možné? Ve světě C# 3.0, LINQ a funkcionálního programování nejsou "nekonečné cykly" tak úplně nekonečné. Klíčové slovo yield totiž přerušuje vykonávání cyklu a výpočet pokračuje dál na jiném místě kódu. Do "nekonečného" cyklu se výpočet vrátí později, až bude metoda sieve potřebovat další přirozená čísla. "Nekonečný" seznam všech přirozených čísel se tedy negeneruje najednou, to by se ostatně nevešel do konečné paměti počítače, ale po částech podle potřeby, tak jak běží výpočet. V tom je hlavní myšlenka tohoto příkladu a také podstata myšlenky "lazy evaluation". "Lazy evaluation" pochází ze světa funkcionálního programování a hodně jí využívá zajímavý programovací jazyk Haskell.
K čemu je to dobré? Představte si že v reálném čase analyzujete ceny akcií na burze, váš algoritmus pracuje s posloupností cen akcií a nějakým způsobem hledá maxima, minima a tendence změn v několika po sobě jdoucích hodnotách. Pokud nepoužijte "lazy evaluation", budete muset v některé fázi vašeho programu průběžně načítat další hodnoty z posloupnosti, takže kód který provádí analýzu cen bude promíchán s kódem který načítá další data. Pokud použijete "lazy evaluation", můžete s posloupností cen pracovat jako by byla nekonečná a probíhající výpočet si v pravou chvíli natáhne další prvky posloupnosti.
