Пару месяцев назад я взяла на себя обязательство по самопросвещению. Есть в иных конторах такая тема — сотрудника, раз в полгода ревьюят и говорят «давай к следующему ревью ты изучишь Spring, паттерны (какие?) и функциональное программирование!» Идея была бы неплоха если бы цели не ставили так размыто. Пропустим пока спринг и паттерны — на выходных я бросилась в атаку на ФП.
Общие-туманные сведения о ФП у меня конечно были — анонимные классы в Java я писать умею — с похожими способностями Python и JavaScript знакома.
Начну с простых упражнений на Scala — решила я. Выбрала Scala поскольку основной рабочий инструмент у нас Java — ну были еще варианты Clojure, Groovy и Java8 (что-то еще?) — но с ними авось попробую потом.
Поставила себе цели (а правильно ли я ФП поняла?):
- Решать задачи в функциональном стиле
- Т.е. по возможности не использовать явных циклов и ветвлений
- А также избегать мутабельных коллекций и т.п.
Одни упражнения получались легко, другие мягко говоря не очень. Сейчас я попробую вкратце рассказать об этом — упорядочить новые познания. Трудно сказать, может ли эта статья кому-то в будущем помочь или, скорее, кто-то поможет мне самой, указав на ошибки или предложив улучшения.
Суммирование и Фильтрация
Самое начало — скачивание скалы и гугление в поисках «как запустить Main» я пропущу. Справилась — и ладно.
В качестве первого примера — первая задача с ProjectEuler: сосчитать сумму тех чисел от 1 до 999, которые делятся на 3 либо 5. Вообще на FizzBuzz похоже.
Гугл помог мне найти примеры генерации диапазона и фильтрации:
object Main extends App {
def res = (1 to 999).filter(x => x % 3 == 0 || x % 5 == 0)
System.out.println(res.sum)
}
Однако написала и задумалась: я использую готовое задание диапазона — и готовую функцию суммирования. Я смутно помнила об агрегирующих функциях и через -дцать минут переписала сумму с использованием reduce (вспомнила её из Python-а). А как сгенерировать список чисел от 1 до 999? Примерно через час мучений я родила рекурсивную функцию (жаль, не смогла без нее).
import scala.annotation.tailrec
import scala.collection.immutable.Vector
object Main extends App {
@tailrec
def genList(sz: Int, res: Vector[Int]): Vector[Int] = {
if (sz == 0) res else genList(sz - 1, sz +: res)
}
def res = genList(999, Vector()).filter(x => x % 3 == 0 || x % 5 == 0)
System.out.println(res.reduce((a, b) => a + b))
}
Конечно, дальше я так делать не буду — считаем, что если я знаю, как написать какую-то библиотечную функцию — то могу ее использовать.
UPD
После намёка в комментариях сообразила что могу для генерации использовать стрим (с которым познакомилась позже) — спасибо за пинок в нужном направлении:
def list = Stream.iterate(1)(x => x + 1).takeWhile(x => x < 1000)
def res = list.filter...
Ввод и Вывод
Ввести с консоли одно число оказалось несложно. Для примера я выбрала одну из старых задач — треугольные числа. Нужно ответить, является ли введенное число треугольным или нет. Я некрасивым образом создала список треугольных чисел а потом проверила есть ли введенное в нем — зато освоила функцию map (с которой знакома в основном из JavaScript).
import scala.io.StdIn
object Main extends App {
def tris = (1 to 500).map(n => n * (n + 1) / 2)
val x = StdIn.readLine.toInt
System.out.println(if (tris.contains(x)) "YES" else "NO")
}
Совсем без ветвлений пока не получается — успокаиваю себя тем что они небольшие.
Что если нужно вводить много чисел? Взяла упражнение о суммировании нескольких пар чисел. Сначала идет количество пар, а потом в отдельных строках сами пары.
У меня получилась более общая задача — нужно найти сумму в каждой строке (необязательно для пары):
import scala.io.StdIn
object Main extends App {
val n = StdIn.readLine.toInt
val samples = Iterator.continually(StdIn.readLine).take(n).toList
val output = samples.map((x) => x.split(" ").map(_.toInt).sum)
System.out.println(output.mkString(" "))
}
Я решила еще пяток похожих задач — считать в цикле, преобразовать, вывести — пока мне не надоело.
Stream-ы и итерации «до обеда»
Гипотезу Коллатца я помню еще из какой-то детской книжки — я тогда чуть не день просидела проверяя её на бумажке для числа 97 (не преуспела). Подыскав соответствующую задачу я думала что раскушу её быстро, но на деле осилила только на следующий день.
Сначала написала с рекурсивной функцией (похоже на то как выше делала), но потом стала искать какой-то более готовый подход. Благодаря этому я познакомилась со Stream, iterate и takeWhile.
Итак, в строке заданы числа — нужно посчитать, за какое число итераций преобразование Коллатца для каждого из них приведет к единице:
import scala.io.StdIn
object Main extends App {
def collatz(a:Long) = if (a % 2 == 1) a * 3 + 1 else a / 2
val input = StdIn.readLine.split(" ").map(_.toLong)
val output = input.map(m => Stream.iterate(m)(collatz).takeWhile(_ > 1).size)
System.out.println(output.mkString(" "))
}
Получилось так коротко что я уже думала что готова к любым неприятностям. Однако пару упражнений спустя я столкнулась с реальной бедой.
Простые Числа
Простые числа я (в основном с помощью однообразных упражнений с ProjectEuler из времен освоения Java) привыкла генерить с помощью trial division. Внезапно оказалось что в функциональном виде это (по крайней мере мне) написать очень сложно. Ведь в цикле нужно проверять все новые и новые числа, добавляя их в результирующий массив, по которому в то же время идёт эта проверка…
Вот задача — по заданным индексам вывести простые числа с соответствующими порядковыми номерами. Я подумала что стоит лишь сгенерировать массив — и ура…
Провозившись полдня, я уже взялась просматривать интернет в поисках подсказок. К сожалению выкрутасы вроде этого «однострочника» не только не приближали меня к разгадке, но и напротив усиливали ощущение собственной неполноценности.
В конце концов я победила изобретя рекуррентную функцию, куда передаётся список уже найденных чисел и следующее проверяемое число. Вот этот монстр:
def generate(n: Int) = {
@tailrec
def mainLoop(test: Int, found: Vector[Int]): Vector[Int] = {
if (found.size == n) {
return found
}
mainLoop(test + 2, if (found.find(test % _ == 0).nonEmpty) found else found :+ test)
}
mainLoop(3, Vector(2))
}
val values = StdIn.readLine.split(" ").map(_.toInt)
val primeList = generate(values.max)
val output = values.map(x => primeList(x - 1))
System.out.println(output.mkString(" "))
У меня были более короткие решения, однако удовлетворительно работавшие для чисел меньше ста — их быстродействие явно страдало из-за неявных внутренних итераций…
Мне не нравится то что получилось. Я нашла некую видимо научную статью о генерации простых чисел в функциональном стиле, где, вроде, намекается что для ФП предпочтительно пробовать подход с решетом Эратосфена. Однако я пока еще чувствую себя достаточно слабой в Scala чтоб придумать как заполнять решето иммутабельно. Хотя сейчас — прямо пока писала этот текст — пришла в голову мысль что нужно использовать что-то вроде иммутабельного HashSet.
Надеюсь что к тому моменту как я созрею написать о продолжении своих экспериментов (если это будет актуально) у меня будет лучшее решение.
Заключение
На этом я осмелюсь поблагодарить что дочитали о моих злоключениях. Я написала о них в первую очередь потому что те несколько тьюториалов по ФП с которыми я столкнулась почему-то старательно показывали мне примеры которые легко писать в функциональном стиле — и избегали тех от которых пухнет мозг.
Если у вас на примете есть другие упражнения — простые с виду, но не очень простые для реализации в функциональном виде (хотя бы для новичка) — пожалуйста, поделитесь ими!
Комментарии (35)
Schrodingers_Cat
02.11.2015 11:53+6Musia17, я бы посоветовал Вам пройти курс Functional Programming Principles in Scala на Coursera. Сам проходил его, могу сказать, что это действительно отличный курс. Но, к сожалению, на сайте нет информации, когда курс запустят в следующий раз. Многие задания в курсе были взяты из небезыизвестной книги SICP. Приятного программирования!
Musia17
02.11.2015 12:00Да, спасибо — я тоже на него смотрела, но увы да, он вроде пока не стартует (а постфактум скучновато).
Как альтернативу рассматривала Mooc.fi по Clojure. Думаю ей заняться вскоре… Просто сам Clojure он такой Clojure…
> Многие задания в курсе были взяты из небезыизвестной книги SICP.
Мне кстати интересно, кто-нить этот небезызвестный талмуд дальше первой части (ну, дальше 100-й страницы скажем) прочел? Правильно ли я слышала что сами MIT-овцы им больше не мучают студентов?
Hokum
02.11.2015 12:30Зато в нем (курс на coursera.org) подробно и пошагово излагаются основы (я в данный момент его прохожу). Для меня был открытием возможный стиль вызова методов класса (я на C++ пишу и вызов метода класса подобно операторам +, — и т.п.) и как был вопрос приоритета вызовов. Хотя для Вас это может быть и не столь актуально — я с использование Java никогда не писал, а Вы пишете. :)
Но из-за того, что курс в архиве задания не проверяются и остается надеятся, что за выполнение можно считать успешное прохождение юнит тестов. Хотя к заданию 3 недели думаю вернуться позже, уж больно долго оно работает в моей реализации. Если Вы его не пробовали сделать, то посмотрите, может будет интересно.
Schrodingers_Cat
02.11.2015 12:46+1Да, вводный курс по программированию теперь на Python, а не на Scheme (Intro to CS and Programming in Python). Насчёт книги — я её не всю подряд читал, отдельные главы. Но думаю, что начинающих это неплохая книга. Ещё на сайте Алекса Отта есть неплохой обзор литературы по ФП.
wheercool
02.11.2015 13:01+2Да после 100 страницы только начинается самое интересное. Помню как читал взахлеб по ночам.
Только после этого можно в полной мере оценить всю гениальность первой части.
Единственное, часть про написание интерпретатора пропустил, но сейчас пишу его по другой статье на хаскеле.
После прочтения книги больше всего был поражен, что с момента ее написания (80-ые) больших зачимых достижений в программировании не было. На самом деле только сейчас многие идеи из книги начинают популяризироваться
leemuar
02.11.2015 17:04На edx.org месяц назад стартовал курс «Introduction to Functional Programming», еще не поздно присоединиться и догнать.
Musia17
02.11.2015 17:23А, знаю, я полгода назад недели три в его предыдущей версии посидела. Можно глянуть что там изменилось… Но тогда там был суровый упор именно на Haskell (хотя утверждалось обратное).
Основная беда — они общие и простые вещи стремятся рассказать, а подводные камни обнаруживаешь только когда посторонние задачи пытаешься решать.leemuar
02.11.2015 22:11Там первое же занятие в этом году — упражнения на пяти языках. Насчет основной беды — курс называется «Introduction», отсюда и общие и простые вещи.
Alesh
02.11.2015 12:10+2Интересно, а почему бы при генерации списка не страдать, а использовать for?
Musia17
02.11.2015 12:24А как же наш ненаглядный функциональный стиль?
Нет уж. Пожалуй если на что-то переделывать, так на Stream — я сейчас подумала.Alesh
02.11.2015 12:36+1А как же наш ненаглядный функциональный стиль?
А причем тут функциональный стиль?
Может быть у вас было ограничение на мутабельность и/или повторное присваивание переменных, но вы о нем не упоминали.Hokum
02.11.2015 12:40+1Функциональный стиль программирования подразумевает работу с неизменямыми данными.
Из википедии:
In computer science, functional programming is a programming paradigm—a style of building the structure and elements of computer programs—that treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data
Alesh
02.11.2015 13:03Под mutable data, обычно подразумевают все таки объект/структуру с изменяющимися полями, и это как бы косвенно подтверждается при переходе с статье по ссылке. К тому же там написано избегать использование, а не то что это недопустимо в принципе. Напомню, что ограничений автором на мутабельность заявлено не было.
Жесткое требование в функциональном программирование, фактически только одно — использование чистых функций.
Schrodingers_Cat
02.11.2015 12:56Musia17 for вовсе не означает нефункциональный стиль. Почитайте про Sequence Comprehensions (for-yield)
Source
02.11.2015 13:01Функциональный стиль не подразумевает генерацию ненужных списков.
Почитайте про хвостовую рекурсию, это функциональная замена любых циклов.
potan
03.11.2015 18:58+5for в Scala — это синтаксический сахор для методов foreach, map и flatMap. То есть все остается достаточно функционально.
AMar4enko
02.11.2015 12:49По функциональному программированию в целом на Coursera есть прекрасный курс Programming Languages.
Его огромное преимущество в том, что он не учит какому-то конкретному языку, а в большей степени посвящен концепциям (иммутабельность, pattern matching, каррирование и.т.д) функциональных языков и почему это хорошо.
В качестве основного языка там используется ML, полученный опыт легко переносится на любой функциональный язык.
К сожалению свежих сессий не предвидится, но я нашел канал на ютубе, где выложены все лекции. www.youtube.com/channel/UCzMlECXd856E028HnSYExOQ
Также на github можно легко найти репозиторий с домашними заданиями.Schrodingers_Cat
02.11.2015 13:06AMar4enko ML — там не основной. В рамках курса изучались несколько концепций и для каждой из них использовался свой язык: ФП — на ML, динамическая типизация, eval, макросы — на Racket, ООП — на Ruby. А вообще курс отличный, рекомендую.
AMar4enko
02.11.2015 13:08Возможно это мне так запомнилось. Но ООП и Ruby по сравнению с ФП там с гулькин нос.
cs0ip
02.11.2015 13:58Хотелось только отметить, что для той работы со списками, которая делается в этих примерах, надо использовать List, а не Vector, т.к. Vector в разы дороже.
Musia17
02.11.2015 14:18Дороже по времени? Судя по этой табличке не всегда — в частности добавление найденных простых чисел в конец листа будет линейно по времени — так?
cs0ip
02.11.2015 15:03Дороже и по времени и по памяти. Т.к. Vector построен на Array Mapped Trie (AMT) и при каждой «модификации» создается не один элемент, а целый массив + дерево перестраивается периодически.
А при работе с List в Scala элементы добавляются в начало, а не в конец (в этом отличие от java, например), что обеспечивает сложность операции O(1) (благодаря персистенстности), но при этом гораздо более дешевое, чем в Vector.Musia17
02.11.2015 15:13Все правильно. Но в коде выше элементы добавляются в конец — насколько я понимаю лист здесь не годится т.к. будет создаваться и копироваться целиком новый лист каждый раз — верно?
cs0ip
02.11.2015 15:20Ну просто у вас в коде я вижу такие фрагменты
genList(sz - 1, sz +: res)
Т.е. вы добавляете элементы в начало вектора. Это как раз тот случай, когда нужно использовать List.
Возможно вы пропустили такой момент, что операторы, заканчивающиеся на: выполняются на втором аргументе, а не на первом.Musia17
02.11.2015 15:36> Это как раз тот случай, когда нужно использовать List.
Да-да, здесь согласна — за это уточнение спасибо :)
roman_kashitsyn
02.11.2015 15:40+1> элементы добавляются в конец
Можно добавлять в начало списка, а в конце сделать линейный reverse. Это довольно частый приём.Musia17
02.11.2015 15:48Не, не можно. Мы же по этому подрастающему листу каждый новый элемент проверяем поиском сначала — это всё-таки все еще trial-division.
roman_kashitsyn
02.11.2015 16:57Я говорил про приём в общем, а не конкретно про задачу поиска простых. Для быстрой вставки в оба конца в Haskell есть Data.Sequence, основанная на Finger Trees (аналога в Scala я что-то сходу не нашёл, разве что в исходниках scalaz).
darkdimius
04.11.2015 23:46+3Вы не правы. Vector в Scala это = RRB Tree infoscience.epfl.ch/record/169879/files/RMTrees.pdf
cs0ip
05.11.2015 01:13Да, действительно. Как-то перепутал их из-за корзин по 32 элемента. А т.к. код читал поверхностно, то так и осталось это заблуждение. Спасибо за исправление.
potan
03.11.2015 19:01В List эффективно добавление в начало. Часто удобно и эффективно наполнять список таким образом, а в конце инвертировать.
AndrewN
Кто-то решил использовать хабр как личный блог :)