[ФП] Алгоритмы

> В виде математической нотации? Если да, то в какой именно?

\lambda

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

в качестве примера можно привести книжку Purely Functional Data Structures - в ней рассматриваются реализации различных структур данных в ФП...

А можно пример? Хотелось бы конкретики, например нахождение вершин, смежных некоторой вершине. (Определение - если x-вершина, то Ux множество смежных ей ребер, тогда множество вершин X, смежных множеству ребер Ux, есть множество вершин, смежных вершине x).

и примитивно рекурсивные функции.

>и примитивно рекурсивные функции.

А вот это уже интереснее. Где можно почитать про это? Интересует именно теория.

>В классическом понимании алгоритм

нас почему-то учили, что "алгоритм" не имеет классического определения, а лишь интуитивное

http://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2...

? :)

>нас почему-то учили, что "алгоритм" не имеет классического определения, а лишь интуитивное

Ну я имел ввиду классическое интуитивное определение. То сомое, которое засело у всех в голове в виде шагов решения. Хочу узреть красоту декларативного программирования, но пока вижу примитивщину типа переворачивания списков и прочих стандартных примеров.

http://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D0%BC%D0%B1%D0%B4%D0%B0-%D0%B8%D1%8...

> функциональные алгоритмы могут получить прирост скорости за счет параллельного выполнения там, где это возможно

не стоит переоценивать возможности фп в параллельных вычислениях. Если нужен functional parallelism, то функциональность ну никак не поможет - все равно будет message passing в том или ином виде. Если data parallelism, то 90% процентов всего долговыполняющего кода - в циклах - а их распараллеливать в императивных языках научились достаточно давно, ациклические участки тоже. В чем большой профит от использования фп - не совсем ясно.

Чем меньше изменяемых объектов, тем больше простор для паралелилизма.

Организация message passing, распараллеливание циклов... Ты упоротый? После считанных минут использования ФП, человек достигает такого уровня чистой, незамутненной деталями абстракции, что ему становятся безразличными и смешными не только перечисленные тобою вещи, но и первоначальная задача в целом. Именно поэтому функциональщики за всю свою короткую жизнь успевают написать только полтора хеловорлда и на неделю пропадают из треда, если попросить их привести решение какой-нибудь задачи на их любимом языке.

ещё один ФПшниками обиженный

> Чем меньше изменяемых объектов, тем больше простор для паралелилизма.

Не правда. Immutable data не дают простор для параллелизма, а позволяют написать более безопасный код. Фактически - это actor модель, message passing без разделяемых *изменяемых* данных. Т.е. внутри нитей может быть совершенная вакханалия и разброд - полная императивщина и сайд-эффекты. И у этой модели весьма существенный минус - когда нам действительно нужны изменяемые разделяемые данные - она не подходит. Приходится иметь по копии в каждом треде (процессе) и при каждом изменении данных их нужно синхронизовать - получается и сильно накладно, и не сильно просто реализуемо. Более на мой взгляд удачная идея - это STM - она специально создана для того, чтобы избавить от ручного управления мьютексами, семафорами, мониторами и прочим низкоуровневым говном. Но опять же - она создана по большому счету для управления mutable shared data. Обе модели созданы для более простого, безопасного кодинга - за счет потерей в производительности, а не для создания "просторов параллелизма".

> внутри нитей ....

В целом согласен, вопрос только в размере этого "внутри нитей".

> когда нам действительно нужны изменяемые разделяемые данные

этого никогда не надо.

> этого никогда не надо.

Аминь.

>когда нам действительно нужны изменяемые разделяемые данные

Ну в целом верно, напомнб лишь, что данные у нас тут скорее всего алгебраические, т.е. представлениые функциями.

Сами функции не мутабельны, да. А вот поведение имитировать они могут любое, как с состоянием, так и без.

> Сами функции не мутабельны, да. А вот поведение имитировать они могут любое, как с состоянием, так и без.

Вот даже если они имитируют наличие состояния, то получаем те же самые проблемы, как и с настоящими изменяемыми данными.

>те же самые проблемы, как и с настоящими изменяемыми данными.

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

Как дополнение в том же хаскеле такие вот "грязные" данные обычно помечаются "несмываемым" маркером - монадическим типом.

Это все понятно. По теме, пока тут холиварят на тему ФП (кстати раньше холиварили на тему Лиспа, тенденция однако), я нашел занимательное чтиво, называется "Algorithms: A Functional Programming Approach". Там классические алгоритмы реализуют на хаскеле.

Для формализации алгоритмов видимо неплохи рекурсивные функции, типа так:

factorial(n) <- if n > 0 then n * factorial(n - 1) else 1, n принадлежит N

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

Что значит безопаснее?

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

Может, простить их, потому что они ньюфаги? Конечно, поначалу функциональная парадигма шокирует, но потом многим приходит понимание, что изменяемость тоже полезна, и они исправляются. В той же SICP в третьей главе написано о плюсах и минусах изменяемости

>Что значит безопаснее?

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

> Для остального кода (чистого) юнит-тесты не нужны.

Нужны. Например, для того, чтобы иметь референсную медленную реализацию и новую быструю.

>Именно поэтому функциональщики за всю свою короткую жизнь успевают написать только полтора хеловорлда и на неделю пропадают из треда, если попросить их привести решение какой-нибудь задачи на их любимом языке.

Соседняя темка про с++ демонтсрирует ровным счетом обратное

> По крайней мере весь такой потенциально опасный код будет локализован в монадических функциях,

Не правда. Сложноповторимы логические ошибки не только из-за сложностей со скрытым измененным состоянием возможны и даже не столько из-за них. Иди посмотри на баги в cl-darcs и удивись.

> Для остального кода (чистого) юнит-тесты не нужны.

Не правда. Зачем тогда quickcheck по твоему создали?

ЗЫ. Ты, видимо, еще одна жертва фп-пиара. Вот почитай[1] на досуге человека, который попытался использовать хаскелл в большом проекте.

[1] http://brainslugs.blogspot.com/2006/12/haskell-in-action.html

>Ты, видимо, еще одна жертва фп-пиара.

Может быть, может быть.

>Иди посмотри на баги в cl-darcs и удивись.

Онож на Common Lisp, это вообще причем здесь?

>который попытался использовать хаскелл в большом проекте.

Ну в общем ничем особо не удивили.

> Онож на Common Lisp, это вообще причем здесь?

Блин же, darcs конечно :).

>darcs

Полистал багтрекер. Ничего там интересного нету. Много проблем с производительностью. А так все норм. Никаких null-pointrt exception по крайней мере нету, большинство ошибок чисто логические аля забыл то-то, не учел то-то и тп.

> Полистал багтрекер. Ничего там интересного нету.

А как же critical и urgent баги, которые висят по месяцу? Почему хаскелл чудесным образом не избавил авторов от трудноуловимых багов?

> Много проблем с производительностью. А так все норм. Никаких null-pointrt exception по крайней мере нету,

Ну да - там же нет указателей. Сравни с багтрекером меркуриала или базаара, там тоже segmentation fault нет.

> большинство ошибок чисто логические аля забыл то-то, не учел то-то и тп.

Во-во и я про то же. Большинство ошибок логические - фп от их совершения не сильно защищает.