Первоклассные функции I: лямбда-функции и карта.
Что такое первоклассная функция?
Возможно, вы уже слышали, как раньше говорилось, что определенный язык функционален, потому что он имеет «первоклассные функции». Как я уже говорил в первой статье, это не моя точка зрения. Я согласен с тем, что первоклассные функции являются важной функцией любого функционального языка, но я не считаю, что это достаточное условие для того, чтобы язык был функциональным. У многих императивных языков есть эта особенность также. Но что такое первоклассная функция? Функции описываются как первоклассные, когда они могут обрабатываться как любое другое значение: то есть они могут динамически присваиваться имени или символу во время выполнения, они могут храниться в структурах данных, передаваться через аргументы функции и возвращаться как функция возвращает значения.
Это на самом деле не новая идея. Функциональные указатели были особенностью C с момента ее появления в 1972 году. До этого ссылки на процедуры были функцией Algol 68, реализованной в 1970 году, и в то время они считались процедурной функцией программирования. Возвращаясь еще дальше, Lisp (впервые реализованный в 1963 году) был основан на самой концепции взаимозаменяемости программного кода и данных.
Это не неясные особенности либо. В C мы обычно используем функции как первоклассные объекты. Например, при сортировке:
|
01
02
03
04
05
06
07
08
09
10
11
|
char **array = randomStrings();printf("Before sorting:\n");for (int s = 0; s < NO_OF_STRINGS; s++) printf("%s\n", array[s]);qsort(array, NO_OF_STRINGS, sizeof(char *), compare);printf("After sorting:\n");for (int s = 0; s < NO_OF_STRINGS; s++) printf("%s\n", array[s]); |
Библиотека stdlib в C имеет набор функций для различных типов процедур сортировки. Все они способны сортировать данные любого типа: единственная помощь, которая им нужна от программиста, заключается в предоставлении функции, которая сравнивает два элемента набора данных и возвращает -1 , 1 или 0 , чтобы указать, какой элемент больше чем другие или что они равны.
По сути, это шаблон стратегии!
Функция компаратора для нашего массива указателей на строки может быть:
|
1
2
3
4
5
6
|
int compare(const void *a, const void *b){ char *str_a = *(char **) a; char *str_b = *(char **) b; return strcmp(str_a, str_b);} |
и мы передаем его в функцию сортировки следующим образом:
|
1
|
qsort(array, NO_OF_STRINGS, sizeof(char *), compare); |
Отсутствие скобок в имени функции compare заставляет компилятор выдавать указатель на функцию вместо вызова функции. Поэтому рассматривать функцию как объект первого класса в C очень легко, хотя сигнатура функции, которая принимает указатель на функцию, довольно некрасива:
|
1
|
qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); |
Указатели на функции используются не только при сортировке. Задолго до изобретения .NET существовал API-интерфейс Win32 для написания приложений для Microsoft Windows (а до этого — API-интерфейс Win16). Он широко использовал указатели функций для использования в качестве обратных вызовов. Приложение обеспечивало указатели на свои собственные функции при вызове оконного менеджера, который должен вызываться оконным менеджером, когда приложению требовалось уведомление о некотором произошедшем событии. Вы можете думать об этом как о шаблонных отношениях Observer между приложением (наблюдателем) и его окнами (наблюдаемыми): приложение получало уведомления о событиях, таких как щелчки мыши и нажатия клавиш клавиатуры, происходящие в его окнах. Работа по управлению окнами — перемещение их, размещение их друг над другом, определение того, какое приложение является получателем пользовательских действий — абстрагируется в диспетчере окон. Приложения ничего не знают о других приложениях, с которыми они совместно используют среду. В объектно-ориентированном программировании мы обычно достигаем такого рода развязки с помощью абстрактных классов и интерфейсов, но это также может быть достигнуто с помощью первоклассных функций.
Так что мы давно используем первоклассные функции. Но, вероятно, справедливо сказать, что ни один язык не сделал больше для широкого продвижения идеи функций как первоклассных граждан, чем скромный Javascript.
Лямбда-выражения.
В Javascript уже давно стандартной практикой является передача функций другим функциям для использования в качестве обратных вызовов, как в API Win32. Эта идея является неотъемлемой частью HTML DOM, где первоклассные функции могут быть добавлены в качестве прослушивателей событий для элементов DOM:
|
1
2
3
4
5
6
|
function myEventListener() { alert("I was clicked!")}...var myBtn = document.getElementById("myBtn")myBtn.addEventListener("click", myEventListener) |
Как и в C, отсутствие скобок в myEventListener функции myEventListener когда на него ссылаются в вызове addEventListener означает, что оно не выполняется немедленно. Вместо этого функция связана с событием click в рассматриваемом элементе DOM. При щелчке по элементу вызывается функция и появляется предупреждение.
Популярная библиотека jQuery упрощает процесс, предоставляя функцию, которая выбирает элементы DOM посредством строки запроса, и представляет полезные функции для управления элементами и добавления к ним прослушивателей событий:
|
1
2
3
|
$("#myBtn").click(function() { alert("I was clicked!")}) |
Первоклассные функции также являются средством для достижения асинхронного ввода-вывода, который используется в объекте XMLHttpRequest который является основой для Ajax. Эта же идея вездесуща и в Node.js: когда вы хотите сделать неблокирующий вызов функции, вы передаете ей ссылку на функцию, чтобы она вызывала вас, когда это будет сделано.
Но здесь есть и кое-что еще. Второй из них — не только пример первоклассной функции. Это также пример лямбда-функции . В частности, эта часть:
|
1
2
3
|
function() { alert("I was clicked!");} |
Лямбда-функция (часто просто называемая лямбда ) является неназванной функцией. Они могли бы просто назвать их анонимными функциями, и тогда бы все сразу поняли, кто они. Но это звучит не так впечатляюще, так что лямбда-функции таковы. Смысл лямбда-функции — это то, где вам нужна функция в этом месте и только там; так как это больше нигде не нужно, вы просто определяете это прямо здесь. Ему не нужно имя. Если вам нужно было повторно использовать его где-то еще, вы могли бы рассмотреть определение его как именованной функции и ссылаться на него по имени, как я делал в первом примере Javascript. Без лямбда-функций программирование с использованием jQuery и Node действительно было бы очень утомительно.
Лямбда-функции определяются различными способами на разных языках:
В JavaScript: function(a, b) { return a + b }
В Java: (a, b) -> a + b
В C #: (a, b) => a + b
В Clojure: (fn [ab] (+ ab))
В Clojure — сокращенная версия: #(+ %1 %2)
В Groovy: { a, b -> a + b }
В F #: fun ab -> a + b
В Ruby — так называемый «стабильный» синтаксис: -> (a, b) { return a + b }
Как мы видим, большинство языков используют более лаконичный способ выражения лямбд, чем Javascript.
Карта.
Возможно, вы уже используете термин «карта» в своем программировании для обозначения структуры данных, в которой объекты хранятся в виде пар ключ-значение. (Если ваш язык называет это «словарь», то отлично, нет проблем). В функциональном программировании этот термин имеет дополнительное значение, хотя на самом деле основная концепция действительно та же самая. В обоих случаях один набор вещей отображается на другой набор вещей. В смысле структуры данных map является существительным: ключи сопоставляются со значениями. В смысле программирования map — это глагол: функция отображает массив значений в другой массив значений.
Допустим, у вас есть функция f и массив значений A = [ a1 , a2 , a3 , a4 ]. Чтобы отобразить f над A, значит применить f к каждому элементу в A :
- a1 → f ( a1 ) = a1 ‘
- a2 → f ( a2 ) = a2 ‘
- a3 → f ( a3 ) = a3 ‘
- a4 → f ( a4 ) = a4 ‘
затем собираем массив результатов в том же порядке, что и входные данные:
A ‘ = map ( f , A ) = [ a1′ , a2 ‘ , a3′ , a4 ‘ ]
Карта по примеру.
Итак, это интересно, но немного математично . Как часто вы будете делать это в любом случае? На самом деле, гораздо чаще, чем вы думаете. Как обычно, пример объясняет лучше всего, поэтому давайте взглянем на простое упражнение, которое я поднял с https://exercism.io/, когда я изучал Clojure. Упражнение называется «РНК-транскрипция», и оно очень простое: входную строку баз необходимо преобразовать в выходную строку. Основания переводятся так:
- C → G
- G → C
- A → U
- T → A
Любой ввод, кроме C, G, A, T, недопустим. Тест в JUnit5 может выглядеть так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class TranscriberShould { @ParameterizedTest @CsvSource({ "C,G", "G,C", "A,U", "T,A", "ACGTGGTCTTAA,UGCACCAGAAUU" }) void transcribe_dna_to_rna(String dna, String rna) { var transcriber = new Transcriber(); assertThat(transcriber.transcribe(dna), is(rna)); } @Test void reject_invalid_bases() { var transcriber = new Transcriber(); assertThrows( IllegalArgumentException.class, () -> transcriber.transcribe("XCGFGGTDTTAA")); }} |
И мы можем выполнить тесты с помощью этой реализации Java:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Transcriber {private Map<Character, Character> pairs = new HashMap<>(); Transcriber() { pairs.put('C', 'G'); pairs.put('G', 'C'); pairs.put('A', 'U'); pairs.put('T', 'A'); } String transcribe(String dna) { var rna = new StringBuilder(); for (var base: dna.toCharArray()) { if (pairs.containsKey(base)) { var pair = pairs.get(base); rna.append(pair); } else throw new IllegalArgumentException("Not a base: " + base); } return rna.toString(); }} |
Неудивительно, что ключом к программированию в функциональном стиле является превращение всего, что может быть выражено как функция, в единое целое. Итак, давайте сделаем это:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
char basePair(char base) { if (pairs.containsKey(base)) return pairs.get(base); else throw new IllegalArgumentException("Not a base " + base);}String transcribe(String dna) { var rna = new StringBuilder(); for (var base : dna.toCharArray()) { var pair = basePair(base); rna.append(pair); } return rna.toString();} |
Теперь мы можем использовать карту как глагол. В Java для этого предусмотрена функция API-интерфейса Streams:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
|
char basePair(char base) { if (pairs.containsKey(base)) return pairs.get(base); else throw new IllegalArgumentException("Not a base " + base);}String transcribe(String dna) { return dna.codePoints() .mapToObj(c -> (char) c) .map(base -> basePair(base)) .collect( StringBuilder::new, StringBuilder::append, StringBuilder::append) .toString();} |
Хммм.
Итак, давайте критикуем это решение. Лучшее, что можно сказать об этом, это то, что петля прошла. Если вы подумаете об этом, зацикливание — это вид клерикальной деятельности, которой мы не должны заниматься большую часть времени. Обычно мы зацикливаемся, потому что хотим что-то сделать с каждым элементом в коллекции. Здесь мы действительно хотим взять эту входную последовательность и сгенерировать из нее выходную последовательность. Потоковая передача заботится об основной административной работе итерации для нас. На самом деле это шаблон дизайна — шаблон функционального дизайна — но я пока не буду упоминать его название. Я не хочу вас пугать.
Я должен признать, что остальная часть кода не так уж хороша, и это в основном связано с тем, что примитивы в Java не являются объектами. Первая часть не-величия заключается в следующем:
|
1
|
mapToObj(c -> (char) c) |
Мы должны были сделать это, потому что Java обрабатывает примитивы и объекты по-разному, и хотя в языке действительно есть классы-обертки для примитивов, нет никакого способа напрямую получить коллекцию объектов Character из String.
Другая часть менее чем удивительная заключается в следующем:
|
1
2
3
4
|
.collect( StringBuilder::new, StringBuilder::append, StringBuilder::append) |
Далеко не очевидно, почему нужно дважды вызывать append . Я объясню это позже, но сейчас не время для этого.
Я не собираюсь пытаться защитить этот код: это отстой. Если бы был удобный способ получить объекты Stream of Character из String или даже из массива символов, тогда не было бы никаких проблем, но мы не были благословлены одним из них. Работа с примитивами — не самое лучшее место для FP в Java — если подумать, это даже не хорошо для ОО-программирования — поэтому, возможно, мы не должны быть настолько одержимы примитивами. Что если мы разработали их из кода? Мы могли бы создать перечисление для основ:
|
1
2
3
|
enum Base { C, G, A, T, U;} |
и класс, действующий как первоклассная коллекция, содержащая последовательность оснований:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
class Sequence { List<Base> bases; Sequence(List<Base> bases) { this.bases = bases; } Stream<Base> bases() { return bases.stream(); }} |
Теперь транскрибер выглядит так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
|
class Transcriber { private Map<Base, Base> pairs = new HashMap<>(); Transcriber() { pairs.put(C, G); pairs.put(G, C); pairs.put(A, U); pairs.put(T, A); } Sequence transcribe(Sequence dna) { return new Sequence(dna.bases() .map(pairs::get) .collect(toList())); }} |
Это намного лучше. pairs::get — это ссылка на метод, она ссылается на метод get экземпляра, назначенного переменной pairs . Создавая тип для баз, мы разработали возможность недопустимого ввода, поэтому необходимость в методе basePair исчезает, как и исключение. Это одно из преимуществ Java над Clojure, которое само по себе не может применять типы в контрактах функций. Более того, StringBuilder также исчез. Java Streams отлично подходит для тех случаев, когда вам нужно выполнить итерацию коллекции, каким-либо образом обработать каждый элемент и создать новую коллекцию, содержащую результаты. Это, вероятно, составляет довольно большую долю циклов, которые вы написали в своей жизни. Большая часть работы по дому, которая не является частью настоящей работы, сделана для вас.
В Clojure.
Помимо отсутствия типизации, Clojure несколько более лаконичен, чем Java-версия, и это не дает нам никаких трудностей при отображении символов строки. Наиболее важной абстракцией в Clojure является последовательность; все типы коллекций могут рассматриваться как последовательности, и строки не являются исключением:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
(def pairs {\C, "G", \G, "C", \A, "U", \T, "A"})(defn- base-pair [base](if-let [pair (get pairs base)] pair (throw (IllegalArgumentException. (str "Not a base: " base)))))(defn transcribe [dna](map base-pair dna)) |
Бизнес-конец этого кода — последняя строка (map base-pair dna) — стоит указать, иначе вы могли ее пропустить. Это означает map функции base-pair на строку dna (которая ведет себя как последовательность). Если мы хотим, чтобы он возвращал строку вместо списка (что дает нам map ), единственное требуемое изменение будет:
|
1
|
(apply str (map base-pair dna)) |
В C #.
Давайте попробуем другой язык. Императивный подход к решению в C # выглядит так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
|
namespace RnaTranscription{ public class Transcriber { private readonly Dictionary<char, char> _pairs = new Dictionary<char, char> { {'C', 'G'}, {'G', 'C'}, {'A', 'U'}, {'T', 'A'} }; public string Transcribe(string dna) { var rna = new StringBuilder(); foreach (char b in dna) rna.Append(_pairs[b]); return rna.ToString(); } }} |
Опять же, C # не представляет нам проблем, с которыми мы столкнулись в Java, потому что строка в C # является перечисляемой, и все «примитивы» могут рассматриваться как объекты с поведением.
Мы можем переписать программу более функциональным способом, подобным этому, и он оказывается значительно менее многословным, чем версия Java Streams. Для «map» в потоке Java читайте «select» в C #:
|
1
2
3
4
|
public string Transcribe(string dna){ return String.Join("", dna.Select(b => _pairs[b]));} |
Или, если хотите, вы можете использовать LINQ для его синтаксического сахара:
|
1
2
3
4
|
public string Transcribe(string dna){ return String.Join("", from b in dna select _pairs[b]);} |
Почему мы петли?
Вы, наверное, поняли идею. Если вы вспомните времена, когда вы писали цикл, чаще всего вы пытались выполнить одно из следующих действий:
- Отображение массива одного типа в массив другого типа.
- Фильтрация путем нахождения всех элементов в массиве, удовлетворяющих некоторому предикату.
- Определение того, удовлетворяет ли какой-либо из элементов в массиве некоторому предикату.
- Накопление числа, суммы или некоторого другого вида совокупного результата из массива.
- Сортировка элементов массива в определенном порядке.
Функции функционального программирования, доступные в большинстве современных языков, позволяют вам выполнять все эти функции, не прибегая к написанию циклов или созданию коллекций для хранения результатов. Функциональный стиль позволяет вам обходиться без этих вспомогательных операций и концентрироваться на реальной работе. Более того, функциональный стиль позволяет объединять операции вместе, например, если вам необходимо:
- Сопоставить элементы массива с другим типом.
- Отфильтруйте некоторые из сопоставленных элементов.
- Сортировать отфильтрованные элементы.
В императивном стиле это потребует либо нескольких циклов, либо одного цикла с большим количеством кода внутри; так или иначе, это включает в себя много административной работы, которая затемняет реальную цель программы. В функциональном стиле вы можете обойтись без работы администратора и выразить прямо то, что вы имеете в виду. Позже мы увидим больше примеров того, как функциональный стиль может облегчить вашу жизнь.
В следующий раз:
В то время как я изучал функциональное программирование и привыкал к API потоков Java, каждый раз, когда я писал цикл, следующее, что я хотел сделать, это подумать, как я могу переписать его как поток. Обычно это возможно. В C # плагин ReSharper для Visual Studio автоматически предлагает этот вид рефакторинга для вас. Теперь, когда я усвоил функциональный стиль, я просто перейду к потоку и даже не заморачиваюсь с циклом, если он мне действительно не нужен. В следующей статье мы продолжим наше исследование первоклассных функций и того, как мы можем использовать функциональный стиль, чтобы сделать наш код более выразительным, с рассмотрением фильтров и сокращений.
| Опубликовано на Java Code Geeks с разрешения Ричарда Уайлда, партнера нашей программы JCG . Смотреть оригинальную статью здесь: Функциональный стиль — Часть 3
Мнения, высказанные участниками Java Code Geeks, являются их собственными. |