async/await и cancellation

Всем привет! Прошу прощения за то что долго не писал. Вынашивал планы родить две больших статьи, но то ли не выносил, то ли не родил. А тут подвернулась тема для маленькой заметочки. Будет приятно, если кому-то пригодится. Итак,

столкнулся недавно с необходимостью отмены асинхронных вычислений, выполненных на async программной модели .NET Framework 4.5. Воспользовался официальным блогом как руководством к действию и получил примерно следующий код:

try
{
    var bytesRead = await stream.ReadAsync(
        buffer, 0, bytesToRead, cancellationToken);
    // some code here
}
catch(TaskCancelledException)
{
    break;
}

Меня смутил подход, при котором индикатором отмены задачи является исключение. Во-первых, у меня предубеждение по поводу использования исключений не по назначению (а здесь оно явно лишнее). Во-вторых, Debug Output окно подзамусоривается текстом о возникших исключениях.

Примечательно то, что при использовании методов Task.ContinueWith исключение TaskCancelledException не возбуждается. Вместо этого мы имеем экземпляр Task, у которого после его отмены свойство IsCanceled установлено в true. Исключение будет возбуждено либо при вызове метода Task.Wait(), либо при обращении к свойству Task.Result.

Все верно, async/await паттерн подразумевает что после старта задачи код получает управление лишь при завершении или отмены задачи. При этом await конструкция вытягивает из задачи результат. Именно это вытягивание и приводит к возбуждению исключения. Обидно, но отказываться от async/await модели не хочется.

Вот тут и пришла идея поднять Task на уровень выше, т.е. await-ить не Task<int>, а Task<Task<int>>, обернув нужный Task в еще один Task с помощью примерно такого кода:

public static Task<Task<T>> Wrap<T>(this Task<T> task)
{
    var tsource = new TaskCompletionSource<Task<T>>();
    task.ContinueWith(tsource.SetResult);
    return tsource.Task;
}

public static Task<Task> Wrap(this Task task)
{
    var tsource = new TaskCompletionSource<Task>();
    task.ContinueWith(tsource.SetResult);
    return tsource.Task;
}

Можем воспользоваться этими методами следующим образом:

var tBytesRead = await stream
    .ReadAsync(buffer, 0, bytesToRead, cancellationToken)
    .Wrap();
if (tBytesRead.IsCanceled)
   break;
var bytesRead = tBytesRead.Result;

Теперь await ловит не только успешно завершенные задачи, но и отмененные. Осталось лишь пощупать IsCanceled и обратиться к свойству Result за результатом операции в случае если она не была отменена.

P.S. Приятный бонус заключается в том, что при моделировании мгновенной отмены операции Task.Delay(100, cancellationToken) подход с оборачиванием задачи показал примерно 4-х кратное преимущество по времени выполнения относительно подхода с поимкой возбужденного исключения.

Посещение чуждых иерархий или посетитель, которого не ждут

В прошлом посте я уделил внимание случаю, когда паттерн посетитель требуется прикрутить к некоторой структуре не модифицируя её. Тогда я воспользовался паттерном адаптер. Не так давно я столкнулся с необходимостью прикрутить паттерн посетитель к иерархии, чье множество классов было недоступно для модификации, и идея с паттерном адаптер не показалась мне здравой.

На той же предметной области, что и в прошлом посте, покажу в чем проблема: требовалось класс Engine, который ничего не знает о посетителе, привести к интерфейсу ICarElement, который обеспечивает метод Accept, обращающийся к методу посетителя ICarElementVisitor<TResult>, соответствующий типу Engine. Адаптер решал эту проблему, однако, при необходимости адаптировать к интерфейсу ICarElement значительное количество классов (даже 10), без кодогенератора будет скучно. Каждый адаптер – 12 линий кода. 120 линий кода для адаптации 10 классов – явный перебор, если есть другие решения. А они есть!

Восстановим и упростим предметную область примера:

class CarElement
{ 
}

class Wheel : CarElement
{
}

class Engine : CarElement
{
}
    
class Car : CarElement
{
    public Wheel[] Wheels = Enumerable.Range(1, 4).Select(_ => new Wheel()).ToArray();
    public Engine Engine = new Engine();
}

Я оставил супертип у иерархии частей машины. Он играет только роль обобщающего типа. Если супертипа в вашей иерархии нет - можно вместо него использовать System.Object. Никакой ответственности на супертип CarElement не накладывается. Никаких методов типа Accept он не предоставляет. Считаем, что создатель этой иерархии не задумывался о применении паттерна посетитель.

Но нам хочется воспользоваться паттерном посетитель. Воспроизведу код из предыдущего поста. Единственное отличие – для класса Engine не используется адаптер.

interface ICarElementVisitor<out TResult>
{
    TResult Visit(Wheel visitable);
    TResult Visit(Engine visitable);
    TResult Visit(Car visitable);
}

class GetNameVisitor : ICarElementVisitor<string>
{
    public string Visit(Wheel visitable)
    {
        return "wheel";
    }

    public string Visit(Engine visitable)
    {
        return "engine";
    }

    public string Visit(Car visitable)
    {
        return "car";
    }
}

class GetChildrenVisitor : ICarElementVisitor<IEnumerable<CarElement>>
{
    public IEnumerable<CarElement> Visit(Wheel visitable)
    {
        yield break;
    }

    public IEnumerable<CarElement> Visit(Engine visitable)
    {
        yield break;
    }

    public IEnumerable<CarElement> Visit(Car visitable)
    {
        yield return visitable.Engine;
        foreach (var wheel in visitable.Wheels)
        {
            yield return wheel;
        }
    }
}

Еще раз хочу обратить внимание на то что код конкретных посетителей не зависит от способа диспетчеризации вызовов, и потому инвариантен к диспетчеризации. За диспетчеризацию будет отвечать следующий метод-расширение:

static class CarElementExtensions
{
    public static T Accept<T>(this CarElement element, ICarElementVisitor<T> visitor)
    {
        var wheel = element as Wheel;
        if(wheel != null)
            return visitor.Visit(wheel);

        var engine = element as Engine;
        if (engine != null)
            return visitor.Visit(engine);

        var car = element as Car;
        if (car != null)
            return visitor.Visit(car);

        throw new NotSupportedException();
    }
}

Осталось повторить код теста. Он остался неизменен.

static class Test
{
    public static void TestVisitor()
    {
        var childrenVisitor = new GetChildrenVisitor();
        var nameVisitor = new GetNameVisitor();

        CarElement car = new Car();

        var elements = car.Walk(e => e.Accept(childrenVisitor));
        var elementNames = elements.Select(e => e.Accept(nameVisitor));

        foreach (var elementName in elementNames)
        {
            Console.WriteLine(elementName);
        }
    }

    public static IEnumerable<T> Walk<T>(this T root, Func<T, IEnumerable<T>> next)
    {
        var q = next(root).SelectMany(n => Walk(n, next));
        return new[] { root }.Concat(q);
    }
}

Таким образом, для того чтобы добавить обход по некоторому классу, достаточно внести его в интерфейс посетителя ICarElementVisitor и добавить несколько строк в метод расширение Accept. Этот подход существенно экономнее, чем написание адаптеров к непослушным классам. Осталось только сделать замечание, что представленный в этом посте подход нельзя называть классическим посетителем.

Еще один штрих будет полезен тем, кто уже перешел на .NET 4, либо собирается переходить на него. Написание метода-расширения Accept можно водрузить на рантайм! Вот так:

static class CarElementExtensions
{
    public static T Accept<T>(this CarElement element, ICarElementVisitor<T> visitor)
    {
        return visitor.Visit((dynamic)element);
    }
}

Решение о том, какой из методов интерфейса ICarElementVisitor нужно вызывать для конкретного объекта CarElement, будет принято прямо во время выполнения программы. Полагаю, что это несколько снизит производительность, возможно стоит относиться к этому осторожно при посещении больших иерархий.

