> Ни один нормальный человек на хаскиле не будет делать рекурсию вместо цикла > Я про циклы и не говорил чсх хммм....

> Ни один нормальный человек на хаскиле не будет делать рекурсию вместо цикла > Я про циклы и не говорил чсх хммм....

Стандартные комбинаторы есть для всего. Внутри там рекурсия конечно, но кому это не пофиг кроме Саши и ему подобных?

btw, хвостовая рекурсия вместо цикла вполне себе норм паттерн

btw, хвостовая рекурсия вместо цикла вполне себе норм паттерн

Нет. Рекурсивные алгоритмы сложнее чем интерактивные аналоги. Годные гайдлайны карают за рекурсию без веских оснований, т.е. почти любую

Нет. Рекурсивные алгоритмы сложнее чем интерактивные аналоги. Годные гайдлайны карают за рекурсию без веских оснований, т.е. почти любую

Итеративные

И кто там за рекурсию карает?

И кто там за рекурсию карает?

Тот кто карает за рекурсию ?

Логично

рекурсивно!

И кто там за рекурсию карает?

И кто там за рекурсию карает?

Итеративные

Это андроед исказил меня

@bertolu4i и эт, почитай про хаскель, правда. смешно от тебя высеры читать

И кто там за рекурсию карает?

Я когда делаю коде ревью. Ибо не хочу внизапного SO на ровном месте

Тебе же сказали про tail rec

Там не будет so

Тебе же сказали про tail rec

В голанге?

@bertolu4i рекурсивные алгоритмы намного проще итеративных, но их нужно применять с умом, особенно в языках, где нет оптимизации хвостовой рекурсии

В голанге?

Причём тут голанг, речь про Хаскель была

В Голанге впринципе оптимизации нет)

Причём тут голанг, речь про Хаскель была

При том что у нас тут чат по го и кодеревью я делаю на нём

При том что у нас тут чат по го и кодеревью я делаю на нём

Тогда не пиши тут слово хаскель никогда) и вообще не лезь туда больше, прошу

Коллеги

Сбавьте тон, а то придется вас банить

Нет. Рекурсивные алгоритмы сложнее чем интерактивные аналоги. Годные гайдлайны карают за рекурсию без веских оснований, т.е. почти любую

такс такс такс, я может что-то не так понимаю, но вроде как если кому-то захочется написать qsort/mergesort без рекурсии, то ему придётся вручную работать со стеком, да и вообще сложность возрастает в разы

такс такс такс, я может что-то не так понимаю, но вроде как если кому-то захочется написать qsort/mergesort без рекурсии, то ему придётся вручную работать со стеком, да и вообще сложность возрастает в разы

приведи алгоритм, о котором ты говоришь, иначе нет предмета для разговора

А про Хаскель есть чатик?

А про Хаскель есть чатик?

Есть

А почему вы не там?

Я там есть

приведи алгоритм, о котором ты говоришь, иначе нет предмета для разговора

быстрая сортировка и сортировка слиянием

Я там есть

Ну, ты - это хорошо... я не тебя имел в виду :)

вообще все D&Q алгоритмы удобнее рекурсией делаются. но насколько часто вы в работе реализуете такие алгоритмы?

быстрая сортировка и сортировка слиянием

ок. покажи код быстрой сортировки с рекурсией, который ты считаешь оптимальным

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

когда дело доходит до реализации общих алгоритмов вроде сортировки каждая наносекунда на счету

код в студию

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

Оптимизации помогают развернуть рекурсивный алгоритм ж. Все ок будет

Господа, топящие за рекурсию. Приведите код быстрой сортировки с рекурсией, или вы пустые болтуны

Господа, топящие за рекурсию. Приведите код быстрой сортировки с рекурсией, или вы пустые болтуны

http://wiki.c2.com/?QuickSortInHaskell

http://wiki.c2.com/?QuickSortInHaskell

спасибо.

http://wiki.c2.com/?QuickSortInHaskell

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

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

Чего?)))

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

