Previous Entry Share Next Entry
photo25

как научиться ФП (repost)

Оригинал взят у bvlb в как научиться ФП
Очень просто: запрещаешь себе менять переменные. Сам с собой договорился: менять переменные больше не буду. Никогда. На характер. Функции в результате становятся чистыми, циклов больше нет, приходится юзать мапы, фолды и прочие рекурсии. Объекты перестают быть гм.. аккумуляторами и аренами и начинают под действиями функций переходить в другие объекты, подозрительно напоминая всякие там алгебраические структуры над разными множествами. Дальше архитектура становится пиздецом и приходится лезть в гугл, смотреть разные либы и придумывать как композировать функции и вылезать из пиздеца. Мозг кипит, но переменных становится все меньше и баги как-то становятся пореже.

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


  • 1
ufm July 17th, 2015
qsort([]) -> [];
qsort([Pivot|Rest]) -> qsort([ X || X <- Rest, X < Pivot]) ++ [Pivot] ++ qsort([ Y || Y <- Rest, Y >= Pivot]).

rinnve July 17th, 2015
Я извиняюсь, но от qsort-а здесь только название. Не надо так делать.

(Deleted comment)
_winnie July 17th, 2015
Во-первых, pivot выбирать не как первый элемент, а из середины или медианный из середины-конца-начала.

Во-вторых, делать не квиксорт, а использовать другие алгоритмы. Например, introsort, у которого quicksort - это кусочек реализации (ещё два кусочка - это insertion sort для крошечных массивов, и heap sort для убийц quicksort).

В-третьих, у меня никак руки не доходят посмотреть внимательно на http://swizard.livejournal.com/197270.html

В-четвертых, quick sort для иммутабельных языков - совсем не quick, для иммутабельных - лучше merge sort.


Edited at 2015-07-17 09:34 pm (UTC)

rinnve July 18th, 2015
Квиксорт - изначально in-place алгоритм, основное его преимущество перед mergesort - O(1) затраты памяти, что в данном случае не соблюдается. Плюс, данная конкретная реализация деградирует до O(N^2) в случае уже отсортированного списка. Корректные реализации можно посмотреть, например, в исходниках библиотек Хаскеля.

ex_juan_gan July 17th, 2015
Возможно, это вам только так кажется; вы не знаете, что будет происходить с этим кодом на самом деле.

rinnve July 18th, 2015
Отчего же, я прекрасно знаю, что будет происходить с этим кодом, если список вдруг окажется уже отсортированным.

ex_juan_gan July 18th, 2015
Это стандартное поведение квиксорта, нет?

rinnve July 19th, 2015
Это стандартное поведение неправильно написанного квиксорта. Хоар ещё в оригинальной публикации рекомендовал pivot выбирать рандомно, чтобы свести шанс деградации до N^2 к минимуму.

ex_juan_gan July 21st, 2015
А кстати да, можно ли тут функционально написать случайный выбор пивота...

wizzard0 July 21st, 2015
Если случайный - то это IO которое читает из мира.
Если псевдослучайный - то это какое-то State где протаскивается сид RNG.

  • 1
?

Log in

No account? Create an account