Functional Programming For Dummies: Лямбда функции и каррирование

необходимо

А кто так говорит? Можно и без них обойтись.

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

По-моему эти вещи мало связаны друг с другом.

По-моему эти вещи мало связаны друг с другом

В плане использования - да, в плане реализации - нет. Каррирование реализуют через лямбды же.

для короткой функции-аргумента

Интереснее когда функция возвращается как результат из функции и при этом замыкает свой контекст, так что уже не может лежать на стеке. А передавать указатели на функции как аргументы другим функциям можно и в си, просто все «анонимные» функции нужно явно расписать и дать им названия (в gcc ещё есть вложенные функции).

Видел, что карирование часто используется в хаскеле. Из-за строгого hlint это чуть ли не необходимость. В других языках карирование встречается намного реже на мой взгляд, и оно не является уже столь необходимым. Ну, разве что, в скале свертка реализована почему-то через карирование (один фиг, передается параметром еще одна лямбда, а значит, алокатор все равно не будет спать), но вполне могли обойтись и без этого.

Еще карирование часто используется в F# с оператором (|>), но он инлайнится, а потому накладные расходы меньше. В этом уже больше красоты, чем действительно реальной необходимости.

Карирование есть и в лиспе через библиотеку, но там, вероятно, оно используется редко.

А вот лямбды используются повсеместно, и для чего они только не используются.

лямбда-функции

Большая часть их использования - это пара к функциям типа map или fold. Вторая возможность - это использование лямбд, как возвращаемых значений у функций (высших порядков) для того, чтобы поменять поведение кода.

Как пример можно привести обработчик callback'а, которому передают лямбду возвращаемую некоторой функцией.

каррирование

Не более чем сахар для работы с лямбдами, чтобы не писать что-то типа таких простыней:

let foo (x) =
    fun y -> x+y

а писать так:

let foo x y = x+y

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

Например

map (+ 1) [1 .. 10]
filter (x ==) ys

частичное применение (+) и (==) за счёт их каррированности как раз. Частичное применение - часто можно встретить. Ещё это способствует pointfree, но это более редкая вещь.

Аналог каррирования есть даже в С++ (можно сделать через boost::bind). Вот простой жизненный пример из одной моей лабы (язык - Maple):

# Задаём некое отображение, зависящее от нескольких параметров 
# a, A, omega. Это делается с помощью лямбда функции, кстати.
ballMap:=(a, A, omega, x, psi)->
  (
     evalf(  x+a*sin(2*psi)  )
    ,evalf(  angle(psi+2*arctan( -A*omega*sin(omega*x)))  )
  );

ballIterate:=proc(a, A, omega, x0, psi0, N)
  local f;
# Каррирование. Создаём функцию отображения с параметрами 
# a,A,omega из контекста функции ballIterate 
  f:=curry(ballMap, a, A, omega);
  [
    seq
    (
# Применяем f i раз к начальным условиям
      [(f@@i)(x0, psi0)]
     ,i=1..N
    )
  ];
end proc;

Вот пример использования лямбда-функции на Maple: из двух списков сделаем список пар:

l1:=[1,2,3];
l2:=[a,b,c];
zip( (a,b)->[a,b], l1, l2 );

Вывод: [[1, a], [2, b], [3, c]]

Не более чем сахар для работы с лямбдами

Если каррировать функцию от n аргументов, то получится функция из которой, путём частичных применений, строится n разных функций, с использованием разных комбинаторов, вроде flip, - вплоть до 0! + 1! + ... + n!.

И к чему ты это сказал то? Я вообще не о том говорил.

Что-то я не вижу здесь каррирования. Сигнатуры всех функций напиши. И что за язык.

F# это. Cигнатура 'X -> 'X -> 'X.

Работать это будет так (для обеих функций):

let f2 = foo 2
f2 3
5

Не нужны. Необходимо никогда не использовать.

Ну ладно, в крайнем случае - так, как в шарпе, для callback-ов. Но лучше все же анонимные классы в Java.

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

А теперь напиши на листочке такую штуку X->(Y->(Z->H)) и думай, что есть каррирование.

А, да, нужно ещё вспомнить, что функция - это отображение одного множества в другое множество (не обязательно отличное от исходного).

Если запись

foo x y = x + y

даёт

foo : Integer -> (Integer -> Integer)

а не

foo : Integer x Integer -> Integer

то есть определяется каррированная функция, то у нас из foo автоматом образуется

foo
foo x
flip foo
flip foo y

