Поиск декартова произведения с помощью LINQ
Для начала, давайте убедимся, что мы знаем, о чем идет речь. Я буду обозначать последовательности как упорядоченные множества: Декартово произведение двух последовательностей S1 и S2 есть последовательность всех возможных упорядоченных пар таких, что их первый элемент из S1, а второй — из S2. Так, к примеру, если у вас есть две последовательности и , то их декартово произведение выглядит как .
Для упрощения, предположим, что S1 и S2 состоят из элементов одного типа. Разумеется, мы можем определить декартово произведение последовательности строк с последовательностью чисел как последовательность кортежей (string, int), но впоследствии это окажется тяжело обобщать, потому что система типов C#, в частности, не лучшим образом работает с кортежами произвольной длины. В LINQ есть оператор специально для вычисления декартовых произведений: в «синтаксисе методов» это SelectMany , в «синтаксисе запросов» это запрос с двумя выражениями «from»:
Конечно же, мы можем обобщить декартово произведение на более чем две последовательности. Декартово произведение n последовательностей есть последовательность всех возможных n-элементных последовательностей, у которых первый элемент из S1, второй из S2 и т.д.
В этом определении не хватает тривиального случая: что есть декартово произведение нуля последовательностей? Пускай в таком случае оно состоит из последовательности, содержащей единственный элемент: пустую последовательность, то есть < < >> .
Обратите внимание, что это дает логичное определение декартова произведения одной последовательности. Декартово произведение последовательности, содержащей одну-единственную последовательность (скажем, ) есть последовательность всех возможных одноэлементых последовательностей, где первый (и единственный) элемент из . Таким образом, декартово произведение есть .
С помощью LINQ вы можете составить декартово произведение любого количества последовательностей достаточно просто, если вы изначально знаете, с каким количеством будете работать:
Что ж, есть причина использовать индукцию; эта идея практически никогда не подводит при работе с рекурсивно определенными структурами данных.
Если sequences содержит ноль последовательностей, дело сделано: мы просто возвращаем < < >> .
Как найти декартово произведение двух последовательностей, скажем, снова и ? Начнем с подсчета декартова произведения первой последовательности. Пускай индуктивное предположение состоит в том, что мы каким-либо образом сделали это, так что мы знаем ответ: . Как соединить с , чтобы получить общее произведение?
В терминах кода: пускай у нас есть старое декартово произведение, скажем . Мы хотим соединить его с последовательностью :
И теперь у нас есть благополучный индукционный переход. Если oldProduct — любое декартово произведение, то мы можем вычислить его комбинацию с другой последовательностью, чтобы получить новое декартово произведение.
На всякий пожарный: этот метод работает с основой индукции? Да. Если мы хотим скомбинировать декартово произведение < < >> с последовательностью , мы склеиваем < >с и < >с , чтобы получить .
Давайте соберем все это вместе:
Работает отлично, но при желании можно сделать чуточку красивее. По существу мы здесь используем аккумулятор. Рассмотрим пример проще, скажем, суммирование списка целых чисел. Один из способов сделать это — сказать «Пусть аккумулятор вначале равен нулю. Новый аккумулятор получается из старого путем добавления текущего элемента к старому аккумулятору». Если у нас есть стартовое значение аккумулятора и мы некоторым образом можем получить новое значение из старого и из текущего элемента последовательности, тогда можно использовать полезный метод Aggregate . Он принимает стартовое значение аккумулятора и функцию, которая принимает последнее значение и текущий элемент и возвращает новое значение аккумулятора. На выходе метода — итоговое значение аккумулятора.
В данном случае мы начнем с пустым произведением в качестве аккумулятора, и каждый раз мы будем «добавлять» к нему путем комбинирования текущей последовательности с произведением предыдущих. На каждом шаге алгоритма, аккумулятор равен декартовому произведению уже просмотренных последовательностей.
И напоследок несколько слов для разбирающихся. Помните, результат LINQ-запроса есть запрос, который предоставит результаты по требованию, а не результаты непосредственно. Когда мы строим этот аккумулятор, мы вообще-то не вычисляем декартово произведение. Мы строим большой сложный запрос, который при запуске выдаст декартово произведение. Запрос строится энергично, но выполняться будет лениво.
От переводчикаЭрик обошел в своем посте конкретное название идиомы, которую он использовал, а именно свертки. Впрочем, на эту тему на Хабрахабре уже были посты. Интересующийся может найти отличный перевод «Катаморфизм в F#».
Ту же задачу, гораздо менее многословно, но с тем же алгоритмом, можно решить и на F#. Вместо LINQ в код хорошо впишутся списочные выражения (list comprehensions) — одна из замечательных фич, традиционно свойственных функциональным языкам. Для достижения большей производительности приклеивать элемент к списку стоит с головы, оператором (::) . В таком случае для достижения классического вида декартова произведения исходную последовательность перед началом работы придется перевернуть.
В сумме свертка, пайплайны и списочные выражения дадут вот такой красивый код: