Простые Задачи и Функционально-Блондинистый Подход

sad girl and lambda expression

Пару месяцев назад я взяла на себя обязательство по самопросвещению. Есть в иных конторах такая тема — сотрудника, раз в полгода ревьюят и говорят «давай к следующему ревью ты изучишь 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.

Надеюсь что к тому моменту как я созрею написать о продолжении своих экспериментов (если это будет актуально) у меня будет лучшее решение.

Заключение


На этом я осмелюсь поблагодарить что дочитали о моих злоключениях. Я написала о них в первую очередь потому что те несколько тьюториалов по ФП с которыми я столкнулась почему-то старательно показывали мне примеры которые легко писать в функциональном стиле — и избегали тех от которых пухнет мозг.

Если у вас на примете есть другие упражнения — простые с виду, но не очень простые для реализации в функциональном виде (хотя бы для новичка) — пожалуйста, поделитесь ими!

© Habrahabr.ru