Мой пост, мне хочется верить, тоже полезный, потому что дает возможность сформировать более взвешенное мнение о чисто функциональных языках и их ограничениях.
Не уверен ни про взвешенное, ни про ограничия. Мнение Харропа никогда взвешенным не было, хотя некоторые вещи он подмечает хорошо. Но, чтобы отделить зерна от плевел в его потах нужно понимать как и почему, все работает, т.е. разбираться в функциональных языках на хорошем уровне.
А так же о том, как осторожно надо относиться к хайпу по поводу какой бы то ни было технологии.
Вот с этим согласен, в т.ч. и про функциональные языки и там не все идеально.
Тем не менее, если я правильно понимаю, правильное решето Эратосфена без priority queue в нем, скорее всего, до сих реализовать нельзя.
Более-менее осмысленное императивное (а решето эратосфена это императивный алгоритм) решение можно было получить, когда появились массивы (array), библиотека от 2007 года, статью искать лень. С появлением пакета vector 2008 год, но не входит в стандарт, стало ещё проще. Учитывая, что ST уже было, то можно даже изолировать алгоритм и получить чистый результат как er n = V.toList $ runST $ do { x <- new 0; run x ; return $ unsafeFreeze x }.
При этом строчек будет столько же или меньше, вот некоторые будут выглядеть хуже, т.к. вместо привычного всем a[i] = 0 будет unsafeWrite a i, в случае не возникающего в задаче a[i] = b[j] будет ещё хуже unsafeWrite a i =<< unsafeRead b j. Для меня учитывая количество получаемых плюсов этот синтаксис большой проблемой не является.
Почему там был использован prioity queue я не знаю, видимо кому-то хотелось получить алгоритм полностью в функциональном стиле, но я не знаю как это можно сделать эффективно без хорошей поддержи компилятора и более продвинутой системы типов, которой в ghc ещё нет. И главное я не знаю зачем нужно пиать полностью функциональную версию в чисто императивном алгоритме, если в языке есть прекрасная поддержка императивности и локализуемой изменяемости.
Харроп то ладно, он всегда был жирным троллем, который не умеет цитировать даже собственные reddit треды, в чем легко можно убедиться пройдя по ссылкам в его посте, но он хотя бы полезный, т.к. пару раз (не преувеличение) после поднятого хайпа интересные вещи в компилятр допиливали.
Но тут интереснее спросить у автора, а насколько у него глубокий уровень экспертизы в Haskell для того, чтобы оставлять подобные
[quote]Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.[/quote]
Если охота потроллить haskell советую взять более современные посты, например, про hashtable и поспрашивать у haskell-истов почему они тормозят. Это гораздо полезнее интереснее и ближе к реальности.
При всём при этом, у меня есть личные конкретные баттхёрты от quality of implementation в случае конкретного ghc — в сколь угодно нетривиальных параллельных программах GC начинает жрать непомерно много времени, потому что GC там хоть и параллельный, но не конкурентный, привет stop-the-world, если даже всего один HEC выжрал свой и соседние allocation area. Но это не свойство языка, впрочем. Либо, не отрицаю, я просто не умею писать многопоточные программы на хаскеле.
Проблема тут не в quality of implementation, а в tradeoff между throughput и latency и предсказуемости того, сколько памяти может отжирать программа на пустом месте. Если важна latency и пофиг на память, то можно идти путём go. Если не важен sharing структур между потоками, то можно делать как Erlang.
В целом ветка non-blocking-gc есть, но те тесты, что были показали, что в большинстве случаев усложнение реализации не окупается. Ну и важно помнить, что до ghc 8.0 очень неудачные RTS опции по умолчанию. Так +RTS -A254m -qb0 -ki{size-of-l1-cache} зачастую очень сильно улучшает поведение (после 8.0 -qb0 не нужно, т.к. он выставляется динамически).
Вполне возможно делать это в 2 статьи или доп параграфом, т.к. часто возникают вопросы, а как правильно сделать зипперы для той или иной структуры данных и эти "заумности" дают весьма точный ответ. В принципе добавления общей информации и ссылки на статьи вполне достаточно, например, тем кто представляет что такое зипперы, но не теорию за этим стоящую.
Имелось ввиду uniform/non-uniform, но вообще правильный термин который тут должен был быть, это CPU memory model. Так, что из просвещения могу только к нему отослать, чтобы лишний раз не запутать.
data Figure = forall x . (Typeable x, Paint x) => Figure x
Далее безопасно кастуете и выбираете наздоровье. В добавок можно ещё и красивые линзы прикрутить.
В целом использование явного словаря data D = D { ... } или невного класса-типов D это достаточно близкие методы, с небольшой разницей, вроде той, что в случае класса типов, для одного параметра у нас гарантируется наличие единственной реализации функций, чего нету в случае явного словаря. Так-же из функций класса типов мы можем достать сам словарь Dict (c::Constraint) и передавать его явно или восстановить его по прокси переменной. Все тоже самое возможно и с явным словарём, но с большим количеством страданий.
Извините, я не понял к чему это утверждение, но повторю вопрос, котрый видимо был непонят. Я спрашиваю частный вид полиморфизма, а именно полиморфизм через подтипирование, встречается ли где либо кроме ООП языков.
> Монады — это костыль, позволяющий спрятать изменяемое состояние под ковёр, притворившись будто его нет.
Я, конечно, не уверен, но мне кажется что перед тем как высказывать экспертное мнение, стоит ознакамливаться с материалом. Тогда будет понятно зачем монады были введены, как используются и чем могут быть заменены и в каких языках.
Хочется отметить, что existential quantification тут используется, но идёт оно из коробки. Инженерный смысл данного расширения в том, что мы таскаем словарь вместе с типом данных в рантайм (что я так понимаю делается в Go всегда), т.е. позволяет делать массив чего-то, что является instance of Figure. В Haskell классы типов (которые чуть-чуть похожи на instance) разрешаются в compile time, но существуют случаи когда этого не достаточно, как в этом примере
В целом согласен.
Кстати, я слышу от хаскелистов то, что они выбирают Haskell, т.к. он дает им возможность качествено и быстро писать софт и легко его поддерживать, при этом у большинства их них в бекграунде есть пачка императивных языков, включая Go. Я правда с Go не знаком настолько, чтобы обсуждать его в данном контексте (практики написания крутых программ). Произошло это т.к. причин продолжать его изучение дальше, чем базовые tutorial-ы, я не увидел. Но даже на этом уровне по сравнению с другими языками той же категории (на мой взгляд python и компания, он выглядит вполне пристойно). Т.е. если я, по какой-то причине, возьмусь писать крутой софт на Go, то я буду страдать от отсуствия возможностей, которые я хотел бы видеть, в языке и с которыми привык работать (те самые теоритические обоснования). В тоже время, замечу, есть достаточно мало областей, где эти причины стали бы для непреодолимой проблемой. как-то так…
мне определенно не нравится деление на «теоретиков» и «практиков», это похоже на попытку спрятатья за какую-то ширмочку. Но в целом в «реальном мире» указанные «теоритические» технологии вполне себе успешно используются. Ну и ещё раз скажу, чуть другими словами, хорошесть/плохость языка и применимость или уместность его для конкретного проекта выполняемого конкретной комадной это разные категории.
Не уверен ни про взвешенное, ни про ограничия. Мнение Харропа никогда взвешенным не было, хотя некоторые вещи он подмечает хорошо. Но, чтобы отделить зерна от плевел в его потах нужно понимать как и почему, все работает, т.е. разбираться в функциональных языках на хорошем уровне.
Вот с этим согласен, в т.ч. и про функциональные языки и там не все идеально.
https://hackage.haskell.org/package/vector-algorithms-0.7.0.1/docs/Data-Vector-Algorithms-Tim.html
Но тут интереснее спросить у автора, а насколько у него глубокий уровень экспертизы в Haskell для того, чтобы оставлять подобные
[quote]Прим. перев.: Это перевод истории о том, как нелегко оказалось написать параллельную быструю сортировку (quicksort) на Хаскеле. Оригинал статьи написан в 2010 году, но, мне кажется, он до сих пор поучительный и во многом актуальный.[/quote]
Если охота потроллить haskell советую взять более современные посты, например, про hashtable и поспрашивать у haskell-истов почему они тормозят. Это гораздо полезнее интереснее и ближе к реальности.
Проблема тут не в quality of implementation, а в tradeoff между throughput и latency и предсказуемости того, сколько памяти может отжирать программа на пустом месте. Если важна latency и пофиг на память, то можно идти путём go. Если не важен sharing структур между потоками, то можно делать как Erlang.
В целом ветка non-blocking-gc есть, но те тесты, что были показали, что в большинстве случаев усложнение реализации не окупается. Ну и важно помнить, что до ghc 8.0 очень неудачные RTS опции по умолчанию. Так
+RTS -A254m -qb0 -ki{size-of-l1-cache}
зачастую очень сильно улучшает поведение (после 8.0-qb0
не нужно, т.к. он выставляется динамически).data Figure = forall x . (Typeable x, Paint x) => Figure x
Далее безопасно кастуете и выбираете наздоровье. В добавок можно ещё и красивые линзы прикрутить.
В целом использование явного словаря
data D = D { ... }
или невного класса-типовD
это достаточно близкие методы, с небольшой разницей, вроде той, что в случае класса типов, для одного параметра у нас гарантируется наличие единственной реализации функций, чего нету в случае явного словаря. Так-же из функций класса типов мы можем достать сам словарьDict (c::Constraint)
и передавать его явно или восстановить его по прокси переменной. Все тоже самое возможно и с явным словарём, но с большим количеством страданий.Я, конечно, не уверен, но мне кажется что перед тем как высказывать экспертное мнение, стоит ознакамливаться с материалом. Тогда будет понятно зачем монады были введены, как используются и чем могут быть заменены и в каких языках.
Кстати, я слышу от хаскелистов то, что они выбирают Haskell, т.к. он дает им возможность качествено и быстро писать софт и легко его поддерживать, при этом у большинства их них в бекграунде есть пачка императивных языков, включая Go. Я правда с Go не знаком настолько, чтобы обсуждать его в данном контексте (практики написания крутых программ). Произошло это т.к. причин продолжать его изучение дальше, чем базовые tutorial-ы, я не увидел. Но даже на этом уровне по сравнению с другими языками той же категории (на мой взгляд python и компания, он выглядит вполне пристойно). Т.е. если я, по какой-то причине, возьмусь писать крутой софт на Go, то я буду страдать от отсуствия возможностей, которые я хотел бы видеть, в языке и с которыми привык работать (те самые теоритические обоснования). В тоже время, замечу, есть достаточно мало областей, где эти причины стали бы для непреодолимой проблемой. как-то так…