Функциональный стиль — часть 6

Функции высшего порядка II: карри.

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

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

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

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

и мы видим, что это дает правильный результат:

Но это не эзотерическая Clojure магия. Чтобы увидеть, насколько это тривиально, давайте сделаем это и в Javascript. Вот функция add :

и вот версия с одним из исправленных параметров:

Итак, это не совсем то , что мы сделали в Clojure. У нас была функция более высокого порядка, называемая partial которая может принимать любую функцию и фиксировать некоторые ее аргументы. Вот пример Javascript, который ближе к версии Clojure. Нам нужно создать собственную partial функцию, но это очень просто сделать:

Затем мы можем использовать его для возврата карри-версии функции add :

Используя карри, чтобы очистить мины.

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

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

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

он должен произвести следующий вывод:

Мы решим эту проблему в Clojure, который будет использовать несколько карри, которые, надеюсь, покажут, почему этот метод полезен.

Знакомство с соседями.

Первый шаг — найти соседей для любой ячейки. Чтобы сделать это проще, мы расширим домен, предполагая две вещи:

• Доска бесконечна.
• Отрицательные координаты в порядке.

Как мы увидим, ни одно из этих предположений не повлияет на окончательное решение. Чтобы вычислить соседей для ячейки, мы можем сделать:

Мы определили neighbours как вектор пар смещения координат, соответствующих восьми ячейкам, смежным с любой позицией доски. Я отформатировал это, чтобы сделать это более ясным: отверстие в середине представляет позицию доски. Функция neighbours-of отображает лямбду на neighbours , чтобы добавить смещения x и y каждого соседа в предоставленную ячейку. Таким образом, он создает набор, содержащий все восемь соседей ячейки, например:

которые действительно являются координатами всех соседей ячейки (2, 2). Получив это, мы можем построить доску с соседями только для одной шахты. Идея состоит в том, что мы будем проверять входную доску ячейка за ячейкой, генерировать промежуточную плату для каждой ячейки на входе и затем объединять их все в окончательный результат. Если рассматриваемая ячейка содержит мину, то сгенерированная доска будет содержать 1 в каждой соседней ячейке; все остальные ячейки будут содержать нули. Наконец, мы сведем все сгенерированные промежуточные доски в таблицу результатов, суммируя соответствующие ячейки на каждой промежуточной доске.

Строим доску.

Чтобы построить доску, нам нужно построить линию, а чтобы построить линию, нам нужно создать ячейку, поэтому давайте начнем с нее:

Аргумент neighbours — это набор позиций ячеек, смежных с шахтой, которые генерируются neighbours-of . Если рассматриваемая ячейка содержит мину, то она будет содержать позиции ее соседей, в противном случае это будет пустой набор. Аргументы y и x — это координаты создаваемой ячейки. Они находятся в таком порядке по определенной причине, которую мы скоро увидим. Кроме того, функция очень проста: если сгенерированная ячейка оказывается смежной с шахтой, она возвращает 1, иначе 0:

Таким образом, мы можем использовать generate-cell для генерации линии ячеек, сопоставляя ее с последовательностью позиций x:

Теперь мы видим немного карри. Мы частично применили первые два аргумента к generate-cell , чтобы динамически создать новую функцию, которая принимает только один аргумент, который является положением х ячейки. Вот почему аргументы x и y были изменены. Затем мы отображаем эту новую функцию на последовательность, сгенерированную (range 0 width) которая формирует координаты x для каждой ячейки в строке:

Теперь, когда у нас есть функция, которая генерирует линию, вызывая эту функцию для диапазона координат y, мы видим, как доска начинает обретать форму. Чтобы полностью понять этот пример, представьте, что мы генерируем доску 5 × 5 для ячейки в (2, 2), которая, как оказалось, содержит шахту:

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

Эта функция ожидает, чтобы dimensions были картой, содержащей ширину и высоту доски, например, для доски 10 × 10: {:h 10 :w 10} . Еще раз, он частично применяет первые два аргумента (соседей и ширину) к генерируемой линии, а затем отображает эту частично примененную функцию на последовательность, сгенерированную (range 0 (dimensions :h)) которая дает координаты y всех линий.

Подождите. Что такое mapcat?

Вам может быть интересно, что делает mapcat. Итак, вот что делает функция generate-board , если мы используем map вместо mapcat:

и это то, что он делает с mapcat вместо этого:

Как видите, список списков сведен в один список. Другими словами, он делает то же самое, что Stream.flatMap в Java. Это облегчит нам жизнь, потому что, как я сказал ранее, мы собираемся создать одну из этих плат для каждой ячейки ввода. Если в ячейке есть мина, то сгенерированная доска будет содержать 1, где находится каждый из ее соседей (хотя она не будет содержать саму мину: это будет накладываться на конечный результат как последний шаг). Затем мы сведем эти сгенерированные доски к одной доске, суммируя значения ячеек в каждой позиции.