Тут я уже вмешаюсь Pawel, приведите результаты бенчмарка, иначе чем вы лучше тех, кого вы ругаете за отсутствие примеров?

Оптимизации помогают развернуть рекурсивный алгоритм ж. Все ок будет

В хаскеле с оптимизацией хвоста не всё так просто из-за лени.

В хаскеле с оптимизацией хвоста не всё так просто из-за лени.

Везде не все так просто )

Тут я уже вмешаюсь Pawel, приведите результаты бенчмарка, иначе чем вы лучше тех, кого вы ругаете за отсутствие примеров?

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

предлагаю оценить красоту этого кода

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

Ну естественно копируется, никто ж не говорил про in place

Господа, топящие за рекурсию. Приведите код быстрой сортировки с рекурсией, или вы пустые болтуны

https://play.rust-lang.org/?gist=75342b7290702231c4a42ad920d35d2b&version=stable&mode=debug&edition=2015

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

код между прочим не студент написал, а PhD

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

ща в хаскеле появятся линейные типы и можно будет писать типобезопасные чистые in place мутации, тогда хаскелевская быстрая сортировка будет ничем не хуже

если хвост можно оптимизировать, значит это итеративный алгоритм написанный через рекурсию

можно и привести, но бенчмарк там не нужен, достаточно посмотреть на структуры данных и контекст их использования. Там копируются списки, для этого выделяются дополнительные чанки на каждой итерации алгоритма. Вот вам код быстрой сортировки на хаскиле, котрый по эффективности вроде бы аналогичен итеративному. И тред с пояснениями https://www.reddit.com/r/coding/comments/codqo/engineering_large_projects_in_a_functional/c0ur6yx/

То есть бенчмарков нету Ну, всё ясно

То есть бенчмарков нету Ну, всё ясно

А их и не будет, написать такое сравнение практически нереально

Не через time же замеры делать)

Я вообще не понимаю зачем сравнивать скорости кстати Если рекурсивный подход удобнее – например при обходе структур, то лучше использовать его И наоборот Ты всё равно упрешься почти всегда во что-то другое

То есть бенчмарков нету Ну, всё ясно

при чём тут бенчмарки , если реализация на хаскиле имеет сложность бОльшую, чем O ( n log ⁡ n ) ??

Идея в том, что писать классические императивные алгоритмы на фп языках - это извращение. И наоборот

https://play.rust-lang.org/?gist=75342b7290702231c4a42ad920d35d2b&version=stable&mode=debug&edition=2015

не знаю на счёт аморт. сложности, но этот код не читается проще аналогичного гошного

при чём тут бенчмарки , если реализация на хаскиле имеет сложность бОльшую, чем O ( n log ⁡ n ) ??

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

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

ну так она сложнее чем гошная. я же сылку выше приводил

при чём тут бенчмарки , если реализация на хаскиле имеет сложность бОльшую, чем O ( n log ⁡ n ) ??

Вам, как человеку якобы пишущему высокопроизводительные приложения, следовало знать, что О большое вообще говоря не определяет скорость алгоритма, а определяет увеличение сложности при росте каких-то параметров Ничто не мешает алгоритму O(n^3) быть быстрее алгоритма O(n^2), всё зависит от кучи условий

не знаю на счёт аморт. сложности, но этот код не читается проще аналогичного гошного

аналогичный гошный код будет усыпан пустыми интерфейсами и тайп ассершенами

при чём тут бенчмарки , если реализация на хаскиле имеет сложность бОльшую, чем O ( n log ⁡ n ) ??

Ох, ты ещё и в оценки не умеешь

Вам, как человеку якобы пишущему высокопроизводительные приложения, следовало знать, что О большое вообще говоря не определяет скорость алгоритма, а определяет увеличение сложности при росте каких-то параметров Ничто не мешает алгоритму O(n^3) быть быстрее алгоритма O(n^2), всё зависит от кучи условий

при таких сравннеиях алгоритмов на разных языкакх нет вообще ни каких оснований считать что О на хаскиле будет меньше чем О на Го

ERROR: S client not available

