Тестировщик, Фронтенд-джуниор
0,0
рейтинг
2 ноября 2015 в 10:28

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

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))
}


Конечно, дальше я так делать не буду — считаем, что если я знаю, как написать какую-то библиотечную функцию — то могу ее использовать.

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.

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

Заключение


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

Если у вас на примете есть другие упражнения — простые с виду, но не очень простые для реализации в функциональном виде (хотя бы для новичка) — пожалуйста, поделитесь ими!
Мария @Musia17
карма
34,0
рейтинг 0,0
Тестировщик, Фронтенд-джуниор
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (35)

  • +13
    Кто-то решил использовать хабр как личный блог :)
  • +6
    Musia17, я бы посоветовал Вам пройти курс Functional Programming Principles in Scala на Coursera. Сам проходил его, могу сказать, что это действительно отличный курс. Но, к сожалению, на сайте нет информации, когда курс запустят в следующий раз. Многие задания в курсе были взяты из небезыизвестной книги SICP. Приятного программирования!
    • 0
      Да, спасибо — я тоже на него смотрела, но увы да, он вроде пока не стартует (а постфактум скучновато).

      Как альтернативу рассматривала Mooc.fi по Clojure. Думаю ей заняться вскоре… Просто сам Clojure он такой Clojure…

      > Многие задания в курсе были взяты из небезыизвестной книги SICP.

      Мне кстати интересно, кто-нить этот небезызвестный талмуд дальше первой части (ну, дальше 100-й страницы скажем) прочел? Правильно ли я слышала что сами MIT-овцы им больше не мучают студентов?
      • 0
        Зато в нем (курс на coursera.org) подробно и пошагово излагаются основы (я в данный момент его прохожу). Для меня был открытием возможный стиль вызова методов класса (я на C++ пишу и вызов метода класса подобно операторам +, — и т.п.) и как был вопрос приоритета вызовов. Хотя для Вас это может быть и не столь актуально — я с использование Java никогда не писал, а Вы пишете. :)
        Но из-за того, что курс в архиве задания не проверяются и остается надеятся, что за выполнение можно считать успешное прохождение юнит тестов. Хотя к заданию 3 недели думаю вернуться позже, уж больно долго оно работает в моей реализации. Если Вы его не пробовали сделать, то посмотрите, может будет интересно.
      • +1
        Да, вводный курс по программированию теперь на Python, а не на Scheme (Intro to CS and Programming in Python). Насчёт книги — я её не всю подряд читал, отдельные главы. Но думаю, что начинающих это неплохая книга. Ещё на сайте Алекса Отта есть неплохой обзор литературы по ФП.
      • +2
        Да после 100 страницы только начинается самое интересное. Помню как читал взахлеб по ночам.
        Только после этого можно в полной мере оценить всю гениальность первой части.
        Единственное, часть про написание интерпретатора пропустил, но сейчас пишу его по другой статье на хаскеле.
        После прочтения книги больше всего был поражен, что с момента ее написания (80-ые) больших зачимых достижений в программировании не было. На самом деле только сейчас многие идеи из книги начинают популяризироваться
      • 0
        На edx.org месяц назад стартовал курс «Introduction to Functional Programming», еще не поздно присоединиться и догнать.
        • 0
          А, знаю, я полгода назад недели три в его предыдущей версии посидела. Можно глянуть что там изменилось… Но тогда там был суровый упор именно на Haskell (хотя утверждалось обратное).

          Основная беда — они общие и простые вещи стремятся рассказать, а подводные камни обнаруживаешь только когда посторонние задачи пытаешься решать.
          • 0
            Там первое же занятие в этом году — упражнения на пяти языках. Насчет основной беды — курс называется «Introduction», отсюда и общие и простые вещи.
  • +2
    Интересно, а почему бы при генерации списка не страдать, а использовать for?
    • 0
      А как же наш ненаглядный функциональный стиль?

      Нет уж. Пожалуй если на что-то переделывать, так на Stream — я сейчас подумала.
      • +1
        А как же наш ненаглядный функциональный стиль?

        А причем тут функциональный стиль?
        Может быть у вас было ограничение на мутабельность и/или повторное присваивание переменных, но вы о нем не упоминали.
        • +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
          • 0
            Под mutable data, обычно подразумевают все таки объект/структуру с изменяющимися полями, и это как бы косвенно подтверждается при переходе с статье по ссылке. К тому же там написано избегать использование, а не то что это недопустимо в принципе. Напомню, что ограничений автором на мутабельность заявлено не было.

            Жесткое требование в функциональном программирование, фактически только одно — использование чистых функций.
      • 0
        Musia17 for вовсе не означает нефункциональный стиль. Почитайте про Sequence Comprehensions (for-yield)
      • 0
        Функциональный стиль не подразумевает генерацию ненужных списков.
        Почитайте про хвостовую рекурсию, это функциональная замена любых циклов.
      • 0
        Вместо рекурсии — y combinator или метод неподвижной точки.
      • +5
        for в Scala — это синтаксический сахор для методов foreach, map и flatMap. То есть все остается достаточно функционально.
  • 0
    По функциональному программированию в целом на Coursera есть прекрасный курс Programming Languages.
    Его огромное преимущество в том, что он не учит какому-то конкретному языку, а в большей степени посвящен концепциям (иммутабельность, pattern matching, каррирование и.т.д) функциональных языков и почему это хорошо.
    В качестве основного языка там используется ML, полученный опыт легко переносится на любой функциональный язык.
    К сожалению свежих сессий не предвидится, но я нашел канал на ютубе, где выложены все лекции. www.youtube.com/channel/UCzMlECXd856E028HnSYExOQ
    Также на github можно легко найти репозиторий с домашними заданиями.
    • 0
      AMar4enko ML — там не основной. В рамках курса изучались несколько концепций и для каждой из них использовался свой язык: ФП — на ML, динамическая типизация, eval, макросы — на Racket, ООП — на Ruby. А вообще курс отличный, рекомендую.
      • 0
        Возможно это мне так запомнилось. Но ООП и Ruby по сравнению с ФП там с гулькин нос.
  • 0
    Здесь много примеров
    rosettacode.org/wiki/Sieve_of_Eratosthenes#Scala
  • 0
  • 0
    Хотелось только отметить, что для той работы со списками, которая делается в этих примерах, надо использовать List, а не Vector, т.к. Vector в разы дороже.
    • 0
      Дороже по времени? Судя по этой табличке не всегда — в частности добавление найденных простых чисел в конец листа будет линейно по времени — так?
      • 0
        Дороже и по времени и по памяти. Т.к. Vector построен на Array Mapped Trie (AMT) и при каждой «модификации» создается не один элемент, а целый массив + дерево перестраивается периодически.
        А при работе с List в Scala элементы добавляются в начало, а не в конец (в этом отличие от java, например), что обеспечивает сложность операции O(1) (благодаря персистенстности), но при этом гораздо более дешевое, чем в Vector.
        • 0
          Все правильно. Но в коде выше элементы добавляются в конец — насколько я понимаю лист здесь не годится т.к. будет создаваться и копироваться целиком новый лист каждый раз — верно?
          • 0
            Ну просто у вас в коде я вижу такие фрагменты
            genList(sz - 1, sz +: res)

            Т.е. вы добавляете элементы в начало вектора. Это как раз тот случай, когда нужно использовать List.
            Возможно вы пропустили такой момент, что операторы, заканчивающиеся на: выполняются на втором аргументе, а не на первом.
            • 0
              > Это как раз тот случай, когда нужно использовать List.

              Да-да, здесь согласна — за это уточнение спасибо :)
          • +1
            > элементы добавляются в конец
            Можно добавлять в начало списка, а в конце сделать линейный reverse. Это довольно частый приём.
            • 0
              Не, не можно. Мы же по этому подрастающему листу каждый новый элемент проверяем поиском сначала — это всё-таки все еще trial-division.
              • 0
                Я говорил про приём в общем, а не конкретно про задачу поиска простых. Для быстрой вставки в оба конца в Haskell есть Data.Sequence, основанная на Finger Trees (аналога в Scala я что-то сходу не нашёл, разве что в исходниках scalaz).
        • +3
          Вы не правы. Vector в Scala это = RRB Tree infoscience.epfl.ch/record/169879/files/RMTrees.pdf
          • 0
            Да, действительно. Как-то перепутал их из-за корзин по 32 элемента. А т.к. код читал поверхностно, то так и осталось это заблуждение. Спасибо за исправление.
      • 0
        В List эффективно добавление в начало. Часто удобно и эффективно наполнять список таким образом, а в конце инвертировать.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.