[Из песочницы] Учимся думать и писать на Erlang (на примере двух комбинаторных задач)
— … Тут я даю ему по морд… Нет, бить нельзя!— В том-то и дело, что бить нельзя, — лицемерно вздохнул Паниковский. — Бендер не позволяет.
И.Ильф, Е.Петров. Золотой теленок.
Мозголомная Брага жила в прозрачном сосуде и была такая
крепкая, что даже ужас. Она не то что из живота — прямо изо рта
бросилась в голову и стала кидаться там из стороны в сторону,
ломая умственные подпорки и укрепы.
М.Успенский. Там, где нас нет.
Пожалуй каждый, кто впервые приступает к изучению Erlang, ощущает себя в положении Шуры Балаганова, которому запрещено было применение единственного доступного и понятного метода: «бить нельзя...». В Erlang отсутствуют такие привычные для большинства современных языков понятия, как повторное присвоение переменной и, соответственно, накопление результата в одной переменной. (Справедливости ради следует отметить, что поведение типа «глобальная многократно меняющаяся переменная» в Erlang все же можно реализовать. Для этого в каждом процессе имеется словарь хешей, хранящий определяемые программистом пары ключ — значение. Имеются встроенные функции put(Key, Value), get(Key) и еще несколько вспомогательных функций. Но использование такого словаря в приложениях считается плохим стилем и рекомендуется только в исключительных случаях (http://www.erlang.org/doc/man/erlang.html\#put-2)). Как следствие, итерации в цикле невозможно реализовать с помощью привычного наращивания значений итерационной переменной. Накопление результата осуществляется только через рекурсию, а организация циклов — через хвостовую рекурсию. (Конечно, и итерации, и накопление результата в цикле можно реализовать через библиотечные функции для списков lists:foreach(Function, List), lists:foldl(Function, StartValue, List), lists:foldr(Function, StartValue, List) (http://www.erlang.org/doc/man/lists.html) и их аналоги для наборов (http://www.erlang.org/doc/man/sets.html, http://www.erlang.org/doc/man/ordsets.html, http://www.erlang.org/doc/man/gb_sets.html) и массивов (http://www.erlang.org/doc/man/array.html). Но наша цель — научиться писать циклы, а не использовать готовые решения, поэтому здесь мы воздержимся от употребления подобных библиотек).
Таким образом, в Erlang приходится ломать привычные шаблоны мышления и заменять их новыми паттернами, характерными только для этого языка программирования. Конечно, идеальное средство — мозголомная брага, способная ломать все «умственные подпорки и укрепы». Но для нас это, пожалуй, слишком радикальное средство, и мы пойдем другим путем.
В житии святого Антония Великого есть рассказ об одном из его учеников. Ученик стоял в храме и слушал, как святой Антоний читал Псалтырь. Как только прозвучал первый стих первого псалма:
Блажен муж, который не ходит на совет нечестивых...ученик вышел из храма. С тех пор его никто не видел почти 30 лет, а когда он вновь появился в храме, Антоний Великий спросил, почему он оставил их так надолго и куда исчез. Ученик ответил: «отче, я услышал слова псалма, и удалился в пустыню, чтобы постараться выполнить то, о чем говорится в этих словах, т.е. не ходить на совет нечестивых мыслей». Другими словами, он усвоил практический урок этих слов, и теперь пришел чтобы читать дальше. К сожалению, у нас нет такого резерва времени, да и цели наши не столь возвышенны. Но основной концепт можно перенять.
Мы рассмотрим две стандартные комбинаторные задачи:
- поиск всех возможных перестановок (permutations) из данного множества по N элементов
- поиск всех возможных сочетаний (combinations) из данного множества по N элементов
и разберем различные подходы и способы их решения средствами языка программирования Erlang, чтобы на конкретных примерах понять и освоить некоторые особенности программирования на этом языке.
Читать дальше →