при таких сравннеиях алгоритмов на разных языкакх нет вообще ни каких оснований считать что О на хаскиле будет меньше чем О на Го

И что?

мне кажется вы извращаете понятие O

при таких сравннеиях алгоритмов на разных языкакх нет вообще ни каких оснований считать что О на хаскиле будет меньше чем О на Го

Давай ты напишешь такой же алгоритм на го, не in place и убедишься на сколько там все проще

Я бы вообще не стал бы делать никаких предположений о виде роста сложности, учитывая что у нас идёт оптимизация на каждом слое: от трансляции до исполнения на функциональных блоках И это ещё без учета кэшей и предективной выгрузки из памяти

И что?

вопрос риторический

насколько я помню О - это относительная величина, она не сравнивает языки и их возможности.

Я бы вообще не стал бы делать никаких предположений о виде роста сложности, учитывая что у нас идёт оптимизация на каждом слое: от трансляции до исполнения на функциональных блоках И это ещё без учета кэшей и предективной выгрузки из памяти

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

Давай ты напишешь такой же алгоритм на го, не in place и убедишься на сколько там все проще

И с реализацией списков на го

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

Так нас интересует сложность реализации или производительность кода? Вы уж определитесь

Так нас интересует сложность реализации или производительность кода? Вы уж определитесь

не производительность бинарника, а гарантии по аморт. сложности

не производительность бинарника, а гарантии по аморт. сложности

Нет никаких гарантий

Откуда?

не производительность бинарника, а гарантии по аморт. сложности

асимптотическая сложность - это свойство алгоритма, а не реализации как бы

не производительность бинарника, а гарантии по аморт. сложности

что вы понимаете под аморт. сложностью?

Нет никаких гарантий

Есть гарантии - O (n * log n) и O(1) по памяти. "Простой" алгормитм на хаскеле их не даёт, и по фигу что О может быть разным

и какое отношение она имеет к inplace квиксорту?

аморт - амортизированная?

Есть гарантии - O (n * log n) и O(1) по памяти. "Простой" алгормитм на хаскеле их не даёт, и по фигу что О может быть разным

"Простой" алгоритм на хаскеле не является квиксортом, это каждому первокурснику очевидно

где что амортизируется в inplace qsort?

"Простой" алгоритм на хаскеле не является квиксортом, это каждому первокурснику очевидно

?

Есть гарантии - O (n * log n) и O(1) по памяти. "Простой" алгормитм на хаскеле их не даёт, и по фигу что О может быть разным

Да? Так вас всё таки интересует потребление памяти, а не скорость работа или простота реализации? А у вас есть результаты замеров?

"Простой" алгоритм на хаскеле не является квиксортом, это каждому первокурснику очевидно

какой мне дали, про тот я написал

честно говорят алгоритмы с нуля это какая то узкая совсем ниша

"все украдено до нас"

честно говорят алгоритмы с нуля это какая то узкая совсем ниша

Разумеется

?

у алгоритма быстрой сортировки есть свойства, которым "простой" алгоритм на хаскеле не удовлетворяет

я правильно понимаю что тут обсуждается тот факт, что рекурсивный qsort на иммутабельном списке менее предпочтителен чем inplace? ?

Да? Так вас всё таки интересует потребление памяти, а не скорость работа или простота реализации? А у вас есть результаты замеров?

да, меня интересует скорость и гарантии по потреблению памяти. Вы не согласны с тем, что "прстой" квиксорт на хакеле сложнее чем O (n * log n) / O(1) ?

я правильно понимаю что тут обсуждается тот факт, что рекурсивный qsort на иммутабельном списке менее предпочтителен чем inplace? ?

?

и на этом основании делается выовод что хаскель - отстой? )))

я правильно понимаю что тут обсуждается тот факт, что рекурсивный qsort на иммутабельном списке менее предпочтителен чем inplace? ?

"рекурсивный qsort на иммутабельном списке" - это школотронство, предназначенное для обучения, а не реального применения.

у алгоритма быстрой сортировки есть свойства, которым "простой" алгоритм на хаскеле не удовлетворяет

Например?