Už vím jak pracuje LINQ

Ve čtvrtém díle našeho seriálu se dostaneme přes Yield k LINQ a vytvoříme i naši vlastní implementaci této knihovny pro Python a C#.

Yield return

Jak jsem slíbil, začneme zajímavou konstrukcí „yield return“, která se používá pro enumeraci dat bez vytváření datové struktury pro jejich držení (je tak rychlejší a paměťově úspornější). Tuto konstrukci pak využijeme v naší vlastní implementaci LINQu.

V prvním případě nejdřív vytvoříme jako seznam objektů pro enumeraci klasický list:

class SomeData
{
    public SomeData(int id) { Id = id; }
    public int Id { get; }
    static public IEnumerable<SomeData> CreateSomeData()
    {
        return new List<SomeData> { new SomeData(1), new SomeData(2), new SomeData(3) };
    }
}
 
public class Program
{
    public static void Main(string[] args)
    {
        foreach (var data in SomeData.CreateSomeData())
        {
            Console.WriteLine($"Hello, data {data.Id}!");
        }
    }
}

V druhém případě s yield return vidíme, že nemusíme konstruovat žádný přepravní „kontejner“ pro data, stačí nám pomocí pozměněného return (yield return) vracet jednotlivé objekty.

class SomeData
{
    public SomeData(int id) { Id = id; }
    public int Id { get; }
    static public IEnumerable<SomeData> CreateSomeData()
    {
        yield return new SomeData(1);
        yield return new SomeData(2);
        yield return new SomeData(3);
    }
}
 
public class Program
{
    public static void Main(string[] args)
    {
        foreach (var data in SomeData.CreateSomeData())
        {
            Console.WriteLine($"Hello, data {data.Id}!");
        }
    }
}

A jak tato konstrukce vůbec může fungovat? Je jasné, že CreateSomeData musí při zavolání ve foreach nějakým způsobem „držet stav“ a vracet se zpátky, na různá místa funkce (v „normální“ funkci je představa tří možných „return“ za sebou něco tak směšného… 😊). Naši smělou hypotézu s vracením ověříme jednoduše, pokusíme se „vracení“ zastavit:

class SomeData
{
    public SomeData(int id) { Id = id; }
    public int Id { get; }
}
 
class SomeDataCreator
{
    public bool StopMe { get; set; }
    public int Counter { get; private set; }      
 
    public IEnumerable<SomeData> CreateSomeData()
    {
            Counter++;
        if (!StopMe) yield return new SomeData(1);
        if (!StopMe) yield return new SomeData(2);
        if (!StopMe) yield return new SomeData(3);
    }
}
 
public class Program
{
    public static void Main(string[] args)
    {
        SomeDataCreator creator = new SomeDataCreator();
        IEnumerable<SomeData> yieldFn = creator.CreateSomeData();
        foreach (var data in yieldFn)
        {
            if (data.Id == 2)
            {
                creator.StopMe = true;
            }
            Console.WriteLine($"Hello, data {data.Id}!");
        }
        Console.WriteLine($"CreateSomeData call = {creator.Counter}!");
    }
}

Jak vidíme, při třetí kontrole StopMe podmínka neprojde a program vrátí pouze dvě hodnoty. Můžeme tak pěkně délku cyklu foreach řídit přímo v něm. Konstrukce yield není ve své podstatě nijak složitá, yield return je jenom „syntaktický cukr“ .NETu pro rychlejší tvorbu „Iteratoru“ (z našeho minulého článku). Z příkladu vidíme, že zavoláním metody CreateSomeData() a uložením jejího výsledku do yieldFn se metoda nespustí, vrátí pouze „agregátor“, který spustí metodu GetEnumerator() až je potřeba, tj. v cyklu foreach. Nezvyklé na „yield return“ zbývá pouze ono „létání“ tam a zpět ve foreach.

LINQ

Nyní využijeme všechny naše znalosti o iterátorech a vytvoříme naší implementaci LINQu (podle některých revoluční formy dotazování, viz odkaz níže), nejdříve pro Python (kód bude bez typů kratší a přehlednější) a pak pro C# (kde samozřejmě děláme celkem zbytečnou práci, protože LINQ je standardní součástí .NETu). Co tedy bude náš LINQ umět? LINQ umožňuje podobné operace jako jazyk SQL, ale na „čemkoli enumerovatelném“ (pole, listy, kolekce atp.). My vytvoříme pomocí lambda funkcí a vzoru Iterátor tyto základní operace:

Select - tj. výběr prvku. Prostě vybereme, co potřebujeme nebo vybraný prvek nějak transformujeme.
Where – vybereme pouze některé položky na základě dané podmínky.
OrderBy - seřazení výsledku, vzestupně a sestupně.
GroupBy - seskupení výsledků, implementováno vrácením dvojice klíč/seznam hodnot.

