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

[@AndrewN]

Кто-то решил использовать хабр как личный блог :)

[@Schrodingers_Cat]

Musia17, я бы посоветовал Вам пройти курс Functional Programming Principles in Scala на Coursera. Сам проходил его, могу сказать, что это действительно отличный курс. Но, к сожалению, на сайте нет информации, когда курс запустят в следующий раз. Многие задания в курсе были взяты из небезыизвестной книги SICP. Приятного программирования!

[@Musia17]

Да, спасибо — я тоже на него смотрела, но увы да, он вроде пока не стартует (а постфактум скучновато).

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

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

Мне кстати интересно, кто-нить этот небезызвестный талмуд дальше первой части (ну, дальше 100-й страницы скажем) прочел? Правильно ли я слышала что сами MIT-овцы им больше не мучают студентов?

[@Hokum]

Зато в нем (курс на coursera.org) подробно и пошагово излагаются основы (я в данный момент его прохожу). Для меня был открытием возможный стиль вызова методов класса (я на C++ пишу и вызов метода класса подобно операторам +, — и т.п.) и как был вопрос приоритета вызовов. Хотя для Вас это может быть и не столь актуально — я с использование Java никогда не писал, а Вы пишете. :)
Но из-за того, что курс в архиве задания не проверяются и остается надеятся, что за выполнение можно считать успешное прохождение юнит тестов. Хотя к заданию 3 недели думаю вернуться позже, уж больно долго оно работает в моей реализации. Если Вы его не пробовали сделать, то посмотрите, может будет интересно.

[@Schrodingers_Cat]

Да, вводный курс по программированию теперь на Python, а не на Scheme (Intro to CS and Programming in Python). Насчёт книги — я её не всю подряд читал, отдельные главы. Но думаю, что начинающих это неплохая книга. Ещё на сайте Алекса Отта есть неплохой обзор литературы по ФП.

[@wheercool]

Да после 100 страницы только начинается самое интересное. Помню как читал взахлеб по ночам.
Только после этого можно в полной мере оценить всю гениальность первой части.
Единственное, часть про написание интерпретатора пропустил, но сейчас пишу его по другой статье на хаскеле.
После прочтения книги больше всего был поражен, что с момента ее написания (80-ые) больших зачимых достижений в программировании не было. На самом деле только сейчас многие идеи из книги начинают популяризироваться

[@leemuar]

На edx.org месяц назад стартовал курс «Introduction to Functional Programming», еще не поздно присоединиться и догнать.

[@Musia17]

А, знаю, я полгода назад недели три в его предыдущей версии посидела. Можно глянуть что там изменилось… Но тогда там был суровый упор именно на Haskell (хотя утверждалось обратное).

Основная беда — они общие и простые вещи стремятся рассказать, а подводные камни обнаруживаешь только когда посторонние задачи пытаешься решать.

[@leemuar]

Там первое же занятие в этом году — упражнения на пяти языках. Насчет основной беды — курс называется «Introduction», отсюда и общие и простые вещи.

[@Alesh]

Интересно, а почему бы при генерации списка не страдать, а использовать for?

[@Musia17]

А как же наш ненаглядный функциональный стиль?

Нет уж. Пожалуй если на что-то переделывать, так на Stream — я сейчас подумала.

[@Alesh]

А как же наш ненаглядный функциональный стиль?

А причем тут функциональный стиль?
Может быть у вас было ограничение на мутабельность и/или повторное присваивание переменных, но вы о нем не упоминали.

[@Hokum]

Функциональный стиль программирования подразумевает работу с неизменямыми данными.
Из википедии:

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]

Под mutable data, обычно подразумевают все таки объект/структуру с изменяющимися полями, и это как бы косвенно подтверждается при переходе с статье по ссылке. К тому же там написано избегать использование, а не то что это недопустимо в принципе. Напомню, что ограничений автором на мутабельность заявлено не было.

Жесткое требование в функциональном программирование, фактически только одно — использование чистых функций.