Последняя деталь – в связи с неожиданным поведением RuntimeBinder-а, не получается использовать следующую форму объявления интерфейса посетителя:

interface IVisitor<in TVisitable, out TResult>
{
    TResult Visit(TVisitable visitable);
}

interface ICarElementVisitor<out TResult> :
    IVisitor<Wheel, TResult>,
    IVisitor<Engine, TResult>,
    IVisitor<Car, TResult>
{
    //TResult Visit(Wheel visitable);
    //TResult Visit(Engine visitable);
    //TResult Visit(Car visitable);
}

Binder считает что у интерфейса ICarElementVisitor нет методов Visit. Это действительно так, но такое поведение отличается от поведения компилятора C#. Подозрение о том что это баг есть не только у меня.

Код с динамической диспетчеризацией вполне работоспособен с первым объявлением интерфейса ICarElementVisitor в этом посте.

Visitor revisited

Сегодня я покажу свое видение паттерна Visitor. У меня складывается впечатление о том что в значительном количестве источников он представлен не самым удачным образом.

Рассмотрим пример из википедии. К сожалению, это типичный такой примерчик посетителя не без недостатков. Я бы даже сказал с ошибками.
Первая и не самая серьезная ошибка примера – то что вложенные элементы Car хранятся в массиве и паттерн Visitor – не лучший способ для перебора этих элементов. Куда проще и нагляднее было бы прикрутить паттерн Composite.
Вторая ошибка серьезнее – обход структуры заложен в методах accept. Я не считаю метод accept подходящим местом для расположения логики обхода структуры.
Я обозначил их для того, чтобы пробегая дальше по определениям сосредотачивать внимание именно на этом аспекте.

Вернемся к началу статьи в Wikipedia:

In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure it operates on. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures.

Т.е. нам обещают что операции можно прикручивать на существующую структуру. Однако пример демонстрирует что мы не можем прикрутить обход извне. Более того, расположенная логика обхода в методе accept мешает выполнять другие операции над одиночными элементами структуры. Будучи примененный к Car посетитель CarElementPrintVisitor неизбежно выведет в консоль имена всех элементов машины, хотим мы этого или нет. Любая новая операция обречена выполняться над всей структурой. И об этом ничего не сказано в “определении”. В определении вообще ни слова про обход структуры, но как видно из примера, ничего кроме обхода паттерн делать не умеет. Но зато умеет их делать по-разному.

GoF

Назначение
Описывает операцию, выполняемую с каждым объектом из некоторый структуры. Паттерн посетитель позволяет определить новую операцию, не изменяя классы этих объектов.

Опять ничего про обход в назначении паттерна. Зато об обходе написано далее:

Результаты

• Упрощает добавление новых операций. …
• Объединяет родственные операции и отсекает те, которые не имеют к ним отношения. …
• добавление новых классов ConcreteElement затруднено …
• Посещение различных иерархий классов.

Аж на 4-м месте в списке результатов применения после отрицательного результата.
И далее:

Реализация
….
Какой участник несет ответственность за обход структуры. Посетитель должен обойти каждый элемент структуры объектов. Вопрос в том, как туда попасть.

Вот как, должен? А как же операции, не связанные с обходом?

Ответственность за обход можно возложить на саму структуру объектов, на посетителя и на отдельный объект итератор.

На саму структуру объектов – мы уже видели как это делается и к чему приводит.

Другое решение – воспользоваться итератором для посещения элементов. … Поскольку внутренние итераторы реализуются самой структурой объектов, то работа с ними во многом напоминает предыдущее решение, когда за обход отвечает структура.

Ну а почему тогда не композит?

Можно даже поместить алгоритмы обхода в посетитель, хотя закончится это дублированием кода обхода в каждом классе ConcreteVisitor для каждого агрегата ConcreteElement. Основная причина такого решения – необходимость реализовать особо сложную стратегию обхода (?!?!?!?), зависящую от результатов операций над объектами структуры. Этот случай рассматривается в разделе “Пример Кода”.

Если честно, то я не понимаю, откуда дублирование. И в разделе “Пример Кода” обход реализован в методах accept.

Джошуа Кериевски (Рефакторинг с использованием шаблонов) считает что все знакомы с назначением паттерна и пишет просто:

Переместить задачу накопления в реализацию шаблона Visitor, который для накопления информации может посетить каждый класс.

Да и рассматривает он Visitor только лишь в аспекте Move Accumulation to Visitor.

Роберт К. Мартин (Быстрая разработка программ. Принципы, примеры, практика)

Семейство Visitor позволяет добавлять к существующим иерархиям новые методы без обновления этих иерархий.

Отлично, новые методы без обновления этих иерархий! Кстати, чуть ли не единственный случай, где пример Visitor-а не содержит обхода. СОВСЕМ НЕ СОДЕРЖИТ.

The Visitor pattern and multiple dispatch

Its purpose is to provide new operations on a class or set of related classes without actually altering the classes involved.

Пример тоже не содержит обхода.

Попытаемся осмыслить

Итак, все рассмотренные источники (кроме Д. Кериевски) утверждают что паттерн предназначен для обеспечения новых операций без изменений классов структуры объектов. Для меня это ключевая особенность паттерна. Вот почему:

Паттерн visitor непрост в реализации, и имеет недостатки. Потому, когда я его применяю, я его применяю для убийства сразу всех зайцев. И если мне один заяц будет мешать убивать остальных, то фиг с ним, пусть бежит в лес (много зайцев лучше одного). Т.е. обход структуры я воспринимаю лишь как одного из зайцев, и не самого важного.

Какие еще бывают зайцы кроме обхода?

• Валидация объектов (существуют разные причины по которым валидацию следует рассматривать как внешнюю по отношению к объектам операцию)
• Вызов метода сохранения объекта в БД, Log файл, рисование на специализированных устройствах
• Размазывание объектов по View-шкам GUI и собирание информации с вьюшек обратно в объект (это только пример, совсем не значит что я так делаю)
• Получение локализованного наименования объекта
• …

В общем все то, что нужно делать специальным способом в зависимости от типа объекта, но что по каким-то причинам не следует вставлять в методы объекта(ов).

Пример: есть Order и Product, которые не знают своих имен, но их надо как-то назвать чтобы представить пользователю. Операция получения названия объекта – внешняя по отношению к Order-у. Все к тому, чтобы воспользоваться посетителем еще раз (если он уже есть). Но если в методе accept класса Order-а реализован обход, то получить название Order-а мы сможем только в случае когда у Order-а нет вложенных объектов.

Если нужен обход структуры, то я за то, чтобы сделать его одной из операций, так чтобы можно было совмещать обход с другими операциями, либо выполнять другие операции отдельно от обхода. Так же выделение обхода в отдельную операцию приведет к возможности менять алгоритм обхода.

Приведу исходный код примера из википедии, но на C# и значительно упрощенный так, чтобы в нем осталась лишь суть паттерна и ничего более:

interface ICarElementVisitor
{
    void Visit(Wheel wheel);
    void Visit(Engine engine);
}

interface ICarElement
{
    void Accept(ICarElementVisitor visitor);
}

class Wheel : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class Engine : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class CarElementPrintVisitor : ICarElementVisitor 
{
    public void Visit(Wheel wheel)
    {
        Console.WriteLine("wheel");
    }
    public void Visit(Engine engine)
    {
        Console.WriteLine("engine");
    }
}

class Test
{
    public static void TestVisitor()
    {
        var elements = new ICarElement[] {new Engine(), new Wheel()};
        var visitor = new CarElementPrintVisitor();
        foreach (var carElement in elements)
        {
            carElement.Accept(visitor);
        }
    }
} 

Выше приведена квинтэссенция классического посетителя, лишенная недостатков примера из википедии. Ну конечно, некоторой функциональности я его тоже лишил (ниже я ее восстановлю).

Что мне еще не нравится в этом коде?
Метод

void Visit(Wheel wheel);