https://www.ictdemy.com/csharp/collections-and-linq/linq-in-csharp-revolution-in-querying

Návrhový vzor fluent interface

V naší implementace LINQu využíváme jeden jednoduchý „návrhový“ vzor, „fluent interface“. Je velmi jednoduchý (než jsem na jeho popis narazil, tak jsem ani nevěděl, že se považuje za vzor), metoda objektu vrací „sám sebe“, tím vytváříme řetězením volání metod pěkný „vláček“.

https://dotnettutorials.net/lesson/fluent-interface-design-pattern/

LINQ v Pythonu

V Pythonu jsem si tvorbu LINQu poněkud ulehčil, na většinu funkcí jsem použil interní funkce, takže select = map, where = filter, orderBy = sorted. Existuje i funkce groupby, z itertools, ale potřebuje seřazený vstup, tak jsem ji jako jedinou implementoval pomocí „slovníku“.

Objekt je navržen tak, aby se celý „vláček“ spustil až při iteraci. Jak je vidět na příkladech, vytvoříme „query“ pomocí dataList, přidáme prvek a při zavolání „for item in query:“ vše funguje i s novým prvkem. Funguje nám to díky vytvoření „gererátoru“ pomocí konstrukce „x for x in“. U groupBy a orderBy tento postup nefungoval, tak jsme si pomohli konstrukcí s „yield“, která nám vytvoří potřebný „agregátor“, jak je podrobně popsáno v první kapitole. V Pythonu se jen zapisuje yield bez return.

Pokud ovšem naší „LambdaQuery“ ukončíme metodou toList, tak se pochopitelně spustí přímo a nebude brát ohled na přidaný prvek!

https://stackoverflow.com/questions/8116666/itertools-groupby-not-grouping-correctly

https://treyhunner.com/2018/06/how-to-make-an-iterator-in-python/

class LambdaQuery:
 
    def __init__(self, iterable):
        self.iterable = iterable
   
    def __iter__(self):
        for x in self.iterable:
            yield x
   
    def select(self, fnSelect):
        return LambdaQuery((x for x in map(fnSelect, self.iterable)))
   
    def where(self, fnWhere):
        return LambdaQuery((x for x in filter(fnWhere, self.iterable)))
  
    def groupBy(self, fnKeySelector):
        return LambdaQuery(self.__constructGroupByIter(fnKeySelector))
   
    def orderBy(self, fnOrder, desc=False):
        return LambdaQuery(self.__constructIter(lambda x: sorted(x, key=fnOrder, reverse=desc)))
   
    def toList(self):
        return list(self.iterable)
   
    def __constructIter(self, fn):
        for x in fn(self):
            yield x
   
    def __constructGroupByIter(self, fnKeySelector):
        groupDict = {}
 
        for item in self.iterable:
            key = fnKeySelector(item)
 
            if key in groupDict:
                groupedValues = groupDict[key]
            else:
                groupedValues = (key, [])
                groupDict[key] = groupedValues
 
            groupedValues[1].append(item)
 
        for x in groupDict.values():
            yield x
 
 
 
print ("*******************************")
print ("1) Test select")
print ("*******************************")
dataList = [1, 2, 3]
query = LambdaQuery(dataList).select(lambda x: x * 10)
dataList.append(3)
 
for item in query:
    print (item)
 
print ("*******************************")
print ("2) Test select, where a orderBy")
print ("*******************************")
dataList = [1, 2, 3, 4, 5]
query = LambdaQuery(dataList).where(lambda x: x < 4).orderBy(lambda x: x, desc=True).select(lambda x: x * 10)
dataList.append(3)
 
for item in query:
    print (item)
 
print ("*******************************")
print ("3) Test Group By")
print ("*******************************")
dataList = [[1, 'A'], [2, 'B'], [3, 'A'], [4, 'B'], [5, 'C']]
query = LambdaQuery(dataList).where(lambda x: x[0] < 4).select(lambda x: (x[1].lower(), x[0])).groupBy(lambda x: x[0])
dataList.append([3, 'A'])
 
for key, group in query:
    for thing in group:
        print("%s is group with value %s." % (key, thing[1]))
    print("---")

https://onecompiler.com/python/

LINQ v .NETu

Kód našeho zbytečného LINQu (slouží pouze k pochopení principů) v .NETu je z hlediska funkčnosti skoro úplně stejný, jako kód v Pythonu. Díky generickým typům vypadá ovšem daleko víc „krypticky“. Hlavní rozdíl mezi implementacemi je v tom, že .NET umožňuje tvoru „extension methods“, naše funkce se tak spouští přímo na dataList a není potřeba tvořit objekt (LambdaQuery je statická třída a její název není ani vidět). Nepoužíváme také žádné interní pomocné funkce jako map nebo filter, protože tuto funkci řeší .NET pomocí LINQu, jehož náhradu programujeme. V prvním „nultém“ „testu“ jsem navíc oproti Pythonu ukázal, že knihovní LINQ metoda Select se chová analogicky jako naše MySelect.