Генерация промежуточных плат.

Вот код, который берет одну ячейку из входных данных и генерирует их выходную плату:

Здесь в форме if отсутствует условие else. Когда условие возвращает значение Falsey, оно возвращает nil , что в данном случае нас вполне устраивает. Как обычно, лучший способ понять, что он делает, — выполнить его в REPL:

Теперь мы можем сгенерировать набор плат для данной строки ввода:

который делает это при выполнении в REPL с различными входами. Вывод на самом деле не выглядит так, потому что я отформатировал его для ясности, но структура данных точна:

Я отформатировал вывод, разбив внутренние списки на массивы 3 × 3, чтобы помочь вам понять, что происходит. Надеюсь, это имеет смысл.

Теперь у нас есть все, что нам нужно, чтобы собрать сердце нашего решения:

Это приводит к следующему выводу (немного отформатирован для облегчения понимания):

Подведение промежуточных досок.

Это набор плат, который мы должны сократить до одной платы, добавив соответствующие значения ячеек, что мы и будем делать дальше. Во-первых, однако, орлиные глаза могли заметить, что функция карри (partial boards-for-line dimensions) отображается на две последовательности: lines и (range 0 (dimensions :h)) которая представляет собой последовательность целых чисел от 0 до (number of lines - 1) . Это хорошая вещь в Clojure: вы можете отобразить функцию на несколько последовательностей одновременно. Отображаемая функция должна принимать столько аргументов, сколько имеется последовательностей, и сопоставление продолжается до тех пор, пока не истечет самая короткая последовательность. Например:

производит:

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

Быстрый тест доказывает, что это работает:

Теперь мы можем использовать суммирование, чтобы уменьшить количество досок до одной:

с быстрым тестом, отформатированным снова, чтобы помочь пониманию:

Здесь есть две вещи, которые мы раньше не видели. Один из них — apply : то, что это делает, это применить предоставленную функцию к последовательности, как если бы элементы в последовательности были аргументами функции. Например:

делает то же самое, что и:

Другими словами, он позволяет использовать любую последовательность в качестве списка аргументов для функции с переменным числом аргументов, что действительно очень полезно. Мы используем его так, чтобы список списков обрабатывался как отдельные аргументы для сопоставления, чтобы получить тот же результат, как если бы мы это сделали:

что дает результат (1 2 1 2 2 2 1 2 1) . (NB. Кавычки заставляют Clojure обрабатывать списки буквально, а не как вызовы функций).

Другая вещь, которую раньше не видели, это макрос последнего потока ->> . Это аналог макроса «первый поток», который мы видели в части 4. Это синтаксический сахар в Clojure, чтобы сделать составные функции более читабельными. Это позволяет вам переписать это:

как это:

Последние штрихи.

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

где cell-as-text заменяет нули пробелами и преобразует другие значения в строки:

Теперь поведение таково:

Далее нам нужно разбить вывод на строки, что мы делаем с помощью partition :

и это дает нам:

Теперь нам нужно связать внутренние списки вместе, что достигается еще большим каррированием:

str — это функция, но поскольку функции являются гражданами первого класса, вы можете передавать их в качестве аргументов другим функциям, и это означает, что нет никаких причин, по которым вы не можете частично применить одну функцию ко второй функции и создать третью функцию: (partial reduce str) . Это имеет эффект применения (reduce str) к каждому из внутренних списков, что дает нам такой результат:

Мы вставляем символы новой строки между строк:

а затем соединить строки:

Наложение мин.

Теперь остается сделать только одно: нам нужно наложить мины из исходной строки ввода поверх результата. Это очень просто сделать:

и если мы попробуем это в REPL, мы получим это:

Наш вывод вышел в виде списка, потому что это то, что всегда делает map , поэтому нам нужно снова привести его в соответствие:

Таким образом, наше окончательное решение выглядит так:

который дает этот результат, отформатированный мной снова для удобства чтения:

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

REPL-ориентированная разработка.

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

Еще одна вещь, о которой я надеюсь рассказать, это сила разработки, основанной на REPL. Я, конечно, не рекомендую его в качестве замены для разработки, основанной на тестировании: основным преимуществом TDD является наследие всеобъемлющего машинно-исполняемого набора тестов, которое тестирование в REPL не дает. Скорее я вижу их как дополнительные. В то время как период цикла TDD цикла TDD составляет порядка минуты или около того, цикл обратной связи в REPL занимает буквально секунды. Как метод конструирования программ, который минимизирует время отладки, он не имеет аналогов в моей жизни.

В следующий раз.

Как любит говорить мой коллега Хорхе, мы уходим в бесконечность … и дальше! В следующей статье мы рассмотрим ленивую оценку и то, как она обещает вам все — до тех пор, пока вы на самом деле не просите об этом.