четверг, 30 апреля 2009 г.

Вывод типов с помощью Fake функций

Рассмотрим один прием, помогающий выводить типы (на авторство не претендую) на примере мемоизации. В двух словах, если кто не вкурсе, мемоизация – это техника оптимизации (подвид кэширования), используемая для избежания вызовов функций с повторяющимися аргументами. Множество примеров реализации мемоизации на C# можно найти здесь. Оттолкнемся от мемоизации функции одного аргумента, описанного Wes Dyer-ом, одним из разработчиков компилятора C#.

public static Func<TKey, TResult> Memoize<TKey, TResult>(this Func<TKey, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new Dictionary<TKey, TResult>();
 TResult result;

 return key => (cache.TryGetValue(key, out result))
     ? result
     : (cache[key] = func(key));
}
Мой вариант отличается только тем, что я переменную result внес в замыкание вместо того, чтобы объявить ее внутри тела возвращаемой функции. Сделал я это только для того, чтобы не писать фигурные скобки в определении тела функции. Все красиво и наглядно, но допустим возникла необходимость мемоизации функции двух переменных.
Мемоизация функции двух аргументов
Решать можно по-разному. Например, модифицировать реализацию мемоизации функции одной переменной, т.е. фактически переписать ее заново:
public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var cache = new object[0].ToDictionary(
     x => new { k1 = default(T1), k2 = default(T2) },
     x => default(TResult));

 return (k1, k2) =>
 {
     TResult result;
     var key = new { k1, k2 };

     return (cache.TryGetValue(key, out result))
         ? result
         : (cache[key] = func(k1, k2));
 };
}
Здесь я воспользовался тем, что анонимный тип, который генерируется компилятором обладает всем необходимым для того, чтобы использовать его в качестве ключа словаря. Небольшая сложность заключалась в том, чтобы объявить переменную словаря с анонимным типом ключа, но выручил метод Enumerable.ToDictionary. Но душа захотела реюза описанного ранее метода мемоизации функции одного аргумента. Мне пока известно два способа сделать реюз:
  1. Применить последовательно мемоизацию к каждому аргументу, что привлечет к появлению множества экземпляров словарей (не интересно для дальнейшего обсуждения)
  2. Применить мемоизацию к методу, который принимает аргумент-комбинацию двух аргументов, а возвращает результат вызова метода func, полученный по соответствующей паре аргументов. Далее будем обсуждать метод этот вариант.
Итого, требуется применить мемоизацию к следующему методу (записанному условно):
Func<?, TResult> func2 = (? x) => func(x.t1, x.t2);
Проблема здесь в том, что комбинированный аргумент представлен анонимным типом, указать который проблематично. Стандартных Tuple-ов нет, да и неизвестно, будут ли они обладать теми же свойствами, что и анонимные типы, будет ли возможность использовать их в качестве ключа словаря?

Итого, есть метод с сигнатурой Func<?, TResult>, записать тело которого мы можем, но не можем сказать компилятору, что за тип кроется за знаком “?” (достаточно было бы указать тип хотя бы в одном из мест, отмеченных знаком “?” в определении анонимного метода).

Вот тут-то и выручит нас метод, который ничего не делает:
static Func<T, TResult> MakeFunc<T, TResult>(T _, Func<T, TResult> func)
{
 return func;
}
Метод MakeFunc абсолютно бесполезен во времени выполнения. Однако он помогает вывести тип “?”. Записать этот тип в коде мы все равно не сможем, но это и не требуется.

Вот как компилятор теперь может выявить тип метода: первым аргументом MakeFunc мы указываем экземпляр анонимного типа, а т.к. тип T первого аргумента совпадает с типом аргумента метода Func<T, TResult> второго аргумента метода MakeFunc, то компилятор теперь знает, что подразумевается под типом T в выражении Func<T, TResult>.

Теперь следующее выражение
var func2 = MakeFunc(
 new { A1 = default(T1), A2 = default(T2) },
 x => func(x.A1, x.A2));

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

public static Func<T1, T2, TResult> Memoize<T1, T2, TResult>(this Func<T1, T2, TResult> func)
{
 if (func == null)
     throw new ArgumentNullException("func");

 var func2 = MakeFunc(
     new { A1 = default(T1), A2 = default(T2) },
     x => func(x.A1, x.A2));

 var func2m = func2.Memoize();

 return (t1, t2) => func2m(new { A1 = t1, A2 = t2 });
}
Здесь находится топик обсуждения мемоизации функции двух аргументов на RSDN (автор – я). Обратите внимание, как легко и изящно решается проблема на языке F#. Вышеописанный метод производит мемоизацию функции аргумента анонимного типа, затем возвращает метод, комбинирующий аргументы в анонимный тип, и передающий экземпляр анонимного типа в мемоизированную функцию.
Вообще говоря, я не думаю, что кому-то из читателей пригодится мемоизация функции двух и более аргументов… Пост немного о другом (как следует из его названия). Пост о том, как можно помочь компилятору вывести необходимый тип, в котором каким-то образом участвуют анонимные типы.
Потому еще один пример, где описанный мной прием может пригодитсья:
Вывод типа IEqualityComparer<?> для анонимного типа.
Преамбула проста: когда-то не так давно я решил, что если не заморачиваться на эффективности, то можно не писать классы компареров каждый раз, а создать адаптер, который бы принимал функции GetHashCode и Equals и представлял бы их экземпляром IEqualityComparer<T>. Выглядит это чудо так:
public static IEqualityComparer<T> CreateAdapter<T>(
 Func<T, T, bool> equals,
 Func<T, int> getHashCode)
{
 if (equals == null)
     throw new ArgumentNullException("equals");

 if (getHashCode == null)
     throw new ArgumentNullException("getHashCode");

 return new EqualityComparerAdapter<T>(equals, getHashCode);
}

class EqualityComparerAdapter<T> : IEqualityComparer<T>
{
 readonly Func<T, T, bool> _equals;
 readonly Func<T, int> _getHashCode;

 public EqualityComparerAdapter(Func<T, T, bool> equals, Func<T, int> getHashCode)
 {
     _equals = equals;
     _getHashCode = getHashCode;
 }

 public bool Equals(T x, T y)
 {
     return _equals(x, y);
 }

 public int GetHashCode(T obj)
 {
     return _getHashCode(obj);
 }
}
Между делом – довольно удобная штука, позволяющая экономить на описании класса, но не в случае когда тип T – анонимный. Вот такой вспомогательный метод
static IEqualityComparer<T> InferComparer<T>(
 T _,
 Func<T, T, bool> equals,
 Func<T, int> gethashCode)
{
 return CreateAdapter(equals, gethashCode);
}
позволяет вывести тип компарера для анонимного типа.
var pairComparer = InferComparer(
 pair,
 (x, y) => x.Key.SequenceEqual(y.Key),
 x => x.Key.Aggregate(0, (h, s) => h ^ s.GetHashCode()));
Эта конструкция создает IEqualityComparer для анонимного типа, свойство Key которого является коллекцией строк. Таким образом сравниваются экземпляры по совпадению коллекций строк, и хэшкод вычисляется по набору строк свойства Key анонимного типа. Далее этот компарер используется для построения словаря.

Комментариев нет:

Отправить комментарий