public static class LambdaQuery
    {
        public static IEnumerable<T2> MySelect<T, T2>(this IEnumerable<T> iterable, Func<T, T2> fnSelector)
        {
            foreach (T item in iterable)
            {
                yield return fnSelector(item);
            }
        }
 
        public static IEnumerable<T> MyWhere<T>(this IEnumerable<T> iterable, Func<T, bool> fnPredicate)
        {
            foreach (T item in iterable)
            {
                if (fnPredicate(item)) yield return item;
            }
        }
 
        public static IEnumerable<T> MyOrderBy<T, T2>(this IEnumerable<T> iterable, Func<T, T2> fnKeySelector, bool desc = false)
        {
            List<T> list = new List<T>(iterable);
            list.Sort(new MyComparer<T, T2>(fnKeySelector, reverse: desc));
 
            //Proč nevracet přímo list? Nefungovalo by to
            foreach (T item in list)
            {
                yield return item;
            }
        }
 
        public static IEnumerable<Tuple<T2, List<T>>> MyGroupBy<T, T2>(this IEnumerable<T> iterable, Func<T, T2> fnKeySelector)
        {
            Dictionary<T2, Tuple<T2, List<T>>> groupDict = new Dictionary<T2, Tuple<T2, List<T>>>();
 
            foreach (T item in iterable)
            {
                T2 key = fnKeySelector(item);
                Tuple<T2, List<T>> groupedValues;
 
                if (groupDict.ContainsKey(key))
                {
                    groupedValues = groupDict[key];
                }
                else
                {
                    groupedValues = new Tuple<T2, List<T>>(key, new List<T>());
                    groupDict.Add(key, groupedValues);
                }
 
                groupedValues.Item2.Add(item);
            }
 
            foreach (Tuple<T2, List<T>> item in groupDict.Values)
            {
                yield return item;
            }
        }
 
 
        public static List<T> MyToList<T>(this IEnumerable<T> iterable)
        {
            return new List<T>(iterable);
        }
 
        private class MyComparer<T, T2> : IComparer<T>
        {
            private Func<T, T2> _FnKeySelector;
            private bool _Reverse;
 
            public MyComparer(Func<T, T2> fnKeySelector, bool reverse = false)
            {
                _FnKeySelector = fnKeySelector;
                _Reverse = reverse;
            }
 
            public int Compare(T x, T y)
            {
                T2 value1 = _FnKeySelector(x);
                T2 value2 = _FnKeySelector(y);
                int result = Comparer<T2>.Default.Compare(value1, value2);
 
                return (_Reverse) ? -1 * result : result;
            }
        }
    }
 
      public class Program
      {
            public static void Main(string[] args)
            {
                              Console.WriteLine("*******************************");
            Console.WriteLine("0) Test LINQ select");
            Console.WriteLine("*******************************");
            List<int> dataList = new List<int> { 1, 2, 3 };
            IEnumerable<int> query = dataList.Select(x => x * 10);
            dataList.Add(3);
 
            foreach (int item in query)
            {
                Console.WriteLine(item);
            }
 
 
            Console.WriteLine("*******************************");
            Console.WriteLine("1) Test select");
            Console.WriteLine("*******************************");
            dataList = new List<int> { 1, 2, 3 };
            query = dataList.MySelect(x => x * 10);
            dataList.Add(3);
 
            foreach (int item in query)
            {
                Console.WriteLine(item);
            }
 
            Console.WriteLine("*******************************");
            Console.WriteLine("2) Test select, where a orderBy");
            Console.WriteLine("*******************************");
            dataList = new List<int> { 1, 2, 3, 4, 5 };
            query = dataList.MyWhere(x => x < 4).MyOrderBy(x => x, desc: true).Select(x => x * 10);
            dataList.Add(3);
 
            foreach (int item in query)
            {
                Console.WriteLine(item);
            }
 
            Console.WriteLine("*******************************");
            Console.WriteLine("3) Test Group By");
            Console.WriteLine("*******************************");
            var rawList2 = new List<Tuple<int, string>> { Tuple.Create(1, "A"), Tuple.Create(2, "B"), Tuple.Create(3, "A"),
                Tuple.Create(4, "B"), Tuple.Create(5, "C") };
 
            var queryGroup = rawList2.MyWhere(x => x.Item1 < 4).MySelect(x => Tuple.Create(x.Item2.ToLower(), x.Item1)).MyGroupBy(x => x.Item1);
            rawList2.Add(Tuple.Create(3, "A"));
 
            foreach (var group in queryGroup)
            {
                foreach (var thing in group.Item2)
                {
                    Console.WriteLine("{0} is group with value {1}.", group.Item1, thing.Item2);
                }
                Console.WriteLine("---");
            }
            }
      }