[@Schrodingers_Cat]

Musia17 for вовсе не означает нефункциональный стиль. Почитайте про Sequence Comprehensions (for-yield)

[@Source]

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

[@xGromMx]

Вместо рекурсии — y combinator или метод неподвижной точки.

[@potan]

for в Scala — это синтаксический сахор для методов foreach, map и flatMap. То есть все остается достаточно функционально.

[@AMar4enko]

По функциональному программированию в целом на Coursera есть прекрасный курс Programming Languages.
Его огромное преимущество в том, что он не учит какому-то конкретному языку, а в большей степени посвящен концепциям (иммутабельность, pattern matching, каррирование и.т.д) функциональных языков и почему это хорошо.
В качестве основного языка там используется ML, полученный опыт легко переносится на любой функциональный язык.
К сожалению свежих сессий не предвидится, но я нашел канал на ютубе, где выложены все лекции. www.youtube.com/channel/UCzMlECXd856E028HnSYExOQ
Также на github можно легко найти репозиторий с домашними заданиями.

[@Schrodingers_Cat]

AMar4enko ML — там не основной. В рамках курса изучались несколько концепций и для каждой из них использовался свой язык: ФП — на ML, динамическая типизация, eval, макросы — на Racket, ООП — на Ruby. А вообще курс отличный, рекомендую.

[@AMar4enko]

Возможно это мне так запомнилось. Но ООП и Ruby по сравнению с ФП там с гулькин нос.

[@dmtrius]

Здесь много примеров
rosettacode.org/wiki/Sieve_of_Eratosthenes#Scala

[@Optik]

www.manning.com/books/functional-programming-in-scala

[@cs0ip]

Хотелось только отметить, что для той работы со списками, которая делается в этих примерах, надо использовать List, а не Vector, т.к. Vector в разы дороже.

[@Musia17]

Дороже по времени? Судя по этой табличке не всегда — в частности добавление найденных простых чисел в конец листа будет линейно по времени — так?

[@cs0ip]

Дороже и по времени и по памяти. Т.к. Vector построен на Array Mapped Trie (AMT) и при каждой «модификации» создается не один элемент, а целый массив + дерево перестраивается периодически.
А при работе с List в Scala элементы добавляются в начало, а не в конец (в этом отличие от java, например), что обеспечивает сложность операции O(1) (благодаря персистенстности), но при этом гораздо более дешевое, чем в Vector.

[@Musia17]

Все правильно. Но в коде выше элементы добавляются в конец — насколько я понимаю лист здесь не годится т.к. будет создаваться и копироваться целиком новый лист каждый раз — верно?

[@cs0ip]

Ну просто у вас в коде я вижу такие фрагменты

genList(sz - 1, sz +: res)

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

[@Musia17]

> Это как раз тот случай, когда нужно использовать List.

Да-да, здесь согласна — за это уточнение спасибо :)

[@roman_kashitsyn]

> элементы добавляются в конец
Можно добавлять в начало списка, а в конце сделать линейный reverse. Это довольно частый приём.

[@Musia17]

Не, не можно. Мы же по этому подрастающему листу каждый новый элемент проверяем поиском сначала — это всё-таки все еще trial-division.

[@roman_kashitsyn]

Я говорил про приём в общем, а не конкретно про задачу поиска простых. Для быстрой вставки в оба конца в Haskell есть Data.Sequence, основанная на Finger Trees (аналога в Scala я что-то сходу не нашёл, разве что в исходниках scalaz).

[@darkdimius]

Вы не правы. Vector в Scala это = RRB Tree infoscience.epfl.ch/record/169879/files/RMTrees.pdf

[@cs0ip]

Да, действительно. Как-то перепутал их из-за корзин по 32 элемента. А т.к. код читал поверхностно, то так и осталось это заблуждение. Спасибо за исправление.

[@potan]

В List эффективно добавление в начало. Часто удобно и эффективно наполнять список таким образом, а в конце инвертировать.