Карри для чайников

Вступление

Концепции функционального программирования не так сложны, но иногда немного абстрактны. В этом посте я попытаюсь объяснить концепцию каррирования, или, проще говоря, частичное применение функции. Если вы задаетесь вопросом, откуда взято название «карри», оно названо в честь Хаскелла Карри, одного из творческих умов, стоящих за функциональным программированием, и, действительно, как следует из названия, оно придает довольно острый вкус функциональному программированию. Честно говоря, карри не был изобретен Хаскеллом Карри; Сам Хаскелл приписал эту технику Шёнфинкелю, хотя другой математик Фреге также использовал ее в то время (в эпоху, предшествовавшую Интернету, нередко разные люди имели одну и ту же идею независимо друг от друга, не зная работы друг друга в в режиме реального времени).

Говорящая бета

Итак, о чем все это? В лямбда-исчислении одним из основных правил работы с функциями является так называемое бета-преобразование. Это не более чем причудливое название для приложения-функции Предположим, у вас есть функция «add», похожая на:

λ ab. а + б

Каждый символ между символом λ и символом. действует как параметр для функции, в то время как тело функции указывается справа от синтаксиса .. В C # 3.0 это будет выглядеть следующим образом (игнорируя тот факт, что приведенное выше выражение является нетипизированным и принимая int для обоих параметров):

( int a, int b) => a + b

Бета-преобразование позволяет нам применять функцию следующим образом:

(λ ab. a + b) 1 2

который левоассоциативен:

(((λ ab. a + b) 1) 2)

и осуществляется путем формальной замены. Оценка внутренней части сначала выглядит так (параметр «связывание» подчеркнут):

(((λ a b. a + b) 1 ) 2)

Это означает, что мы можем заменить 1 в теле функции следующим образом:

((λ б. 1 + б) 2)

Теперь во внутренних скобках осталась новая функция, которая принимает один оставшийся аргумент:

λ б. 1 + б

Это основная идея карри. Возвращаясь к C # 3.0, это означало бы, что мы сможем написать что-то вроде:

Func<int, int, int> add = (int a, int b) => a + b;
Func<int, int> addOne = add(1);

Но мы не можем. Компилятор будет жаловаться на вторую строку, сообщая нам, что делегат не принимает один аргумент. Другими словами, язык (в отличие, например, от F #) не поддерживает каррирование. Тем не менее, я все еще хочу показать вам, как такая функция будет работать концептуально, убрав наши лямбда-выражения из языка и переключившись на деревья выражений.

Простой подход

Так как же нам добиться построения образца карри в C # 3.0? Есть разные подходы на самом деле. Один из способов сделать это — взять исходную лямбда-функцию и «вызвать» ее с предоставленными параметрами, оставив остальные параметры на месте. Другими словами, мы едим определенные параметры в голове и оставляем там остальные параметры хвоста. Давайте предположим, что нам дан экземпляр LambdaExpression с любым телом, о котором вы можете мечтать. Чтобы сделать это конкретным, рассмотрим это лямбда-выражение:

( int a, int b) => Добавить (a, b)

Вот соответствующий код, который сгенерирует компилятор, если вы назначите приведенное выше выражение переменной с типом Expression <Func <int, int, int >> (здесь часть Expression <T> имеет огромное значение и говорит компилятору генерировать дерево выражений в отличие от анонимного метода):

ParameterExpression a = Expression.Parameter(typeof(int), “a”);
ParameterExpression b = Expression.Parameter(typeof(int), “b”);
Expression<Func<int, int, int>> e = Expression.Lambda<Func<int, int, int>>(
Expression.Call(null, typeof(Operators).GetMethod(“Add”), a, b),
a, b
);

Учитывая этот объект выражения и набор значений параметров, которые должны быть применены, мы хотим создать новое лямбда-выражение с меньшими (то есть оставшимися) параметрами. Давайте сделаем шаг назад и придумаем обобщенную подпись для карри:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters);

То, что мы могли бы сделать сейчас, довольно наивно, — это взять исходное лямбда-выражение и обернуть его в выражение InvocationExpression, передав в него предоставленные параметры (избавляясь от «съеденных» лямбда-параметров) и оставшиеся лямбда-параметры и превратив это тело в новое лямбда-выражение, которое все еще имеет оставшиеся лямбда-параметры. Больше слов, чем строк кода, вот как это будет выглядеть, используя некоторые операторы LINQ to Objects:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters)
{
    ParameterExpression[] lambdaParams = func.Parameters.Skip(parameters.Count).ToArray();
    return Expression.Lambda(Expression.Invoke(func, parameters.Concat(lambdaParams)), lambdaParams);
}

