Простые Задачи и Функционально-Блондинистый Подход
Пару месяцев назад я взяла на себя обязательство по самопросвещению. Есть в иных конторах такая тема — сотрудника, раз в полгода ревьюят и говорят «давай к следующему ревью ты изучишь 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))
}
Конечно, дальше я так делать не буду — считаем, что если я знаю, как написать какую-то библиотечную функцию — то могу ее использовать.
Ввод и Вывод
Ввести с консоли одно число оказалось несложно. Для примера я выбрала одну из старых задач — треугольные числа. Нужно ответить, является ли введенное число треугольным или нет. Я некрасивым образом создала список треугольных чисел а потом проверила есть ли введенное в нем — зато освоила функцию 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.
Надеюсь что к тому моменту как я созрею написать о продолжении своих экспериментов (если это будет актуально) у меня будет лучшее решение.
Заключение
На этом я осмелюсь поблагодарить что дочитали о моих злоключениях. Я написала о них в первую очередь потому что те несколько тьюториалов по ФП с которыми я столкнулась почему-то старательно показывали мне примеры которые легко писать в функциональном стиле — и избегали тех от которых пухнет мозг.
Если у вас на примете есть другие упражнения — простые с виду, но не очень простые для реализации в функциональном виде (хотя бы для новичка) — пожалуйста, поделитесь ими!
