Введение в функциональное программирование на Python

[gwer]

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

Аргумент _d и переменная d в assoc — это терпимое зло? Пусть даже с учетом краткости функции. Но допустим, что это набор абстрактных данных, пусть. А вот s не слишком ли кратко для последовательности чего-либо кроме символов?

fn и fns — насколько устоявшиеся сокращения? Всем ли оно понятно с первого взгляда?

И как таки вы именуете параметры в анонимных функциях? У меня обычно a, b, … или x, y, …. И выбираются как-то интуитивно. А здесь a, x заставили призадуматься даже.

[grossws]

fn/fns — function/functions; сокращения такого вида часто используют в расчетных программах (типа x/xs/xss, y/ys). Также, как i/j/k для счетчика цикла, вполне понятно и предсказуемо.

a, x — accumulator, x. В том же руби часто используют e в качестве element, a/acc для аккумулятора. Более-менее говорящее имя переменной. Как регистр ax/eax/rax =)

[gwer]

x/xs мне ясны и знакомы еще из книги по Хаскелю. Скорее, интересовало именно сокращение fn. Будем считать, что с ним все ясно.

Про a — аккумулятор не задумался, ибо, просматривая пост в поисках примера, не обратил внимания, что оно исключительно к reduce относится здесь. Действительно удобно, возьму на заметку.

[matiouchkine]

Если вы не заметили, что оно относится только к reduce, то и ваш коллега не заметит. В ruby, вопреки огульному заявлению grossws, используется `memo` для аккумулятора. Достаточно коротко и автореферентно.

[grossws]

Часто встречал acc, как в ruby, так и в scala. В одном проекте стоит использовать консистентное именование, тогда принципиальной разницы между acc и memo не будет.

[matiouchkine]

`acc` это же не совсем `a`, правда? Хотя бы потому, что `[[1,2], [3,4]].each { |a| ...}` ⇐ тут `a` это array.

Про консистентность согласен.

[grossws]

Процитирую комментарий, на который вы отвечали:

В том же руби часто используют e в качестве element, a/acc для аккумулятора.

[matiouchkine]

Процитирую комментарий, на который я отвечал, целиком:

x/xs мне ясны и знакомы еще из книги по Хаскелю. Скорее, интересовало именно сокращение fn. Будем считать, что с ним все ясно.
Про a — аккумулятор не задумался, ибо, просматривая пост в поисках примера, не обратил внимания, что оно исключительно к reduce относится здесь. Действительно удобно, возьму на заметку.

Найдете здесь `acc` — с меня пиво :)

[grossws]

Ага, вижу. Был уверен, что вы отвечали на мой комментарий, а было только упоминание.

[freylis]

Простите, а почему вдруг map и reduce не принимают именованную функцию, а только lambda?

def func(arg):
return arg*arg

map(func, [2,3])
>>> [4, 9]

Мне казалось они могут использовать что угодно вызываемое, хоть метод класса, хоть конструктор

[gwer]

Там речь об аргументе в контексте текущего примера. А примером выше принимается именованная функция.

[bolk]

Что же вы богатую тему генераторов тут не затронули? Вроде примеры подходящие.

[encyclopedist]

Это перевод.

[BasicWolf]

Спасибо за перевод! Для полноты картины я бы добавил ссылку на библиотеку fn.py.

[AlexBin]

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

Набросал пример от балды (извините, что на пасте, тут в карму насрали, теги не работают):
pastebin.com/1yQnJPDS

Товарищи ФП-шники, научите меня…

[kstep]

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

[tenzink]

IMO, в python удобней и читабельней использовать list comprehensions.

[AlexBin]

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

[AlexBin]

вот мой пример выше с помощью ФП:
pastebin.com/1yQnJPDS

а вот через списковые включения:
pastebin.com/DD0aG0U7

читабельность умерла окончательно

[hellman]

people = [{'имя': 'Маша', 'рост': 160},
    {' рост ': 'Саша', ' рост ': 80},
    {'name': 'Паша'}]

heights = map(lambda x: x['рост'],
              filter(lambda x: 'рост' in x, people))

if len(heights) > 0:
    from operator import add
    average_height = reduce(add, heights) / len(heights)

Я конечно понимаю, что это «упражнение» на map/filter/reduce но зачем писать такую ерунду? Хотя бы

