#prog #haskell
Товарищ Мёртвопищ написал небольшую библиотеку для облегчения кастомизации (де)сериализации, реализованных при помощи тайпклассов Binary (того, который базируется на Generic).
github.com/0xd34df00d/binary-generic-combinators
Товарищ Мёртвопищ написал небольшую библиотеку для облегчения кастомизации (де)сериализации, реализованных при помощи тайпклассов Binary (того, который базируется на Generic).
github.com/0xd34df00d/binary-generic-combinators
GitHub
GitHub - 0xd34df00d/binary-generic-combinators: Combinators and utilities to make Generic-based deriving of Binary easier and more…
Combinators and utilities to make Generic-based deriving of Binary easier and more expressive - GitHub - 0xd34df00d/binary-generic-combinators: Combinators and utilities to make Generic-based deriv...
#prog #haskell #article
Статья (pdf) о технике, позволяющей запрограммировать регионы для выделения ресурсов (таких, как открытые файлы), удостоверяющие, что все выделенные ресурсы освобождены в конце региона (а не вычисления в целом, как в ST), что ручки к выделенным ресурсам не утекают из вычислений, корректно прокидывающее исключения (с деаллокацией ресурсов при досрочном завершении вычислений в регионе) и позволяющее вкладывать регионы один в другой без передачи значений-свидетельств вложенности регионов.
Статья (pdf) о технике, позволяющей запрограммировать регионы для выделения ресурсов (таких, как открытые файлы), удостоверяющие, что все выделенные ресурсы освобождены в конце региона (а не вычисления в целом, как в ST), что ручки к выделенным ресурсам не утекают из вычислений, корректно прокидывающее исключения (с деаллокацией ресурсов при досрочном завершении вычислений в регионе) и позволяющее вкладывать регионы один в другой без передачи значений-свидетельств вложенности регионов.
ACM SIGPLAN Notices
Lightweight monadic regions | ACM SIGPLAN Notices
We present Haskell libraries that statically ensure the safe use of resources such
as file handles. We statically prevent accessing an already closed handle or forgetting
to close it. The libraries can be trivially extended to other resources such as ...
as file handles. We statically prevent accessing an already closed handle or forgetting
to close it. The libraries can be trivially extended to other resources such as ...
#prog #haskell #article
Статья (бесстыдно стыренная с Haskell wiki) о дизайне и разработке библиотеки для красивого вывода (pretty printing) выражений.
В данной работе автор решает формализовать красивый вывод, как вывод, удовлетворяющий трём принципам (в порядке убывания важности):
1. Видимость — весь вывод должен умещаться в пределах указанной ширины.
2. Разборчивость — в выводе должна быть видна иерархичная структура данных.
3. Бережливость — вывод должен занимать как можно меньше строк.
Данная библиотека отнюдь не первая, решающая эту задачу, поэтому автор также вскользь касается прошлых библиотек — и замечает, что, ввиду использования жадных подходов, они не дают вышеозначенные свойства.
Автор сначала строит наивный алгоритм, фактически строящий все возможные варианты и выбирающий среди них наилучший — и потому ожидаемо имеющий экспоненциальное время работы — а затем вводит две оптимизации, радикально снижающие время работы за счёт раннего отбрасывания заведомо негодных вариантов. Для обеих оптимизаций автор приводит доказательства их корректности.
Разумеется, автор также проводит замеры производительности библиотеки. Эмпирические результаты показывают, что время, потраченное на вычисления оптимальной раскладки, линейно пропорционально числу строк в итоговом выводе. К сожалению, автор не даёт строгого доказательства линейности данного алгоритма, ограничиваясь правдоподобными рассуждениями (а жаль, я бы почитал).
Сравнение с прошлыми библиотеками показывает, что библиотека автора работает примерно на порядок медленнее state of art на тот момент, что автор считает удовлетворительным с учётом того, что эта библиотека, в отличие от предыдущих, достигает оптимальности раскладки согласно принципам выше.
Статья (бесстыдно стыренная с Haskell wiki) о дизайне и разработке библиотеки для красивого вывода (pretty printing) выражений.
В данной работе автор решает формализовать красивый вывод, как вывод, удовлетворяющий трём принципам (в порядке убывания важности):
1. Видимость — весь вывод должен умещаться в пределах указанной ширины.
2. Разборчивость — в выводе должна быть видна иерархичная структура данных.
3. Бережливость — вывод должен занимать как можно меньше строк.
Данная библиотека отнюдь не первая, решающая эту задачу, поэтому автор также вскользь касается прошлых библиотек — и замечает, что, ввиду использования жадных подходов, они не дают вышеозначенные свойства.
Автор сначала строит наивный алгоритм, фактически строящий все возможные варианты и выбирающий среди них наилучший — и потому ожидаемо имеющий экспоненциальное время работы — а затем вводит две оптимизации, радикально снижающие время работы за счёт раннего отбрасывания заведомо негодных вариантов. Для обеих оптимизаций автор приводит доказательства их корректности.
Разумеется, автор также проводит замеры производительности библиотеки. Эмпирические результаты показывают, что время, потраченное на вычисления оптимальной раскладки, линейно пропорционально числу строк в итоговом выводе. К сожалению, автор не даёт строгого доказательства линейности данного алгоритма, ограничиваясь правдоподобными рассуждениями (а жаль, я бы почитал).
Сравнение с прошлыми библиотеками показывает, что библиотека автора работает примерно на порядок медленнее state of art на тот момент, что автор считает удовлетворительным с учётом того, что эта библиотека, в отличие от предыдущих, достигает оптимальности раскладки согласно принципам выше.
#prog #regex #parsing #haskell
Fix-ing regular expressions
TL;DR: We add variables, let bindings, and explicit recursion via fixed points to classic regular expressions. It turns out that the resulting explicitly recursive, finitely described languages are well suited for analysis and introspection.
Если читали мои претензии к регулярным выражениям, то наверняка помните, что одной из моих претензий было отсутствие декомпозируемости. В статье это решается за счёт добавления явных переменных (точнее, привязок в форме
К сожалению, не обошлось без ложки дёгтя: даже с некоторыми оптимизациями производительность итогового решения оставляет желать лучшего — что, в принципе, вполне ожидаемо, учитывая, что распознавание использует подход regular expression derivatives, который при применении в лоб приводит к сильному распуханию промежуточных структур данных. А ещё лично меня несколько расстраивает использование в финальной версии fix и полиморфной рекурсии — это означает, что итоговый результат не переносим в лоб на другие ЯП.
Fix-ing regular expressions
TL;DR: We add variables, let bindings, and explicit recursion via fixed points to classic regular expressions. It turns out that the resulting explicitly recursive, finitely described languages are well suited for analysis and introspection.
Если читали мои претензии к регулярным выражениям, то наверняка помните, что одной из моих претензий было отсутствие декомпозируемости. В статье это решается за счёт добавления явных переменных (точнее, привязок в форме
let x = r in re). Также добавление явного fix расширяет возможности языка и даёт возможность использовать рекурсию. На практике это означает, что подобное решение в состоянии распарсить известный пример грамматики, являющейся контекстно-зависимой: aⁿbⁿ.К сожалению, не обошлось без ложки дёгтя: даже с некоторыми оптимизациями производительность итогового решения оставляет желать лучшего — что, в принципе, вполне ожидаемо, учитывая, что распознавание использует подход regular expression derivatives, который при применении в лоб приводит к сильному распуханию промежуточных структур данных. А ещё лично меня несколько расстраивает использование в финальной версии fix и полиморфной рекурсии — это означает, что итоговый результат не переносим в лоб на другие ЯП.
Блог*
#prog #js #typescript #abnormalprogramming github.com/jamiebuilds/json-parser-in-typescript-very-bad-idea-please-dont-use
GitHub
GitHub - dmjio/type-level-json: RFC8259 compliant JSON parser, at the type level.
RFC8259 compliant JSON parser, at the type level. Contribute to dmjio/type-level-json development by creating an account on GitHub.
#prog #go #haskell #article
Сложность простоты
Или о том, как Haskell показал себя лучше на задаче, для которых Go преподносится хорошим решением, с точки зрения человека, который и то, и то знал слабо.
Статья старая в том смысле, что она написана до того, как в Go запилили дженерики, но выводы и сейчас остаются валидными.
Сложность простоты
Или о том, как Haskell показал себя лучше на задаче, для которых Go преподносится хорошим решением, с точки зрения человека, который и то, и то знал слабо.
Статья старая в том смысле, что она написана до того, как в Go запилили дженерики, но выводы и сейчас остаются валидными.
Хабр
Сложность простоты
Как я писал в предисловии предыдущей статьи, я нахожусь в поисках языка, в котором я мог бы писать поменьше, а безопасности иметь побольше. Моим основным языком...
Блог*
Все же уже слышали про новый формат QOI (quite ok image format, qoiformat.org), который lossless сжимает картинки +- так же хорошо, как PNG, но при этом в 20-50 раз быстрее, а его спецификация умещается на одну страницу? Хотели бы кодинг стрим где я бы подумал…
#prog #haskell #article
ТоварищМёртвопищ 0xd34df00d написал декодер и енкодер QOI на хаскелле. И весьма быстрые.
Haskell is quite OK for images: decoding QOI
Haskell is quite OK for images: encoding QOI
Товарищ
Haskell is quite OK for images: decoding QOI
Haskell is quite OK for images: encoding QOI
#prog #haskell #article
Why 'Functor' Doesn't Matter
Names can’t transmit meaning. They can transmit a pointer, though, which might point to some meaning. If that meaning isn’t the right meaning, then the recipient will misunderstand. <...>
Object Oriented Programming is littered with terrible names, precisely because they mislead and cause a false familiarity. Object, Class, Visitor, Factory, Command, Strategy, Interface, Adapter, Bridge, Composite. All of these are common English words with a relatively familiar understanding to them. And all of them are misleading.
Why 'Functor' Doesn't Matter
Names can’t transmit meaning. They can transmit a pointer, though, which might point to some meaning. If that meaning isn’t the right meaning, then the recipient will misunderstand. <...>
Object Oriented Programming is littered with terrible names, precisely because they mislead and cause a false familiarity. Object, Class, Visitor, Factory, Command, Strategy, Interface, Adapter, Bridge, Composite. All of these are common English words with a relatively familiar understanding to them. And all of them are misleading.
www.parsonsmatt.org
Why 'Functor' Doesn't Matter
Alternative, less click-baity title: Names Do Not Transmit Meaning
#prog #haskell #article
GADTs
Статья, которая показывает с опорой на лемму Йонеды, что GADT чисто технически не является чем-то, увеличивающим выразительность языка, и что GADT могут быть выражены на обычных ADT (не G) при наличии в языке полиморфизма второго ранга.
GADTs
Статья, которая показывает с опорой на лемму Йонеды, что GADT чисто технически не является чем-то, увеличивающим выразительность языка, и что GADT могут быть выражены на обычных ADT (не G) при наличии в языке полиморфизма второго ранга.
Haskellforall
GADTs
Prelude Some time ago I asked a question on /r/haskell about what unique purpose GADTs served that other language features could not prov...
#prog #haskell #article
Unique sample drawing & searches with List and StateT --- "Send more money"
Или про то, как интерпретация списка как недетерминированного значения позволяет очень ясно записать решение задачи с ограничениями и при этом задействовать ранний бектрекинг.
Unique sample drawing & searches with List and StateT --- "Send more money"
Или про то, как интерпретация списка как недетерминированного значения позволяет очень ясно записать решение задачи с ограничениями и при этом задействовать ранний бектрекинг.
in Code
Unique sample drawing & searches with List and StateT --- "Send more money"
Nothing too crazy today, just a cute (basic/intermediate) haskell trick as a response to Mark Dominus’s excellent Universe of Discourse post on Easy exhaustive search with the list monad intended for people new or unfamiliar with haskell demonstrating the…