не позволяет получить результат применения паттерна напрямую. Единственный способ что-то получить – накопить это что-то в конкретном классе посетителя, либо извне (например в глобальной переменной) и потом забрать значение. Было бы лучше, если бы визитор умел возвращать результат операции. Но опять-таки, если операции разные, то и типы результатов у них будут разные. Тип возвращаемого результата должен передаваться generic параметром интерфейса (а не метода!!! Важно, чтобы все методы Visit интерфейса посетителя меняли тип результата синхронно, а не по отдельности):

TResult Visit(Wheel wheel);

Отлично. Еще бы уметь передать дополнительный аргумент. Хотя это как раз лишнее. Аргумент можно передать непосредственно в класс посетителя.

Итак, интерфейс посетителя будет выглядеть так:

interface ICarElementVisitor<out TResult> 
{
    TResult Visit(Wheel wheel);
    TResult Visit(Engine engine);
    TResult Visit(Car car); 
}

А лучше чуть по-другому:

interface IVisitor<in TVisitable, out TResult>
{
    TResult Visit(TVisitable visitable);
}

interface ICarElementVisitor<out TResult> :
    IVisitor<Wheel, TResult>,
    IVisitor<Engine, TResult>,
    IVisitor<Car, TResult>
{
    //TResult Visit(Wheel visitable);
    //TResult Visit(Engine visitable);
    //TResult Visit(Car visitable);
}

Функционально разницы никакой, просто я побаиваюсь напутать что-то с сигнатурой одного из методов, а вынесение метода Visit в отдельный интерфейс позволяет исключить некоторые ошибки.
(+) ключевые слова in/out в объявлении интерфейса
Если кого-то смущают ключевые слова in и out в списке generic параметров интерфейса, то об этом можно почитать здесь. Для этой статьи они никакой роли не играют и должны быть удалены при использовании кода в версиях языка C# 2.0-3.0
(-) ключевые слова in/out

Интерфейс элемента напротив не должен зависеть от generic параметров, но метод Accept должен уметь работать с разными типами посетителей:

interface ICarElement
{
    TResult Accept<TResult>(ICarElementVisitor<TResult> visitor);
}

Вот собственно реализация конкретного элемента паттерна:

class Wheel : ICarElement
{
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}

Ничего кроме метода Accept! Все как и в стандартных примерах, только угловых скобочек побольше.

Дальше будет элемент посложнее. Помните, в определениях говорилось о том, что паттерн visitor можно применять к существующим структурам не модифицируя их? Покажу как это можно сделать не модифицируя элемент совсем (с помощью адаптера).

class Engine
{
}

class EngineAdapter : ICarElement
{
    public EngineAdapter(Engine engine)
    {
        Engine = engine;
    }
    public Engine Engine { get; private set; }

    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(Engine);
    }
}

Можно было интерфейс ICarElementVisitor замкнуть на EngineAdapter вместо Engine, если бы это играло какую-то роль.

Теперь составной элемент Car. Обратите внимание на то, что метод Accept не содержит логики обхода!

class Car : ICarElement
{
    public Wheel[] Wheels = Enumerable.Range(1, 4).Select(_ => new Wheel()).ToArray();
    public Engine Engine = new Engine();
        
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}

Дальше код визитора, достающего имена объектов:

class GetNameVisitor : ICarElementVisitor<string>
{
    public string Visit(Wheel visitable)
    {
        return "wheel";
    }

    public string Visit(Engine visitable)
    {
        return "engine";
    }

    public string Visit(Car visitable)
    {
        return "car";
    }
}

Дальше чуть сложнее. Посетитель, который из элементов достает наборы вложенных элементов:

class GetChildrenVisitor : ICarElementVisitor<IEnumerable<ICarElement>>
{
    public IEnumerable<ICarElement> Visit(Wheel visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Engine visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Car visitable)
    {
        yield return new EngineAdapter(visitable.Engine);
        foreach (var wheel in visitable.Wheels)
        {
            yield return wheel;
        }
    }
}

Здесь следует обратить на метод посещения составного объекта Car. Проходя по engine элементу он возвращает не сам элемент, а адаптер.

Ну и в конце-концов метод, который демонстрирует поведение паттерна:

public static void TestVisitor()
{
    var childrenVisitor = new GetChildrenVisitor();
    var nameVisitor = new GetNameVisitor();

    ICarElement car = new Car();

    var elements = car.Walk(e => e.Accept(childrenVisitor));
    var elementNames = elements.Select(e => e.Accept(nameVisitor));

    foreach (var elementName in elementNames)
    {
        Console.WriteLine(elementName);
    }
}

static IEnumerable<T> Walk<T>(this T root, Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new[] { root }.Concat(q);
}

Во-первых создаются экземпляры посетителей и составного элемента Car. Далее с помощью метода Walk, представляющего дерево в виде одиночной последовательности и описанного в предыдущем посте, а так же посетителя GetChildrenVisitor, строится набор элементов. Затем набор элементов преобразовывается в набор имен с помощью GetNameVisitor и выводится в консоль циклом foreach.

Итог

Итак, я восстановил функциональность примера из википедии, но избежал недостатков. Перечислю еще раз достоинства такого подхода:

• метод accept не содержит логики обхода (это достоинство само по себе, как и вытекающие из него следствия);
  
• логика обхода содержится снаружи иерархии, и это позволяет менять ее не изменяя объектов иерархии;
  
• внешний обход не мешает выполнению других операций, реализованных с помощью паттерна, и более того, позволяет комбинирование обхода с другими операциями;
  
• посетитель, возвращающий результат, позволяет избавиться от накопления данных внутри объектов либо внутри самого посетителя и использовать мощь LINQ в обходе иерархии;
  
• посетитель, возвращающий generic результат, позволяет удобно совмещать одним паттерном множество разнотипных операций.
  

Замечу так же, что никакого дублирования логики обхода в каждом классе ConcreteVisitor, как это было написано в GoF, не намечается.

Надеюсь, что моя статья позволит читателям использовать паттерн Visitor более эффективно.

З.Ы.
Респект тем кто дочитал до конца.

LINQ-ом по деревьям (часть 2)

В предыдущей части я рассказал о том, как ходить по деревьям LINQ-ом и о том какие проблемы с производительностью может породить цепочка перечислителей.
Итак, в бенчмарке присутствуют следующие методы:

Walk

С прошлого поста заменил Enumerable.Repeat(root, 1) на new [] {root}.

public static IEnumerable<T> Walk<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new []{root}.Concat(q);
}

Walk2

Слегка оптимизированная версия Walk, где методы SelectMany и Concat развернуты в конечный автомат yield return:

public static IEnumerable<T> Walk2<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    yield return root;
    foreach (var child in next(root))
    {
        foreach (var node in Walk2(child, next))
        {
            yield return node;
        }
    }
}

Эта версия Walk метода покажет нам ценность такого переписывания. Я не буду пропагандировать ни за ни против, просто предоставлю данные, а решать пусть будет каждый сам за себя, пользоваться ли высокоуровневыми методами, либо эквивалентными циклами.

WalkS

WalkS – обход с помощью структуры Stack<T>. Это самый простой способ преобразования callstack-а в структуру данных.

public static IEnumerable<T> WalkS<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current).Reverse())
        {
            stack.Push(x);
        }
    }
}

Здесь использован метод Enumerable.Reverse чисто для сохранения порядка обхода в соответствии с оригинальным методом Walk. Но гоняться в бенчмарке будет немного другой метод:

WalkS2

У этой модификации используется 2 стека (Stack<T>). Второй заменяет Enumerable.Reverse.

public static IEnumerable<T> WalkS2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    var stack2 = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current))
        {
            stack2.Push(x);
        }
        foreach (var x in stack2)
        {
            stack.Push(x);
        }
        stack2.Clear();
    }
}

WalkL

В очередной модификации вместо Stack<T> используется односвязный список.

class ListNode<T>
{
    public T Value { get; private set; }
    public ListNode<T> Next { get; private set; }