heights = [x['рост'] for x in people if 'рост' in x]
if heights:
    average_height = sum(heights) / len(heights)

[sunnyfox]

Меня тоже сразу на генераторы неудержимо потянуло, но видимо автор оставил остальной код в классическом виде, чтобы не запутать читателя. А генераторы наверняка разжеваны в другой главе.
И add, видимо, вытащили, чтобы куда-то впихнуть reduce. Хотя это действительно гланды через задницу… натянутый пример.

[serh1o]

Какой-то странный способ обхода списков:

for i in range(len(names)):
    names[i] = random.choice(code_names)

Не лучше ли:

for name in names:
    names[names.index(name)] = random.choice(code_names)

?

[encyclopedist]

Нет, потому что names.index(name) — это линейный поиск элемента.

можно ещё так:

for i, _ in enumerate(names):
    names[i] = random.choice(code_names)

[iroln]

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

[gwer]

А потом в списке имен появляются повторяющиеся имена…

[serh1o]

Согласен, я понял свою ошибку.
Но неужели в Питоне хорошо писать вот так, тем более в примере в статье?

for i in range(len(names)):

[gwer]

Тут все зависит от задачи. Что-то делается через map или генераторы списков. Где-то достаточно for i in names. Но если требуется именно цикл по списку/кортежу со знанием ключа текущего элемента, то такая конструкция вполне приемлема. Во-первых, в ней нет ничего плохого. Во-вторых, она смотрится не хуже, чем предложенное выше names.index(name), и не имеет присущих этому варианту недостатков.

Другой вариант, не менее подходящий, в ответе к тому комментарию имеется.

[JC_Piligrim]

А почему enumerate рассматриваете не в первых рядах, а в P.S. комментария? Красивее же
for i_name, name in enumerate(names):
чем
for i in range(len(names)):

Это почти так же как
for name in names:
только сразу с индексом и без len().

[kstep]

Потому что перевод?

[gwer]

Потому что пост не об этом. Он о функциональном программировании. Примеры с for i in range(len(names)) здесь используются как примеры того, «как не надо писать» (конечно же, в контексте функционального программирования).

Нужен был пример «обычного» цикла, и используемый подходил как нельзя лучше.

Кроме того, в данном примере enumerate как раз и не нужен, так как имя из итератора не берется. Это видно из примера выше: for i, _ in enumerate(names). Вы собираетесь использовать итератор с сущностями, которые вам не нужны. Это просто лишнее усложнение. В вашем же примере вводится еще и новое имя name, которое не нужно.

[Secessus]

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

Можно ли как-то переписать через те же map и reduce?
Как это решаете в продe? Или не решаете?

Прим. map и reduce внутри вполне себе императивные и проблемой переполнения вызова страдать не должны:

bltinmodule.c

