LINUX.ORG.RU

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


0

0

В классическом понимании алгоритм это последовательность неких шагов для достижения результата. Достаточно вспомнить теже схемы алгоритмов.

Собственно вопрос: как спроецировать "стандартные" алгоритмы на функциональное программирование? Ведь декларативнео программирование тем и замечательно что избавляет от явного задание шагов решения задачи. Зависит ли эффективность алгоритма от парадигмы реализации? Как правильнее формализовать такие алгоритмы? В виде математической нотации? Если да, то в какой именно?

★★★★★

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

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

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

ott ★★★★★ ()
Ответ на: [ФП] Алгоритмы от ugoday

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

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

dizza ★★★★★ ()
Ответ на: [ФП] Алгоритмы от Pi

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

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

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

dizza ★★★★★ ()

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

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

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

Pi ★★★★★ ()
Ответ на: [ФП] Алгоритмы от Pi

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

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

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

dizza ★★★★★ ()
Ответ на: [ФП] Алгоритмы от ott

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

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

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

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

mannaz ()
Ответ на: [ФП] Алгоритмы от ugoday

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

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

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

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

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

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

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

ugoday ★★★★★ ()
Ответ на: [ФП] Алгоритмы от ugoday

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

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

Аминь.

anonymous ()
Ответ на: [ФП] Алгоритмы от ugoday

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

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

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

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

dizza ★★★★★ ()
Ответ на: [ФП] Алгоритмы от dizza

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

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

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

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

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

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

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

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

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

dizza ★★★★★ ()
Ответ на: [ФП] Алгоритмы от dizza

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

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

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от mannaz

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

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

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

doctor ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

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

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

dizza ★★★★★ ()
Ответ на: [ФП] Алгоритмы от dizza

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

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

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

dave ★★★★★ ()
Ответ на: Re: [ФП] Алгоритмы от mannaz

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

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

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

Waterlaz ★★★★★ ()
Ответ на: [ФП] Алгоритмы от dizza

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

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

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

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

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

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

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

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

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

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

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

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

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

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

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

>darcs

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

anonymous ()
Ответ на: Re: [ФП] Алгоритмы от anonymous

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

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

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

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

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

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

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

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.