    public ListNode(T value, ListNode<T> next)
    {
        Value = value;
        Next = next;
    }
}
public static IEnumerable<T> WalkL<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var current = list;
        list = list.Next;
        yield return current.Value;

        foreach (var x in next(current.Value).Reverse())
        {
            list = new ListNode<T>(x, list);
        }
    }
}

Но воевать будет не она, а та что использует 2 односвязных списка:

WalkL2

Последняя модификация, учавствующая в бенчмарке использует один список для замены callstack-а, другой вместо Enumerable.Reverse().

public static IEnumerable<T> WalkL2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var currentNode = list;
        var nextNode = list.Next;
        yield return currentNode.Value;

        ListNode<T> tmpList = null;
        foreach (var v in next(currentNode.Value))
        {
            tmpList = new ListNode<T>(v, tmpList);
        }

        if(tmpList != null)
        {
            for (; tmpList != null; tmpList = tmpList.Next)
            {
                nextNode = new ListNode<T>(tmpList.Value, nextNode);
            }
        }
        list = nextNode;
    }
}

Depth

В бенчмарке учавствует еще один метод, который тоже обходит дерево, но при этом не пытается выпрямить его узлы в последовательность. Подсчет глубины конкретного двоичного дерева в чисто рекурсивной форме. Этот метод будет эталоном скорости.
Вслед за методом GetDepth привел класс узла дерева, на котором проходил бенчмарк.

public static int GetDepth<T>(this Node<T> node)
{
    return (node == null)
        ? 0
        : 1 + Math.Max(
            node.Left.GetDepth(),
            node.Right.GetDepth());
}

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
}

Забег №1

Случайным образом перемешанный массив индексов [0..N] подается на вход алгоритму, строящему двоичное дерево (без балансировки). Полученное дерево скармливается вышеуказанным методам Walk* и у полученного IEnumerable<int> извлекается последний элемент Enumerable.Last ().
Результаты первого забега (по оси x кол-во элементов, по y – время обхода в секундах):

Следующим образом выглядит таблица времен обхода дерева из 10М элементов:

Метод обхода	Время
Walk	00:00:24.7759974
Walk2	00:00:10.8108170
WalkS2	00:00:03.5185059
WalkL2	00:00:02.7030328
Depth	00:00:01.0753161

Что-то здесь не так. Судя по графику, нерекурсивные методы значительно быстрее, но я не увидел зависимости графиков рекурсивных методов от глубины дерева… И деревья-то подсовывались не слишком глубокие. Глубина дерева из случайно перемешанного набора из 20М индексов не превышала 60. При таком подходе, увеличивая вдвое число элементов, мы будем получать увеличение глубины дерева лишь на единицу. Геометрическая, блин, прогрессия! Страшно подумать, сколько нужно элементов, для того чтобы достичь глубины 1000 :(
Но кое-какие выводы можно сделать и из этого забега:

• Методы Walk и Walk2 идут ноздря в ноздрю и значительного перевеса не наблюдается, хотя и foreach-и немного опережают высокоуровневые методы SelectMany+Concat.
• Нерекурсивные методы WalkS2 и WalkL2 достаточно близки к эталонному Depth
• Односвязные списки немного шустрее чем Stack<T>.

Забег №2

То же самое двоичное дерево, но исходные данные теперь не перемешаны, потому получается вырожденное в список дерево, чья глубина будет равна числу элементов. Элементов будет мало, но теперь дерево будет сосредоточено в глубину.

Что интересно, рекурсивные методы Walk и Walk2 не осилили дерево глубиной 12000 и отвалились с StackOverflowException. Однако метод GetDepth работал стабильно (полагаю что JIT распознал хвостовую рекурсию и преобразовал рекурсию в цикл это не так, спасибо Пельмешко за внимательность. GetDepth-у для исключения нужно глубину 65000).


Этот эксперимент показывает нелинейную зависимость рекурсивных методов Walk и Walk2 от глубины дерева и совершенно ничего не показывает о нерекурсивных методах WalkS2, WalkL2 и рекурсивном но преобразованном в цикл методе GetDepth. Т.е. их зависимость от глубины на этом графике не видна. Время, которое показывали три последних метода на обходе 10000 элементов не превышало 0.001 секунды.

Итого:

Рекурсивная комбинация перечислителей представляет опасность переполнения стека на глубинах дерева от 10К. На глубинах дерева до 1000 рекурсивными перечислителями вполне можно пользоваться и их производительность хоть и уступает нерекурсивным методам,  но может быть вполне приемлема для множества задач.

P.S.

На RSDN Sinix-ом был приведен другой метод выпрямления рекурсивных комбинаций перечислителей. Нетрудно увидеть схожесть его метода с представленными мной. Отличия в сигнатуре (принимает коллекцию узлов), в порядке обхода (нет Reverse), да и в стек он помещает не узлы, а перечислители узлов. Не знаю, в чем фокус, но его метод работает примерно в 2 раза медленнее WalkS2, представленного мной (с Reverse-ом с помощью дополнительного стека). Ну и собственно название, UngroupRecurseEnumerator сбивает с толку. Это тот же самый обход дерева.

P.P.S.

В этой статье упоминается Range через yield foreach:

static IEnumerable<int> FromTo(int b, int e)
{
    if (b > e)
        yield break;
    yield return b;
    yield foreach FromTo(b + 1, e);
}

А вот и наш ответ Чемберлену

static IEnumerable<int> FromTo(int b, int e)
{
    return b.WalkL2(i =>
         (i < e)
            ? new int[] { i+1 } 
            : new int[] {});
}

Не столь красивый, но не требующий изменения языка.
А yield foreach все-таки сила!

Upd.

Я таки написал версию GetDepth с хвостовой рекурсией:

public static int GetDepthC<T>(this Node<T> node)
{
    return GetDepthCps(node, d => d);
}

static int GetDepthCps<T>(Node<T> node, Func<int, int> cont)
{
    return (node == null)
       ? cont(1)
       : GetDepthCps(node.Left, leftDepth =>
            GetDepthCps(node.Right, rightDepth =>
                cont(Math.Max(leftDepth, rightDepth))));
}

Естественно я не ожидал что C# ее выпрямит в цикл. А вот F# выпрямляет!
Если будут пожелания, можно в другой раз написать что-то вроде "CPS для чайников". Толку, правда, будет немного в рамках C#. Но разжевать предмет можно попробовать.

LINQ-ом по деревьям

Сегодня покажу универсальный код обхода любых деревьев с однотипными узлами.

public static class TreeWalker
{
    public static IEnumerable<T> Walk<T>(T root, Func<T, IEnumerable<T>> next)
    {
        var q = next(root).SelectMany(n => Walk(n, next));
        return Enumerable.Repeat(root, 1).Concat(q);
    }
}

За исключением нескольких отличий, этот метод похож на Enumerable.SelectMany. Отличия:

1. В качестве первого аргумента принимается один элемент (корень дерева), а не последовательность.
2. Метод рекурсивно применяется ко всем элементам, полученным с помощью делегата next из исходного.

Области применения

Для начала прогуляемся по дереву каталогов файловой системы:

foreach(var dir in TreeWalker.Walk(@"d:\Test", Directory.GetDirectories))
{
     Console.WriteLine(dir);
}

Однако, гулять – не главный бенефит этого метода. Главный – “выпрямлять” деревья для того чтобы по ним можно было гулять LINQ-ом.

Еще один пример - собрать только листовые узлы у TreeView можно такой конструкцией

var q = from rootNode in treeVew1.Nodes.Cast<TreeNode>()
        from node in TreeWalker.Walk(rootNode, n => n.Nodes.Cast<TreeNode>())
        where node.Nodes.Count == 0
        select node;

Совсем не обязательно обходить дерево целиком. Например, при работе с двоичными деревьями поиска, с помощью метода Walk можно находить минимальный, максимальный элемент и даже делать поиск конкретного элемента за время соразмерное  высоте дерева (при сбалансированном дереве – O(log N)).

Пусть у нас есть дерево из узлов следующего вида:

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; private set; }
    public Node<T> Left { get; private set; }
    public Node<T> Right { get; private set; }
}

