Недавно наткнулся на примеры реализации паттерн-матчинга Антона Оникийчука (лидер spbalt.net). Понятное дело что подобные вещи достаточно просто реализуются в F#, но вот на C# сделать посложнее. Что же, посмотрим во что это выльется.
Первая попытка
Итак, что такое pattern-matching? Можно начать с того, что это более умный switch который, при полной реализации, умеет намного больше. При этом, паттерн-матчинг применяется к различным типам, но “специальным” типом для него является список (или посделовательность, неважно), т.к. именно для списков используются list comprehensions. Но давайте не будем забегать вперед.
Итак, реализация Антона предлагает нам сделать fluent interface, с помощью которого каждый кейс обрабатывается как некий предикат. Например:
private int year;
public int Year {
get {
return year;
}
set
{
value.Match(v => v < 0, y => {throw new Exception("BCE not supported");})
.Match(v => v > DateTime.Now.Year,
y => {throw new Exception("Future years not supported");})
.Match(v => true, y => {year = y;});
}
}
Тут наверное понятно откуда взялся Match() – его реализация примитивна:
public static T Match<T>(this T target, Predicate<T> predicate,
Action<T> whenMatched)
{
if (predicate(target))
whenMatched(target);
return target;
}
Вообще-то, то что мы сейчас реализовали – это поддержка ключевого слова when. А как же поддержка значений напрямую? Это просто:
public static T Match<T>(this T target, T value, Action<T> whenMatched)
{
if (target.Equals(value))
whenMatched(target);
return target;
}
Теперь уже можно писать year.Match(0, throw new Ex("There is no 0 year")) или что-то в этом духе. Еще один интересный аспект мэтчинга – это когда нужно сделать проверку на несколько значений. Например, если год равен 666 или 1666 – бить тревогу. А вот это уже сложнее, т.к. нам не подставить params предпоследним аргументом – компилятор не даст.
Элегантного решения этой проблемы вообще не существует – разве что если T имеет тип char (тогда можно передать строку). В обобщенном случае, можно банально передавать массив. Сам метод расширения будет брать IEnumerable<T>:
public static T Match<T>(this T target, IEnumerable<T> values, Action<T> whenMatched)
{
foreach (var t in values.Where(v => v.Equals(target)))
whenMatched(t);
return target;
}
и использоваться вот так:
value.Match(v => v < 0, y => {throw new Exception("BCE not supported");})
.Match(v => v > DateTime.Now.Year,
y => {throw new Exception("Future years not supported");})
.Match(0, y => {throw new Exception("There is no year Zero");})
.Match(new[]{666, 1666}, y => {throw new Exception("Bad year!");})
.Match(v => true, y => {year = y;});
Фундаментальным вопросом остается то, что возвращает Match<T> – а примере Антона, идет возврат значения, т.е. вместо Action<T> принимается Func<T,U>, где U – тип результата. Это создает определенные проблемы т.к. исключения явно не типа U, и тем самым приходится заниматься организацией их перехвата.
Вариадичность
У нас в паттерн-матчинге есть, условно говоря, две ситуации – в одной используется list comprehension (т.е. проверка элементов списка, последовательности, и т.п.), в другой – все остальное. Мы уже посмотрели на то, как можно реализовать ПМ для простых типов, давайте теперь посмотрим на то, как сделать то же самое для списков.
Для начала, придется признать что нужны будут перегрузки. Точно так же как Func<T,...> имеет вариаций этак 16, нам потребуется аналогичные фичи вместо Predicate<T>. Естественно, для обработчика так же потребуются 16 вариаций Action<T>. И естественно, это задача для кодогенерации (кто сказал что кодогенерация это nuclear option?)
Давайте посмотрим как будет выглядеть мэтчинг для 3х аргументов:
public static IEnumerable<T> Match<T>(this IEnumerable<T> target,
Func<T,T,T,bool> predicate,
Action<T,T,T> whenMatched)
{
if (target.Count() >= 3) {
var values = target.Take(3).ToArray();
if (predicate(values[0], values[1], values[2]))
whenMatched(values[0], values[1], values[2]);
}
return target;
}
Тут неважно чем пользоваться – Linq или напрямую брать Enumerator и обходить, особой погоды это (наверное) не сделает. Вот типичное использование:
public string processList(IEnumerable<int> list)
{
string result = string.Empty;
list.Match((a,b,c) => ( a == b && b == c ),
(a,b,c) => {result = "First 3 elements identical";});
return result;
}
Замечу что мы все еще не научились делать из этих методов возвращаемые значения, но сделать это “правильно” невозможно в принципе – единственный вариант это когда вместо IEnumerable<T> в цепочке появляется некий контейнер который агрегирует IEnumerable<T> а также некую переменную Result, которую потом придется возвращать вручную, т.к. никакого приведения вроде implicit operator U тут не получится (не верите – попробуйте).
А где же хвост, пустой список, и т.п.?
Очень хочется показать реальный пример, поэтому постараюсь ‘закрыть’ еще пару проблем прежде чем переходить к примеру. Во-первых, мы не умеем делать мэтчинг на пустой список []. Эта проблема решается просто – мы используем старую реализацию, которая не заточена под IEnumerable:
public string processList(IEnumerable<int> list)
{
string result = string.Empty;
list.Match((a,b,c) => ( a == b && b == c ),
(a,b,c) => {result = "First 3 elements identical";})
.Match((l => !l.Any()), l => {result = "Empty list";});
return result;
}
Теперь что касается ‘хвоста’. Поскольку мы используем не LinkedList<T> а IEnumerable<T>, рекурсивная обработка наверное должна выглядет вот так:
public void processList(IEnumerable<int> list, IList<int> result)
{
list.Match((a,b,c) => (a == b && b == c),
(a,b,c) => { result.Add(a);
processList(list.Skip(3), result); }
}
Мораль в том, что это безобразие будет порождать миллион новых перечислений, которые наверняка откушают много памяти и CPU. Использование связанного списка – пожалуй единственное решение данной проблемы.
Еще одну вещь которую пришлось сделать – это эксклюзивность кейсов в мэтчинге (раньше об этом как-то не подумал). Для этого в цепочку вклинивается null и везде делаются проверки.
Финальный пример
Рассмотрим ситуацию, в которой нам нужно обходить строку, и заменять некоторые символы – например менять --> на -->. Как это будет выглядеть? Сразу скажу – достаточно кошмарно. Во-первых, мы делаем метод для перевода строки в LinkedList<char>:
public static LinkedList<char> ToList(this string target)
{
return new LinkedList<char>(target.ToCharArray());
}
Также нам нужен будет метод для передвижения по списку:
public static LinkedListNode<T> Move<T>(this LinkedListNode<T> list, int steps)
{
var p = list;
while (steps --> 0)
p = p.Next;
return p;
}
Теперь нужны обработчики для списка (да-да, 16 или сколько там), которые во-первых умеют общаться с LinkedList<T>, а во-вторых знают что при “провале” нужно возвращать именно null:
public static LinkedListNode<T> Match<T>(this LinkedListNode<T> target,
Func<T,T,T,bool> predicate,
Action<T,T,T> whenMatched)
{
if (target != null && target.Next != null && target.Next.Next != null)
{
var a = target.Value;
var b = target.Next.Value;
var c = target.Next.Next.Value;
if (predicate(a,b,c)) {
whenMatched(a,b,c);
return null;
}
}
return target;
}
Самое время начать использовать Boo :) Тем временем, у нас появляется “оберточный” метод для обработки строки:
public string processString(string input)
{
var sb = new StringBuilder();
var list = input.ToList();
processString(list.First, sb);
return sb.ToString();
}
Это, опять же, еще один минус отсутствия полноценных вложенных функций. Можно было создать делегат, но я поленился. Ну а теперь – самое главное – реализация нашего примитивного алгоритма:
private void processString(LinkedListNode<char> first, StringBuilder result)
{
first.Match(
(a,b,c) => (a == '-' && b == '-' && c == '>'),
(a,b,c) => { result.Append("-->");
processString(first.Move(3), result); })
.Match(c => c == null, c => {})
.Match(c => c != null, c => { result.Append(c.Value);
processString(first.Next, result);});
}
Тут есть что поизучать и пооптимизировать. Но все равно вид сего достаточно кошмарен хотя, конечно, все работает :)
Заключение
Попытка вклинить стороннюю фичу в язык который ее не поддерживает нативно – задача достаточно болезненная, и как по мне так особого value в программу она не превносит. Более того, есть огромное количество накладных расходов связаных с конверсией в LinkedList<T> – ведь насколько я понимаю, каждая буква в моем примере превратилась бы в LinkedListNode<char>. Если учесть средней размер статьи (10,000 символов), то сразу как-то становится не по себе.
Так или иначе, надеюсь что это пример показал как можно сделать что-то a la паттерн мэтчинг/list comprehension в C#. Хотя, опять же, программирование в стиле С (использование switch, for и т.п.) тоже работает весьма неплохо.
Dmitri Nesteruk 
Оставить комментарий