0! + 1! + 2! = 4 функций. Или для fold:

fold
fold f
fold f z
flip (fold f)
flip (fold f) xs
flip fold
flip fold z
flip fold z f
flip (flip fold z)
flip (flip fold z) xs

0! + 1! + 2! + 3! = 10 функций (если я правильно считаю).

Сахар для лямбд и сахар для частичных аппликаций предполагаются. Но, может быть, это и не сахар, а основа, вокруг которой уже «нормальные» лямбды и аппликации - сахар. Зависит от предпочтений при выборе ядра языка. Реализация тоже предполагается.

Я сразу понял о чём ты, вопрос в другом: ты думаешь я этого не понимаю? А если я всё это прекрасно понимаю, то зачем ты мне это расписываешь, что я должен увидеть то?

ты думаешь я этого не понимаю?

Ну, я не знаю :)

А если я всё это прекрасно понимаю, то зачем ты мне это расписываешь, что я должен увидеть то?

По крайней мере теперь мы этот момент прояснили.

А, кажется понял. Имелось в виду, что краткая запись ведёт себя точно так же как и более вербозная, так как функции в F# каррированны по умолчанию, их можно частично применять образуя много новых функций и т.п. Прямо как в хаскеле.

0! + 1! + 2! + 3! = 10 функций (если я правильно считаю).

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

Именно, а для связи с сишарповскими функциями используется передача параметров в виде кортежей :)

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

Не более чем сахар для работы с лямбдами, чтобы не писать что-то типа таких простыней:

Имхо, большего знать не нужно, пока сам не увидишь, что такое нужно в коде применить.

Логика мне подсказывает, что реализация всех функций не делается

Для каррированной fold, например, по крайней мере первые n - 1 (= 2) функций постоянно строятся динамически при каждом частичном применении, то есть всякий раз как в коде будут частичные (fold f) и (fold f z). Фишка в том, что все остальные функции из этой суммы строятся так же динамически с помощью частичных применений и flip-подобных комбинаторов. То есть, если обычная некаррированная функция задаёт строго одну функцию, то каррированная - сразу много функций (много реализаций не нужно, частные случаи получаются автоматически), проблема только в том чтобы эффективно реализовать карринг.

Пример с немножко обобщённым обходом дерева на си:

#include <stdio.h>
#include <stdlib.h>

struct node {
    int number;
    struct node *left, *right;
};

void gen_tree(struct node *node, unsigned level)
{
    if (node && level > 0) {
        struct node *left = calloc(1, sizeof(struct node));
        struct node *right = calloc(1, sizeof(struct node));
        left->number = rand();
        right->number = rand();
        node->left = left;
        node->right = right;
        gen_tree(node->left, level - 1);
        gen_tree(node->right, level - 1);
    }
}

void free_tree(struct node *node)
{
    if (!node) return;
    free_tree(node->left);
    free_tree(node->right);
    free(node);
}

typedef void(node_action)(struct node*, void*);

struct ctx {
    int level;
};

void sub_traverse(struct node *node, node_action action, struct ctx ctx)
{
    if (!node) return;
    ctx.level++;
    sub_traverse(node->left, action, ctx);
    action(node, (void*)(&ctx));
    sub_traverse(node->right, action, ctx);
}

void traverse(struct node *node, node_action action)
{
    struct ctx ctx = { -1 };
    sub_traverse(node, action, ctx);
}

void do_even(struct node *node, void *ctx_)
{
    struct ctx *ctx = ctx_;
    if (!(node->number % 2))
        printf("level %d: even %d\n", ctx->level, node->number);
}

void do_odd(struct node *node, void *ctx_)
{
    struct ctx *ctx = ctx_;
    if (node->number % 2)
        printf("level %d: odd: %d\n", ctx->level, node->number);
}

void traverse_even(struct node *node)
{
    traverse(node, do_even);
}

void traverse_odd(struct node *node)
{
    traverse(node, do_odd);
}

int main(void)
{ 
    struct node *root = calloc(1, sizeof(struct node));
    gen_tree(root, 3);
    traverse_even(root);
    traverse_odd(root);
    free_tree(root);
    return 0;
}

С вложенными функциями gcc sub_traverse и traverse упрощаются:

void traverse(struct node *node, node_action action)
{
    void sub_traverse(struct node *node, int level) {
        if (!node) return;
        sub_traverse(node->left, level + 1);
        struct ctx ctx = { level };
        action(node, (void*)(&ctx));
        sub_traverse(node->right, level + 1);
    }
    sub_traverse(node, 0);
}