Тогда для поиска минимального элемента потребуется следующий вспомогательный метод:

public static IEnumerable<Node<T>> NextLeft<T>(this Node<T> root)
{
    if (root.Left != null)
        yield return root.Left;
}

Тогда найти узел с минимальным элементом двоичного дерева можно следующей конструкцией:

TreeWalker.Walk(root, r => r.NextLeft()).Last();

Для поиска узла с конкретным элементом потребуется более хитрая вспомогательная функция, которая будет возвращать подузлы Left или Right в зависимости от результата сравнения значения текущего узла с искомым значением.

А если к функции получения дочерних узлов добавить маркировку пройденных узлов, то из метода Walk получится алгоритм “поиск в глубину” для графов.

Особенности реализации

Вместо Enumerable.Repeat(root, 1) можно было сделать new [] { root}, но я хотел сделать акцент на другом.

Как можно заметить, метод Walk ленив. Притом что его можно считать рекурсивным (он использует себя в определении своего тела), он не вызывает себя рекурсивно при обращении, а возвращает управление сразу же, возвращая перечислитель. Однако, агрессивное использование стека при работе метода никуда не делось, более того, оно более агрессивно, по сравнению с обычным рекурсивным методом. Все дело в том, что при погружении в дерево выстраиваются в цепочку активные перечислители на манер вложенных декораторов, длина цепочки которых пропорционален глубине погружения в дерево.

next(root).SelectMany добавляет в цепочку свои перечислители (полагаю что больше одного, лениво лезть в рефлектор). Над ним надстраивается Сoncat перечислитель.

Даже если дерево состоит только лишь из одного корневого элемента, вызовы IEnumerator<T>.MoveNext(), IEnumerator<T>.Current будут выполнены каскадно через 2-3 (а может и больше) перечислителей.

Итого, обход дерева высотой в несколько сот тысяч элементов с хорошей вероятностью может завершиться StackOverflowException (udated: 12000 элементов достаточно)… Даже если не завершится, цена вызова по цепочке перечислителей длиной в несколько глубин дерева может серьезно сказаться на производительности приложения. Ведь для получения очередного элемента нужно сделать два таких сверхглубоких вызова (MoveNext и Current).

Естественно, ситуацию можно изменить за счет переписывания метода Walk с какой-нибудь структурой данных, эмулирующей стек вызовов (например, Stack<T>). Но я пока в этом необходимости не испытываю. StackOverflowException я видел только на тестовых данных (двоичное дерево из миллиона элементов). А на тех данных, с которыми приходилось работать методу Walk, проблем с производительностью или с переполнением стека нет. Даже не было повода замеров производительности метода Walk с целью выявить зависимость времени выполнения от глубины дерева.

Если кому-то вопрос производительности и/или нерекурсивный вариант Walk метода окажется интересным, дайте знать в комментариях. А пока будем считать что я поделился красивым но не очень быстрым способом обхода деревьев с помощью LINQ-а.

P.S.

На авторство не претендую, аналогичный подходы к обходу деревьев я определенно встречал, единственное что я сделал – обобщил его, представил и предостерег от использования с деревьями больших глубин.

Монады для чайников

Вот и я написал собственное введение в монады. Нет, вовсе не потому что я разобрался в этом вопросе лучше других. Мне кажется, что мое введение будет проще чем другие, т.к. оно требует только лишь знаний языка C# и базовых знаний LINQ, и не потребует опыта в функциональном программировании. Я не обещаю, что после прочтения этого поста вы будете понимать и уметь использовать монады. Я только лишь покажу, что же это такое. Но все равно, после преодоления моего поста, должно сложиться хотя бы поверхностное представление о предмете. Полагаю, что вы уже сможете понимать, о чем речь, когда столкнетесь с упоминанием монад в будущем.

Тем же, кто уже знаком в достаточной мере с монадами, но все равно решит прочитать мой пост, предлагаю выразить критику, буду рад.
 
Значительная часть блогов лишь мельком затрагивает понятие монады чтобы рассказать о каком-нибудь монадном парсер-комбинаторе, асинхронном workflow или о чем-то пострашнее. Некоторые блоги и материалы отталкиваются от математики, комбинирования чистых функций, пользы монадах в функциональном программировании и прочей теории. А я предлагаю пожевать знакомые большинству концепции и повести читателя не от простого к сложному, а от уже знакомого к более простому.

Знакомство

Полагаю, что многие из разработчиков C# пользуются методом Enumerable.SelectMany либо вложенными друг в друга from clause. На всякий случай напомню, что from clause транслируется компилятором в вызов SelectMany. Тем, кто не понимает эти конструкции (читай не привыкнул к ним) рекомендую начать к ним привыкать как можно скорее. Это не сложно, к хорошему быстро привыкаешь. Вот статья, где упоминаются вложенные from конструкции - Query Expression Basics.

Рассмотрим следующий запрос в форме Query Expression:

IEnumerable<City> cityQuery =
    from country in countries
    from city in country.Cities 
    select city;

Его можно записать в следующем виде:

IEnumerable<City> cityQuery = countries
    .SelectMany(country => country.Cities);

Компилятор собственно и производит подобное преобразование, только он использует более сложную перегрузку метода SelectMany. Нам она пока ни к чему, сосредоточим внимание на более простой функции SelectMany. Вот ее сигнатура:

IEnumerable<TResult> SelectMany<TSource, TResult>(
   this IEnumerable<TSource> source,
   Func<TSource, IEnumerable<TResult>> selector)

Напомню её назначение:

Проецирует каждый элемент последовательности в объект IEnumerable<T> и объединяет результирующие последовательности в одну последовательность.

Думаю, стоит обратить внимание на одну деталь:

именно проецирует (связывает), а не выбирает. То что у объекта типа Country есть свойство со списком городов – это лишь совпадение. Для проекции мы могли бы использовать не только свойство Cities, а любой другой способ получения списка городов, будь они записаны в файле, в базе данных или возвращены веб-сервисом. Да и вместо класса страны мог быть ее числовой код.

Вобщем, знакомьтесь, SelectMany это и есть монада! Точнее ее часть… Точнее часть одной из монад… Но это пока не важно. Важно то, что если вы раньше не были знакомы с монадами, то теперь вы можете в ответ на вопрос “знаете ли вы что такое монады, используете ли их?” отвечать “А-то!!!” и многозначительно ухмыляться.

Дабы избежать недопонимания, отметём все лишнее, что было помянуто. Сначала исключим Query Expressions (это from … select…). Они к монадам не имеют ровно никакого отношения. Это только синтаксический сахар, который может быть применен в том числе и к монадным вычислениям (позже об этом вспомним). Вообще любое Query Expressions выражение можно записать в эквивалентной форме в стандартном синтаксисе (чем и занимается компилятор) без потери функциональности. Усугубится только вид выражения, да и то не всегда.

Ленивые вычисления (это я про итераторы IEnumerable<T>) тоже не имеют прямого отношения к монадам. Вместо IEnumerable<TSource> и IEnumerable<TResult> мы могли бы использовать List<TSource> и List<TResult> без потери работоспособности выражения. Разве что оно стало бы менее обобщенным, и позволяло бы работать только со списками. Т.е. IEnumerable<T> тоже левый тип.

Extension method-ы не имеют отношения к монадам. Это всего лишь удобная форма записи вызова функций через точку (как если бы это был метод экземпляра).
Итого: тип IEnumerable<?> заменяю на некий C<?>, чтобы не мозолил глаза. Нам не важно что там за тип, главное что это generic тип. Настолько не важно, что я заменю его сразу на M<?> (позже станет ясно, почему именно M). А так же выкину ключевое слово this и заменю название метода SelectMany на более традиционное Bind (в языке Haskell это будет “>>=”). Вот что получилось:

M<U> Bind<T,U>(M<T> source, Func<T, M<U>> selector);