static PyObject *
builtin_map(PyObject *self, PyObject *args)
{
    typedef struct {
        PyObject *it;           /* the iterator object */
        int saw_StopIteration;  /* bool:  did the iterator end? */
    } sequence;

    PyObject *func, *result;
    sequence *seqs = NULL, *sqp;
    Py_ssize_t n, len;
    register int i, j;

    n = PyTuple_Size(args);
    if (n < 2) {
        PyErr_SetString(PyExc_TypeError,
                        "map() requires at least two args");
        return NULL;
    }

    func = PyTuple_GetItem(args, 0);
    n--;

    if (func == Py_None) {
        if (PyErr_WarnPy3k("map(None, ...) not supported in 3.x; "
                           "use list(...)", 1) < 0)
            return NULL;
        if (n == 1) {
            /* map(None, S) is the same as list(S). */
            return PySequence_List(PyTuple_GetItem(args, 1));
        }
    }

    /* Get space for sequence descriptors.  Must NULL out the iterator
     * pointers so that jumping to Fail_2 later doesn't see trash.
     */
    if ((seqs = PyMem_NEW(sequence, n)) == NULL) {
        PyErr_NoMemory();
        return NULL;
    }
    for (i = 0; i < n; ++i) {
        seqs[i].it = (PyObject*)NULL;
        seqs[i].saw_StopIteration = 0;
    }

    /* Do a first pass to obtain iterators for the arguments, and set len
     * to the largest of their lengths.
     */
    len = 0;
    for (i = 0, sqp = seqs; i < n; ++i, ++sqp) {
        PyObject *curseq;
        Py_ssize_t curlen;

        /* Get iterator. */
        curseq = PyTuple_GetItem(args, i+1);
        sqp->it = PyObject_GetIter(curseq);
        if (sqp->it == NULL) {
            static char errmsg[] =
                "argument %d to map() must support iteration";
            char errbuf[sizeof(errmsg) + 25];
            PyOS_snprintf(errbuf, sizeof(errbuf), errmsg, i+2);
            PyErr_SetString(PyExc_TypeError, errbuf);
            goto Fail_2;
        }

        /* Update len. */
        curlen = _PyObject_LengthHint(curseq, 8);
        if (curlen > len)
            len = curlen;
    }

    /* Get space for the result list. */
    if ((result = (PyObject *) PyList_New(len)) == NULL)
        goto Fail_2;

    /* Iterate over the sequences until all have stopped. */
    for (i = 0; ; ++i) {
        PyObject *alist, *item=NULL, *value;
        int numactive = 0;

        if (func == Py_None && n == 1)
            alist = NULL;
        else if ((alist = PyTuple_New(n)) == NULL)
            goto Fail_1;

        for (j = 0, sqp = seqs; j < n; ++j, ++sqp) {
            if (sqp->saw_StopIteration) {
                Py_INCREF(Py_None);
                item = Py_None;
            }
            else {
                item = PyIter_Next(sqp->it);
                if (item)
                    ++numactive;
                else {
                    if (PyErr_Occurred()) {
                        Py_XDECREF(alist);
                        goto Fail_1;
                    }
                    Py_INCREF(Py_None);
                    item = Py_None;
                    sqp->saw_StopIteration = 1;
                }
            }
            if (alist)
                PyTuple_SET_ITEM(alist, j, item);
            else
                break;
        }

        if (!alist)
            alist = item;

        if (numactive == 0) {
            Py_DECREF(alist);
            break;
        }

        if (func == Py_None)
            value = alist;
        else {
            value = PyEval_CallObject(func, alist);
            Py_DECREF(alist);
            if (value == NULL)
                goto Fail_1;
        }
        if (i >= len) {
            int status = PyList_Append(result, value);
            Py_DECREF(value);
            if (status < 0)
                goto Fail_1;
        }
        else if (PyList_SetItem(result, i, value) < 0)
            goto Fail_1;
    }

    if (i < len && PyList_SetSlice(result, i, len, NULL) < 0)
        goto Fail_1;

    goto Succeed;

Fail_1:
    Py_DECREF(result);
Fail_2:
    result = NULL;
Succeed:
    assert(seqs);
    for (i = 0; i < n; ++i)
        Py_XDECREF(seqs[i].it);
    PyMem_DEL(seqs);
    return result;
}

_functoolsmodule.c

/* reduce() *************************************************************/

static PyObject *
functools_reduce(PyObject *self, PyObject *args)
{
    PyObject *seq, *func, *result = NULL, *it;

    if (!PyArg_UnpackTuple(args, "reduce", 2, 3, &func, &seq, &result))
        return NULL;
    if (result != NULL)
        Py_INCREF(result);

    it = PyObject_GetIter(seq);
    if (it == NULL) {
        PyErr_SetString(PyExc_TypeError,
            "reduce() arg 2 must support iteration");
        Py_XDECREF(result);
        return NULL;
    }

    if ((args = PyTuple_New(2)) == NULL)
        goto Fail;

    for (;;) {
        PyObject *op2;

        if (args->ob_refcnt > 1) {
            Py_DECREF(args);
            if ((args = PyTuple_New(2)) == NULL)
                goto Fail;
        }

        op2 = PyIter_Next(it);
        if (op2 == NULL) {
            if (PyErr_Occurred())
                goto Fail;
            break;
        }

        if (result == NULL)
            result = op2;
        else {
            PyTuple_SetItem(args, 0, result);
            PyTuple_SetItem(args, 1, op2);
            if ((result = PyEval_CallObject(func, args)) == NULL)
                goto Fail;
        }
    }

    Py_DECREF(args);

    if (result == NULL)
        PyErr_SetString(PyExc_TypeError,
                   "reduce() of empty sequence with no initial value");

    Py_DECREF(it);
    return result;

Fail:
    Py_XDECREF(args);
    Py_XDECREF(result);
    Py_DECREF(it);
    return NULL;
}