В формате «ToString» оригинальная лямбда будет выглядеть так:

(a, b) => Добавить (a, b)

и при применении карри так:

LambdaExpression add1 = Curry((int a, int b) => Add(a, b), Expression.Constant(1));

результат выглядит так:

b => Invoke ((a, b) => Добавить (a, b), 1, b)

Сигнатура определенно верна, в результате получается функция только с одним оставшимся аргументом, но тело выглядит как ад (представьте, как это будет выглядеть, если вы каррируете 1 аргумент за раз для функции с 10 аргументами). Кроме того, параметр «b» является немного особенным (оставлено читателю, чтобы подумать немного больше). Вместо этого мы хотели бы видеть более простую форму, которая действительно иллюстрирует формальную замену, получая это:

b => Добавить (1, б)

Формальная замена

Пришло время переключить передачи и перейти от быстрого и грязного решения выше к лучшему решению, которое выполняет реальную замену. Как мы можем достичь этого? Первое, что нам нужно знать, это то, что деревья выражений неизменны. Нет возможности изменить их, мы можем создавать только новые. Это именно то, что нам нужно сделать здесь: учитывая дерево выражений для лямбда-выражения, взять его тело и клонировать его, но при этом заменить набор заданных параметров (которые будут экземплярами ParameterExpression) их соответствующими значениями подстановки. Теперь нам нужно знать, как клонировать дерево выражений, переписывая при этом определенные части. Ответ на этот вопрос — посетитель дерева выражений, и да, у нас есть один на MSDN по адресу http://msdn.microsoft.com/en-us/library/bb882521.aspx, То, что делает этот фрагмент кода, это просто рекурсивно обходить дерево выражений, и для каждого узла он вызывает виртуальный метод (который мы поэтому можем переопределить), который имеет поведение new’ing до нового экземпляра выражения, имеющего те же значения , На самом деле, ParameterExpressions являются забавным исключением из этого правила, поскольку они действуют как ссылочные заполнители для параметров, и их равенство необходимо для работы этих ссылок (поэтому вы найдете просто «return p» в VisitParameter). В любом случае, чтобы использовать посетителя, нам нужно наследовать его и предоставить желаемое поведение:

class CurryVisitor : ExpressionVisitor
{
    private Dictionary<ParameterExpression, Expression> _parameters;

    public CurryVisitor(Dictionary<ParameterExpression, Expression> parameters)
    {
        _parameters = parameters;
    }

    protected override Expression VisitParameter(ParameterExpression p)
    {
        if (_parameters.ContainsKey(p))
            return _parameters[p];

        return base.VisitParameter(p);
    }

    public Expression Clone(Expression exp)
    {
        return base.Visit(exp);
    }
}

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

LambdaExpression Curry(LambdaExpression ex, params Expression[] parameters)
{
    if (parameters.Length > ex.Parameters.Count)
        throw new InvalidOperationException("Too many parameters specified.");

    var assignments = new Dictionary<ParameterExpression, Expression>();

    for (int i = 0; i < parameters.Length; i++)
    {
        ParameterExpression parameter = ex.Parameters[i];
        Expression value = parameters[i];

        if (!parameter.Type.IsAssignableFrom(value.Type))
            throw new InvalidOperationException("Incompatible parameter value type for parameter " + parameter.Name);

        assignments[parameter] = value;
    }

    var visitor = new CurryVisitor(assignments);
    return Expression.Lambda(visitor.Clone(ex.Body), ex.Parameters.Skip(parameters.Length).ToArray());
}

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

Вот пара примеров:

    Expression<Func<int, int, int, int>> add = (a, b, c) => a + b + c;
    Console.WriteLine(add);
    Console.WriteLine(Curry(add, Expression.Constant(1)));

    Expression<Func<Func<int, int, int>, int, int, int>> binOp = (f, a, b) => f(a,b);
    Expression<Func<int, int, int>> binAdd = (int a, int b) => a + b;
    Console.WriteLine(binOp);
    Console.WriteLine(Curry(binOp, binAdd));

    Expression<Func<int, int>> d = a => a + a;
    Console.WriteLine(d);
    Console.WriteLine(Curry(d, Expression.Constant(1)));

и вот соответствующий вывод:

Curry(binOp, binAdd).Compile().DynamicInvoke(1, 2); // produces 3