Мы получили что-то более широкое, чем SelectMany. Я бы сказал, что мы получили целый класс функций, и SelectMany вместе с типом IEnumerable<?> определенно принадлежит к этому классу. Пора, пожалуй ввести определение монады, а после я покажу, близкие к природе SelectMany монады.

Определение монады

Монадой называется тройка (M, Return, Bind) где

• М – одноаргументный generic тип M<T>
• Return – функция, конструирующий экземпляр монадного типа М<T>
• Bind – функция, связывающая монадные вычисления

Более того, тройку должны связывать 3 монадных закона. О них можно почитать в любом материале о монадах, потому я не буду акцентировать на них внимание.

Пожуём немного определение…
Тип M из определения - это тот самый тип M, которым я выше заменил IEnumerable в сигнатуре метода SelectMany. Он называется монадным типом.

Фунция Return – это функция, которая должна сгенерировать экземпляр монадного типа из экземпляра типа T (generic параметра типа M). Так, если нам требуется определить функцию  Return для уже знакомой нам монады (с функцией SelectMany в качестве функции Bind), то она могла бы быть реализованной следующим образом:

IEnumerable<T> Return<T>(T value)
{
    return new T[] { value };
}

Функция Bind связывает монадное вычисление M<T> с монадным результатом М<U> с помощью функции проекции Func<T, M<U>>.

Итого, если мы возьмем определение монады, рассмотрим его в приложении к типу IEnumerable<T>, то тройка (IEnumerable<T>, Return, SelectMany) формально представляет монаду IEnumerable. Выполнение упомянутых монадных законов проверять не будем. Пост и так получился довольно длинным, хотя сложного в этом ничего нет. Заинтригованные читатели смогут проверить выполнение монадных законов сами.

Но тут я ввожу всех в заблуждение. Формально монада называется по названию монадного типа, но монады IEnumerable нет ни в каких анналах. Есть монада List (The List Monad). Так вот, тройка (IEnumerable<T>, Return, SelectMany) – это реализация монады List в .NET платформе.

Итак, после того, как мы узнали, что такое монада, конструкцией SelectMany все еще можно делать разные удобные вещи, какие мы могли делать до того, как узнали, что оно имеет отношение к монадам. Например, можно связывать коллекции с коллекциями и выпрямлять всё в одну коллекцию. Важно отметить, что в результате монадного связывания мы всегда получаем на выходе монадный тип, к которому можно применять связывание и далее.

Рассмотрим более глубокий пример:

var query = 
    from country in countries
    from city in country.Cities
    from street in city.Streets
    select streets;

Eго можно записать в следующей форме:

var query = countries
    .SelectMany(country => country.Cities)
    .SelectMany(city => city.Streets);

Может показаться что эти формы эквивалентны, но это не так. Результаты будут совпадать, но способы их получения разные. Вторая форма записи применяет последовательно SelectMany к результатам, полученным в предыдущих вычислениях. Т.е. сначала берется набор стран, потом SelectMany вычисляет плоскую последовательность всех городов стран, к ней применяется SelectMany, вычисляющий плоскую последовательность улиц всех городов.

Монадные вычисления используют другую стратегию. Для каждой страны находятся улицы  городов страны, а затем улицы городов склеиваются в единую последовательность. Вот как это может выглядеть:

var query = countries.SelectMany(
                country => country.Cities.SelectMany(
                    city => city.Streets));

Или так, если записать в нотации без Extension Methods

var query = SelectMany(countries, country =>
                SelectMany(country.Cities, city => 
                    city.Streets));

Это и есть использование воплощения монады List в C#.
(Театральная пауза)
Вы спрашиваете:

-Это и есть та самая монада? Что делает обычный метод SelectMany монадой?

Я отвечаю:

- Да, это она самая! Выполнение монадных законов наделяет этот метод особенной магией и позволяет вызывать его, получать результат, а потом к результату применять его снова сквозь типы, обстоятельства, время, вытаскивая нужную нам трансформацию из любых глубин!

Наверняка вы пока не разделяете мой восторг, но меня просто прёт!

Монада List, вообще говоря, не самая простая монада из списка стандартных монад. Но вот так получилось, что познакомились мы сперва именно с ней. Тем легче будет перейти к более простым монадам.

Если честно, пытался я постичь более простые монады до понимания сути монады List. Не получалось, т.к. их смысл ускользал от меня. Вам я представлю возможность постичь их смысл через монаду List.

The Maybe Monad

В случае с коллекциями мы уже привыкли к тому, что в каждой коллекции элементов может быть много. Вообразим теперь коллекцию, в которой может быть не более одного элемента. Т.е. либо есть элемент, либо нет ни одного. Третьего не дано. От примера со странами, городами, улицами и домами перейдем к другому примеру:

Программа открывает файл, читает из него строку и ищет в базе данных значение, соответствующее этой строке. Если на каком-то этапе происходит ошибка, возвращается null.

Нет, не нравится. В файле может быть несколько строк, в базе данных может быть несколько значений… Не наш случай. Да и условие задачи стырено отсюда. Так же не очень интересно складывать 5 и Nothing (как здесь).

Возьмем Смерть Кащея! Это есть игла, которая в яйце, которое в утке, утка на сундуке. Дуб, зайцы, селезни, и т.п. – кыш с пляжа! Нам требуется написать программу, которая сможет достать Смерть Кащея, если она там действительно есть, и не сломается, если чего-то не хватает. Т.е. мы не уверены, есть ли сундук, что в сундуке действительно есть утка. Яйцо в утке тоже не факт, что есть. Ну и т.п. Неожиданности вроде двух яиц внутри утки нас не интересуют по условию задачи.

Можем воспользоваться каскадом вложенных if-ов, либо последовательностью выражений if(…==null) return null. Но мы-то тут с монадами знакомимся, а не с if-ами!

Монада List нам почти подходит. Если у сундука есть коллекция уток, у утки коллекция яиц, у яйца коллекция иголок. Можно записать решение в виде последовательного применения SelectMany:

var query = сундуки
    .SelectMany(сундук => сундук.Утки)
    .SelectMany(утка => утка.Яйца)
    .SelectMany(яйцо => яйцо.Иглы);
var смертьКащеяНайдена = query.Any();

Либо в виде монадного связывания:

var query = сундуки.SelectMany(сундук =>
                сундук.Утки.SelectMany(утка =>
                    утка.Яйца.SelectMany(яйцо =>
                        яйцо.Иглы)));
var смертьКащеяНайдена = query.Any();

получилось довольно компактно, но вот вместо коллекций уток, яиц и игл хорошо бы воспользоваться чем-то более простым. Нам не нужны здесь коллекции на самом деле. Тип Nullable<T> подошел бы вместо коллекций, не будь у него ограничения на тип параметра (только структуры). Впрочем, если вся наша предметная область описана структурами, то вполне подойдет.

Введем класс Maybe<T>, который будет устроен в точности как Nullable<T>, но без ограничений на тип T. Я его прямо скопирую из блога Wes Dyer-а вместе с реализацией метода SelectMany и ToMaybe (это аналог нашей функции Return):

class Maybe<T>
{
    public readonly static Maybe<T> Nothing = new Maybe<T>();
    public T Value { get; private set; }
    public bool HasValue { get; private set; }
    Maybe()
    {
        HasValue = false;
    }
    public Maybe(T value)
    {
        Value = value;
        HasValue = /*true;*/ (value != null);
    }
}

public static Maybe<U> SelectMany<T, U>(
     this Maybe<T> m,
     Func<T, Maybe<U>> k)
{
    if (!m.HasValue)
        return Maybe<U>.Nothing;
    return k(m.Value);
}

public static Maybe<T> ToMaybe<T>(this T value)
{
    return new Maybe<T>(value);
}

Я немного модифицировал конструктор типа Maybe, чтобы он мог принимать null-ы и возвращать экземпляр со свойством HasValue равным false (модификация будет работать только с reference типами. Инициализация Maybe Value-типами всегда будет возвращать экземпляр со значением).