[kstep]

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

[grossws]

В случае scala есть крайне полезная аннотация @tailrec, которая приведёт в compile-time error, если в аннотированном методе невозможно выполнить tail-call optimization. При компиляции превращается в цикл, естественно.

[HDDimon]

>> Функциональный код отличается одним свойством: отсутствием побочных эффектов. Он не полагается на данные вне текущей функции, и не меняет данные, находящиеся вне функции. Все остальные «свойства» можно вывести из этого.

def increment2(a):
    print a
    return a + 1

Вопрос знатокам. Данная функция без побочных эффектов?

[kstep]

Подозреваю, что вопрос риторический, но всё же отвечу =)
Эта функция с побочными эффектами.
Но эта функция не проходит критерий «не меняет данные, находящиеся вне функции».
Потому, что она меняет состояние дескриптора стандартного вывода, который находится вне этой функции.
Так что всё правильно написал автор.

[TheShock]

def draw_car(car_position):
    print '-' * car_position

То есть эта функция имеет побочные эффекты и потому это не функциональное программирование?

[grossws]

Да

[TheShock]

А как в исконно-функциональном программировании делать вывод?

[kstep]

В трёх словах: через монаду IO.

[TheShock]

А в псевдокоде на питоне можно?)

[iroln]

Вот эту статью поглядите:
www.stephanboyer.com/post/83/monads-for-dummies

[TheShock]

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

[kstep]

По сути да, но не совсем. Монада создаёт контекст, в котором вычисляется функция, при этом сама функция может сохранять ссылочную прозрачность. По сути функция, которая возвращает IO String, возвращает не строку, а контекст, из которого можно извлечь строку. А функция, которая принимает IO String, принимает не чистую строку, а опять же контекст со строкой внутри (или, если угодно, обещание строки). Получается, функция как бы не делает никаких побочных эффектов, ничего не читает и ничего не выводит, просто принимает и возвращает чистые немутабельные значения типа «контекст с чем-то внутри», и за счёт этого остаётся чистой. В итоге на выходе из программы, после соединения кучи монад, получаем чистое значение, которое ничего само по себе не читает и не пишет, а только описывает какие-то действия с различными значениями в заданном контексте. А потом уже во время работы программы «грязный» рантайм «выполняет» все эти действия в нужном контексте (например контексте ввода-вывода IO), и мы получаем все побочные эффекты и действия со значениями в них.

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

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

[Lol4t0]

Монада IO — не какое-то волшебное стредство, которое сделает из функции с побочными эффектами функцию без побочных эффектов.

[kstep]

Нет, конечно, но это инструмент, который используется для контроля ввода-вывода в ФП, которая позволяет делать ввод-вывод из чистых функций.

[kstep]

Дополню: чтобы такие функции стали чистыми (без побочных эффектов), используют монады.

[Yuuri]

А также эффекты (Idris) и линейные/уникальные типы (Clean). Монады – лишь один из способов.

[kstep]

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

[Yuuri]

Эффекты, наверное, действительно «монады сбоку». А вот суть Clean'а в том, что если система типов гарантирует, что на каждое значение в любой момент времени существует ровно одна ссылка, то можно смело делать IO-функции вида putString : String → *World → *World и getString : *World → (*World, String), и они будут чистыми «от противного» (потому что нельзя функции скормить два раза одно и то же состояние мира и посмотреть, одинаковые ли результаты получатся).
Кстати, ещё на тему альтернативных подходов к всеобщей чистоте можно глянуть на старый домонадический хаскель с потоковыми IO-функциями вида Request → Response, которые дёргал грязный рантайм.

[kstep]

То есть полный аналог уникальных ссылок (unique_ptr из С++, &mut T из Rust), причём ближе к &mut T раста.

[kstep]

А ведь getString : *World -> (*World, String) по виду тоже очень похоже на поднятую в монаду функцию getString вроде getString : IO () -> IO String, контекст описывается через *World. Могу поспорить, что и монадические законы для этой штуки будут работать, хотя доказывать сейчас лень.