С простыми лямбдами-аргументами можно do_odd и do_even заменить анонимными функциями (далее везде псевдокод):

void traverse_even(struct node *node)
{
    traverse(node, fun (struct node *node, void *ctx_) {
            struct ctx *ctx = ctx_;
            if (!(node->number % 2))
                printf("level %d: even %d\n", ctx->level, node->number);
        });
}

void traverse_odd(struct node *node)
{
    traverse(node, fun (struct node *node, void *ctx_) {
            struct ctx *ctx = ctx_;
            if (node->number % 2)
                printf("level %d: odd: %d\n", ctx->level, node->number);
        });
}

то есть, это уже такой JavaScript получается (кстати, сегодня обнаружил /usr/share/gnome-shell/js). Такие лямбды довольно просто переписываются в обычные функции и, в принципе, ничего не стоят по ресурсам (разве что замангливают ABI).

С возвращаемыми лямбдами можно сделать что-то вроде

enum do_type { odd, even };

node_action make_do(enum do_type type)
{
    switch (type) {
    case odd :
        return fun (struct node *node, void *ctx_) {
            struct ctx *ctx = ctx_;
            if (!(node->number % 2))
                printf("level %d: even %d\n", ctx->level, node->number);
        };
    case even :
        return fun (struct node *node, void *ctx_) {
            struct ctx *ctx = ctx_;
            if (node->number % 2)
                printf("level %d: odd: %d\n", ctx->level, node->number);
        };
    }
}

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

Дальше, если есть обобщённые отображения деревьев:

typedef struct node*(node_map)(struct node*, void*);
struct node* some_parametrized_node_map(param_t param, struct node* node, void* ctx);
struct node* map_tree(struct node *node, node_map mapf);

то карринг позволяет вместо

struct node* new_root = map_tree(root, fun (struct node* node, void* ctx) {
        return some_parametrized_node_map(param, node, ctx);
    });

написать

struct node* new_root = map_tree(root, some_parametrized_node_map(param));

каррирование

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

лямбда-функции

Так любая функция — лямбда-выражение.

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

В хаскеле все функции по дефолту каррированные. Ленивость же.

Имелось в виду, что краткая запись ведёт себя точно так же как и более вербозная

Какая, блин? Русский язык на этом сайте уже не моден?

лямбда-функции

Для функций высшего порядка.

каррирование

Для бесточечного стиля, см. http://en.wikipedia.org/wiki/Tacit_programming

Какая, блин?

Чем более многословная (verbose).

многословная

подробная :)

1. для универсализации синтаксиса в части что и описание действий есть данные и следовательно функции ребята первого класса как и иные данные

2. для универсализации синтаксиса т.е один из методов сказать что всякая функция есть отображения между множестами ( где если слева или справа составные множества это сворачивается в множество составных )

всё вместе + ещё куча всего остального - с целью универсализации

подробная

Гугл с ручным словарём говорят, что всё-таки многословная. detailed, detail, thorough, itemized, explicit, close, particular, minute, circumstantial, nice, narrow, ample, prolix - подробная.

эти вещи мало связаны друг с другом

на примере Haskell: лямбда - это функция, морфизм в Hask; каррирование - это экспоненциал в Hask (всегда существует, поскольку Hask замкнута)

Прелестно. Теория категорий. Ах, как же иногда хорош лисп, где не надо над таким задумываться! :)

как же иногда хорош лисп, где не надо над таким задумываться!

а работа дворника как хороша - вообще думать не надо!

Теория категорий

теория категорий - это язык, на котором удобно отвечать на поставленный вопрос; можно по желанию выбрать любой другой - лишь бы утверждения на нём оставались верными

твоё утверждение верным не было

ну, и бог с ним.

экспоненциал в Hask (всегда существует, поскольку Hask замкнута)

Экспоненциал всегда существует в CCC, в замкнутой - только internal hom. Вопрос о том является ли Hask CCC это ещё вопрос (то есть, хотелось бы, но, говорят, это не так).

Экспоненциал всегда существует в CCC, в замкнутой - только internal hom

не вижу, откуда бы взялось требование декартовости

Экспоненциал всегда существует в CCC

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

достаточно замкнутой симметричной моноидальной категории, совсем не обязательно CCC

Достаточно несимметричной моноидальной категории в которой эндофунктор ─ × b имеет правое сопряжение (для всех b).