Тогда выражение примет вид:

var query = сундук.ToMaybe().SelectMany(сундук => 
     сундук.Утка.ToMaybe().SelectMany(утка => 
         утка.Яйцо.ToMaybe().SelectMany(яйцо => 
             яйцо.Игла.ToMaybe())));
var смертьКащеяНайдена = query.HasValue;

Знакомьтесь – монада Maybe. Связывает каскад вычислений, каждое из которых может окончиться ничем, тогда последующие вычисления не потребуются.

Не уговаривайте меня, что if(сундук.Утка != null) проще чем монада. Я сегодня лишь демонстрирую монаду Maybe, а не склоняю к отказу от if-ов :)

The Identity Monad

Для понимания монады Identity потребуется представить списки с точностью одним обязательным элементом. Можно так же представить тип Maybe с отсутствующим флагом о наличии значения.

Так же нам потребуется упростить задачу о Смерти Кащея: теперь в сундуке есть в точности одна утка, в утке есть яйцо, в яйце есть игла. Никаких неожиданностей.

Вводим тип Identity и соответствующие ему методы (снова спасибо Wes Dyer-у):

class Identity<T>
{
    public T Value { get; private set; }
    public Identity(T value) { this.Value = value; }
}

public static Identity<T> ToIdentity<T>(this T value)
{
    return new Identity<T>(value);
}

public static Identity<U> SelectMany<T, U>(this Identity<T> id, Func<T, Identity<U>> k)
{
    return k(id.Value);
}

Теперь мы можем записать решение с помощью последовательных применений SelectMany:

var query = сундук.ToIdentity()
    .SelectMany(сундук => сундук.Утка.ToIdentity())
    .SelectMany(утка => утка.Яйцо.ToIdentity())
    .SelectMany(яйцо => яйцо.Игла.ToIdentity());
var смертьКащея = query.Value;

Решение задачи о Смерти Кащея с использованием Identity монады будет выглядеть так:

var query =
    сундук.ToIdentity().SelectMany(сундук =>
        сундук.Утка.ToIdentity().SelectMany(утка => 
            утка.Яйцо.ToIdentity().SelectMany(яйцо => 
                яйцо.Игла.ToIdentity())));
var смертьКащея = query.Value;

Решение такой постановки задачи гораздо проще записать без монады:

var смертьКащея = сундук.Утка.Яйцо.Игла;

Впрочем, как сказал автор статьи о монадах на rsdn.ru,

Такая монада находит применение с монадными трансформерами, которые в данной статье не рассматриваются. Будем считать, что это чисто иллюстративный простейший пример.

В отношении Identity монады мне добавить нечего.

Пристегиваем Query Expression (припудрим сахаром)

Внимательный читатель наверняка обратил внимание, что при том что утка, яйцо и игла имеют кол-во экземпляров не более одного, название метода связывания остается “SelectMany”, будто сущностей может быть больше одной. Вот тут пришла пора вспомнить Query Expressions. 

В спецификации языка C# можно найти информацию о том, что Query Expressions может быть смаппирован в функцию со следующей сигнатурой:

C<V> SelectMany<T,U,V>(
    C<T> source,
    Func<T,C<U>> selector,
    Func<T,U,V> resultSelector);

При внимательном анализе можно заметить, что это функция есть более общая форма известной нам Bind (SelectMany), где к значению типа T и результату работы селектора C<U> применяется еще одна функция, возвращающая некоторое значение V, потом с помощью функции Return (ToMaybe) возвращается монадный тип с параметром V. Именно эта функция SelectMany используется компилятором для трансляции Query Expression выражений.
Назначение третьего аргумента выяснить оказалось несложно (покажу чуть позже).
Вот код более навороченной функции SelectMany:

static Maybe<V> SelectMany<T, U, V>(
    this Maybe<T> m,
    Func<T, Maybe<U>> k,
    Func<T, U, V> s)
{
    return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}

Пока примем его на веру. Теперь можно скомпилировать и выполнить следующий код:

static void Main()
{
    var m = from x in 1.ToMaybe()
            from y in 2.ToMaybe()
            from z in 3.ToMaybe()
            select x + y + z;
    Console.WriteLine(m.HasValue);
}

Посмотрев на результат с помощью Reflector-а можно увидеть (отформатировано мной):

Console.WriteLine(
    1.ToMaybe()
       .SelectMany(
           x => 2.ToMaybe(), 
           (x, y) => new { x = x, y = y })
       .SelectMany(<>h__TransparentIdentifier0 => 
           3.ToMaybe(), 
           (<>h__TransparentIdentifier0, z) => 
               ((<>h__TransparentIdentifier0.x + <>h__TransparentIdentifier0.y) + z))
       .HasValue);

Похоже что компилятор преобразовал исходный код так, как если бы он был написан следующим образом:

static void Main()
{
    var m = from x in 1.ToMaybe()
        from y in 2.ToMaybe()
        select new {x, y}
        into t
        from z in 3.ToMaybe()
        select t.x + t.y + z;
    Console.WriteLine(m.HasValue);
}

И дейсвтительно, если посмотреть Reflector-ом на результат компиляции этого выражения, мы увидим

Console.WriteLine(
    1.ToMaybe()
        .SelectMany(
            x => 2.ToMaybe(), 
            (x, y) => new { x = x, y = y })
        .SelectMany(
            t => 3.ToMaybe(),
           (t, z) => ((t.x + t.y) + z))
        .HasValue);

что в точности есть результат предыдущей декомпиляции с точностью до именования идентификатора t.

Внимательно сопоставим выражение QueryExpression с декомпилированным выражением:
from x in 1.ToMaybe() было преобразовано в 1.ToMaybe() и подано первым аргументом первого SelectMany метода.

from y in 2.ToMaybe() было преобразовано в 2.ToMaybe() и подано вторым аргументом первого SelectMany метода. Третьим аргументом стало сопоставление паре (x, y) выражения new { x, y }.

Результатом этих действий будет  new { x, y }.ToIdintity(), который подается на вход второго метода SelectMany. Так же туда подается 3.ToMaybe() и выражение второго select clause.

Таким образом, трехаргументный SelectMany метод подставляется во все выражения from ? in expr, кроме самого первого. Третьим аргументом этого метода становится выражение в select clause, и если такого нет, то оно синтезируется компилятором искусственно. Это не совсем соответствует монадным связываниям выражений, однако на результате сказываться не должно.

Теперь можно делать выводы о том, что же делает супер версия SelectMany и как она реализована. Приведу вариант реализации без использования синтаксиса Extension Method:

static Maybe<V> SelectMany<T, U, V>(
    this Maybe<T> m,
    Func<T, Maybe<U>> k,
    Func<T, U, V> s)
{
    return SelectMany(
        m,
        x => SelectMany(
                k(x),
                y => s(x, y).ToMaybe()));
    //return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}

Внимание! Внешний метод SelectMany (двухаргументный) принимает значение m и лямбда функцию. Если значение m пусто, то внешний метод тут же возвращает Nothing, иначе он подаст m.Value на вход к переданной лямбда-функции и вернет ее результат. В свою очередь лямбда-функция устроена так, что она проверит результат выполнения метода k над первым аргументом. И если он Nothing, вернет Nothing. Иначе вернет результат выполнения метода s над x и y, завернутый в монадный тип Maybe. Итак, в случае наличия значения в m, и наличия значения в результате k(m.Value), выполнится s(m.Value, k(m.Value).Value) и результат обернется в монадный тип Maybe.

Точно так же мы могли бы определить сперва большой трехаргументный метод SelectMany, а потом выразить малый двухаргументный через большой. Возможно читателю будет интересно проделать это самостоятельно.

Ну в общем, надеюсь теперь понятно, почему связывающие методы Bind в C# принято называть “SelectMany”. Это связано с Query Expression паттерном, позволяющим записывать монадные преобразования в удобном синтаксисе. В то же время, мы могли бы малые методы SelectMany назвать и Bind и SelectOne и как-нибудь по другому, ничего бы не изменилось.

Заключение

Надеюсь, что с помощью данного поста удалось выяснить

• что монады не так страшны, как их название
  
• что читатели уже знакомы в какой-то мере с монадными вычислениями (в лице монады List, реализованной в LINQ-е)
  
• что Query Expression связывает с монадами только лишь укороченный синтаксис, который можно пристегнуть к монаде с помощью доопределения более развернутого метода SelectMany (который даже имеет другую форму, нежели монадный Bind).
  
• что существуют другие монады кроме той, что реализована в LINQ-е, и что их можно использовать в языке C# (правда польза монад Maybe и Identity осталась нераскрыта в данном посте)
  

Остались за бортом довольно интересные монады такие как Error, State, Parser, Continuation, Async. По поводу монады Async нужно сказать отдельно. В языке F# она заняла целую нишу, связанную с асинхронными вычислениями, возможно такую же обширную, как монада List в C#. Почитать о ней вместе с другими монадами можно по ссылке [4] (см. ниже).
Не буду обещать, что расскажу о них в ближайшее время, вместо этого предлагаю заинтересовавшимся шагнуть в мир монад самостоятельно, используя следующие ссылки:

Ссылки

1. http://www.rsdn.ru/article/funcprog/monad.xml
2. http://blogs.msdn.com/wesdyer/archive/2008/01/11/the-marvels-of-monads.aspx
3. http://weblogs.asp.net/podwysocki/archive/2008/10/13/functional-net-linq-or-language-integrated-monads.aspx
4. http://blogs.msdn.com/lukeh/archive/2007/08/19/monadic-parser-combinators-using-c-3-0.aspx
5. http://www.haskell.org/all_about_monads/html/index.html

Бесконечное решето Эратосфена

Во время выполнения одного из упражнений учебника по языку Haskell Р. Душкина, меня посетила мысль, что упражнение можно выполнить и на языке C# в духе Haskell.

Упражнение заключалось в реализации функции для получения бесконечного списка простых чисел с помощью алгоритма ”решето Эратосфена”. Надеюсь на то, что автор учебника не обидится на меня за то, что я привел тут решение задачи. Оно же почти в том же виде описано на wikipedia (ссылка выше на решето). Мое же решение отличается от опубликованного лишь тем, что четные числа я вычернкул загодя:

primes :: [Integer]
primes = 2 : sieve [3, 5..]
       where
         sieve (p:ps) = p : sieve [x | x <- ps, x `mod` p > 0]

Нет, я не подглядывал и решение на Haskell в википедии обнаружил уже после того, как решил поделиться мыслями на эту тему. Мысли были примерно следующего характера:

Круто, ведь несколько раз мне приходилось реализовывать решето Эратосфена, и ни разу не пришло в голову реализовать его для бесконечного списка! Всегда требовалось задавать порог-размер решета. Беда даже не в том, что нужен порог, а в том, что нужно его тщательно подбирать для каждой задачи. Слишком малый порог грозит тем, что размера решета не хватит, а слишком большой опасен тем, что приложение будет слишком много времени тратить на ненужный счет.

Впрочем, в C# есть механизмы для работы с бесконечными последовательностями. Ну или почти бесконечными.

Подумал я так, и решил повторить решение на C#:

public static IEnumerable<int> GetPrimes()
{
  yield return 2;
  var sieve = Generate(3, 2);

  while(true)
  {
      var p = sieve.First();
      yield return p;

      sieve = sieve.Where(x => x % p > 0);
  }
}
static IEnumerable<int> Generate(int start, int step)
{
  for (int i = start; ; i += step)
      yield return i;
}

По ходу написания ощутил, что в C# таки нет некоторых инструментов, но в остальном реализация на C# почти полностью соответсвует представленному выше решению на Haskell, потому я решение на Haskell не буду комментировать.

Код на C# вполне рабочий. Первым делом он возвращает 2, затем берет последовательность нечетных чисел больше 2 и на каждой итерации делает следующее: берет первое число p из последовательности и навешивает на последовательность фильтр, выкидывающий все что делится нацело на p.

Итак, отличия этого кода от решения на Haskell.

1. В C# нет типа BigInt (неограниченного целого). Потому решение на C# ограничено типом Int32.
2. В C# нет встроенного генератора бесконечного списка. Enumerable.Range требует ограничителя диапазона и не воспринимает шаг. Впрочем, легко написать свой генератор, что я и сделал.
3. В C# недоступен механизм рекурсии для работы с бесконечными списками. Ну т.е. рекурсия сама по себе есть, но воспользовавшись ей мы получим переполнение стека не дойдя до второго члена последовательности. Потому рекурсивное определение списка пришлось заменить на цикл с изменяемым состоянием. Да, решение на C# императивно. Ну да ладно, хоть состояние изменяемое, но оно невидимое клиенту изменяемое состояние.

Вот, пожалуй, и все отличия, подмеченные мной с первого раза. Все да не все. Что-то заставляет скомпилированный код на C# доставать 1000-е простое число в 5 раз дольше, чем выполняется код на интерпретаторе Haskell!!! Нет, это не шутка. А если попросить Haskell обойтись ограниченным целым (Int32), то он работает в 20 раз быстрее C#-а!!!

Все дело в том, что Haskell на каждой итерации выполняет фильтрацию над хвостом бесконечного списка, а C# выполняет фильтрацию над всей бесконечной последовательностью. Т.е. при поручении очередного элемента каждый раз требуется пройти часть бесконечной последовательности с самого начала, но уже с новыми условиями для фильтрации, которые добавляются на каждой итерации. Далее представлен слегка оптимизированный вариант на C#:

public static IEnumerable<int> GetPrimes1()
{
  yield return 2;
  var sieve = Generate(3, 2);

  Func<int, bool> predicate = x => true;

  while (true)
  {
      var p = sieve.First();
      yield return p;
      predicate = predicate.And(x => x % p > 0);

      sieve = Generate(p, 2)
          .Where(predicate);
  }
}

static Func<T, bool> And<T>(this Func<T, bool> p1, Func<T, bool> p2)
{
  return t => p1(t) && p2(t);
}

Теперь последовательности не просматриваются каждый раз сначала, вместо этого на каждой итерации генерируется новая последовательность нечетных чисел и на нее накладываются фильтры, которые пришлось накопить в локальной переменной. Здесь можно заметить что накапливать можно не условия фильтрации, а сами простые числа, которые можно подставить в неизменное условие фильтрации.

public static IEnumerable<int> GetPrimes2()
{
  yield return 2;
  var primes = new List<int> {2};
  var sieve = Generate(3, 2);

  Func<int, bool> predicate = x => primes.All(p => x % p > 0);

  while (true)
  {
      var p = sieve.First();
      yield return p;
      primes.Add(p);

      sieve = Generate(p, 2)
          .Where(predicate);
  }
}

Впрочем, последние две версии решета на C# уже уверенно обгоняют интерпретатор Haskell-а. Вот только оригинальное решето Эратосфена они напоминают лишь отдаленно. И сильно смахивают на проверку делением на предварительно найденные простые числа. Следующее решение на языке F#:

let primes =
  let gen n = seq { n..2..System.Int32.MaxValue }
  let f (sieve, filter) =
      let p = sieve |> Seq.filter filter |> Seq.hd
      Some(p, (gen p, (fun x -> filter x && x % p > 0)))
  Seq.unfold f (gen 3, (fun _ -> true))
  |> Seq.append [2]

Оно больше всего соответствует варианту GetPrimes1() на C#, хотя написано без явно изменяемого состояния. В библиотеке F# имеется тип для представления больших целых, но я им здесь не воспользовался.

Выводы

Хоть .NET и имеет средства для работы с бесконечными последовательностями, но к сожалению, пользоваться ими далеко не так удобно, как могло бы быть. Но основная мысль не об этом. Мое знакомство с Haskell-ем, пока еще поверхностное, позволило по новому взглянуть на известные ранее алгоритмы и инструменты.