Как стать автором
Обновить
145.5
Карма
24.3
Рейтинг
Сергей Самойленко @samsergey

Руководитель, научный сотрудник, преподаватель

  • Подписчики 186
  • Подписки 1

Элегантный вопросительный знак

Занимательные задачки Haskell *Математика *Функциональное программирование *

В этой заметке я хочу поделиться элегантным решением одной задачи с сайта-хрестоматии RosettaCode. Речь пойдёт о программе, вычисляющей функцию Минковского — одного из инструментов теории чисел и динамических систем. Несмотря на то, что реализовать эту функцию относительно несложно (её код даже приводится в Википедии), имеет смысл подняться на достаточно высокий уровень абстракции, для того, чтобы увидеть предельно простое решение этой задачи. Ну, и получить удовольствие от красоты математики и языка Haskell.

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

Сначала мы обсудим саму функцию Минковского, потом разглядим в её действии изоморфизм между двумя алгебраическими структурами и уже с этих позиций напишем короткую программу на Haskell, и, конечно, обсудим что нам с этого всего будет.

Читать далее
Всего голосов 24: ↑24 и ↓0 +24
Просмотры 3.6K
Комментарии 15

Аппликативные регулярные выражения, как свободный альтернативный функтор

Haskell *Функциональное программирование *
Перевод

Предлагаю вашему вниманию перевод замечательной свежей статьи Джастина Ле. В своём блоге in Code этот автор достаточно легким языком рассказывает о математической сути красивых и изящных функциональных решений для практических задач. В этой статье подробно разбирается пример того, как перенос математической структуры, которую образуют данные в предметной области на систему типов программы, может сразу, как писали Джеральд и Сассман "автомагически", привести к работающему решению.


Приведённый на картинке код — это полноценная самодостаточная, расширяемая реализация парсера регулярных выражений, написанная "с нуля". Высший класс, настоящая магия типов!

Читать дальше →
Всего голосов 31: ↑30 и ↓1 +29
Просмотры 6.9K
Комментарии 5

Теория счастья. Статистика, как научный способ чего-либо не знать

Занимательные задачки Математика *Научно-популярное
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.


Речь в этой главе пойдёт о статистике, о погоде и даже о философии. Не пугайтесь, совсем чуть-чуть. Не более того, что можно использовать для tabletalk в приличном обществе.




Читать дальше →
Всего голосов 28: ↑28 и ↓0 +28
Просмотры 19K
Комментарии 16

Теория счастья. Головокружительный полёт бутерброда с маслом

Занимательные задачки Математика *Научно-популярное
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



В этой главе мы рассмотрим закон бутерброда и организуем целое исследование с применением метода Монте-Карло, и анализа размерностей. И, наконец, развенчаем популярный миф о том, что именно масло является причиной этого закона подлости.
Читать дальше →
Всего голосов 26: ↑26 и ↓0 +26
Просмотры 12K
Комментарии 11

Теория счастья. Случайности неслучайны?

Занимательные задачки Математика *Научно-популярное
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



В этой главе мы порассуждаем о предопределённости полёта монетки, о топографических картах, о математических катастрофах и о природе случайности. А по пути заглянем в такие разделы математики, как теория мер и теория динамического хаоса.
Читать дальше →
Всего голосов 60: ↑57 и ↓3 +54
Просмотры 44K
Комментарии 127

Учим поросёнка на моноидах верить в себя и летать

Программирование *Haskell *Функциональное программирование *
Tutorial

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



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

Читать дальше →
Всего голосов 41: ↑41 и ↓0 +41
Просмотры 9.9K
Комментарии 25

Стековая машина на моноидах

Программирование *Haskell *Математика *Функциональное программирование *
Tutorial

Не так давно на Хабре появилась отличная и вдохновляющая статья про компиляторы и стековые машины. В ней показывается путь от простой реализации исполнителя байт-кода ко всё более и более эффективным версиям. Мне захотелось показать на примере разработки стековой машины, как это можно сделать Haskell-way.


На примере интерпретации языка для стековой машины мы увидим, как математическая концепция полугрупп и моноидов помогает разрабатывать и расширять архитектуру программы, как можно использовать алгебру моноидов и каким образом можно строить программы в форме набора гомоморфизмов между алгебраическими системами. В качестве рабочих примеров мы сначала построим интерпретатор, неотделимый от кода в виде EDSL, а потом научим его разным штукам: вести запись произвольной отладочной информации, отделять код программы от самой программы, проводить простой статический анализ и вычислять с различными эффектами.


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

Читать дальше →
Всего голосов 49: ↑49 и ↓0 +49
Просмотры 13K
Комментарии 28

Теория счастья. Термодинамика классового неравенства

Занимательные задачки Математика *Научно-популярное
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



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


Читать дальше →
Всего голосов 46: ↑43 и ↓3 +40
Просмотры 30K
Комментарии 110

Теория счастья. Проклятие режиссёра и проклятые принтеры

Занимательные задачки Математика *Научно-популярное
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.





Мы порассуждаем о цейтнотах, дедлайнах и о невовремя ломающихся принтерах.

Читать дальше →
Всего голосов 32: ↑32 и ↓0 +32
Просмотры 12K
Комментарии 6

Теория счастья. Закон зебры и чужой очереди

Занимательные задачки Математика *Научно-популярное
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.





Мы поговорим о фатуме, землетрясениях, очередях и замечательных процессах: пуассоновском потоке, случайном блуждании и немного о цепях Маркова.
Читать дальше →
Всего голосов 45: ↑43 и ↓2 +41
Просмотры 37K
Комментарии 30

Теория счастья. Введение в мерфологию

Занимательные задачки Математика *Научно-популярное
Продолжаю знакомить читателей Хабра с главами из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



Это, одна из первых глав, в которой на примере велосипедиста рассматриваются нужные нам инструменты для измерения несправедливости: кривая Лоренца и индекс Джини, а также упоминаются пресловутый Парето и грозный инспектор.

Читать дальше →
Всего голосов 37: ↑37 и ↓0 +37
Просмотры 31K
Комментарии 44

Теория счастья. Закон арбузной корки и нормальность ненормальности

Занимательные задачки Математика *Научно-популярное
Представляю на суд читателей Хабра неупорядоченные главы из своей книжки «Теория счастья» с подзаголовком «Математические основы законов подлости». Это ещё не изданная научно-популярная книжка, очень неформально рассказывающая о том, как математика позволяет с новой степенью осознанности взглянуть на мир и жизнь людей. Она для тех кому интересна наука и для тех, кому интересна жизнь. А поскольку жизнь наша сложна и, по большому счёту, непредсказуема, упор в книжке делается, в основном, на теорию вероятностей и математическую статистику. Здесь не доказываются теоремы и не даются основы науки, это ни в коем случае не учебник, а то, что называется recreational science. Но именно такой почти игровой подход позволяет развить интуицию, скрасить яркими примерами лекции для студентов и, наконец, объяснить нематематикам и нашим детям, что же такого интересного мы нашли в своей сухой науке.



В этой главе мы начнём с анализа арбузов и их корок, выясним их связь со знаменитым законом Мерфи и убедимся со всей строгостью в том, что о вкусах не спорят.

Читать дальше →
Всего голосов 118: ↑117 и ↓1 +116
Просмотры 69K
Комментарии 250

Безразмерный воздушный шар. Утилитарная магия анализа размерностей

Алгоритмы *Математика *Функциональное программирование *
Tutorial

На написание этой небольшой заметки меня натолкнула недавно опубликованная на Хабре статья Динамика вертикального полёта летательного аппарата легче воздуха. Захотелось написать комментарий, но он быстро перерос во что-то большее и, как кажется, более полезное.

В оригинальной статье приводится пример расчёта динамики воздушного шара или аэростата в атмосфере. При этом учитываются и сопротивление воздуха и градиенты плотности и температуры атмосферы, так что задача сводится к нетривиальному дифференциальному уравнению, которое благополучно решается численно средствами языка Python. В статье всё хорошо: шар взлетел, остановился, где надо, мы получили и предельную высоту и время подъёма. Потребовалось запустить другой шар, скажем, побольше, нагрузить его поосновательнее, или поменять водород на гелий – не проблема – поменяем параметры в программе и снова всё посчитаем. Программка понятная, линейная, работает, что же можно здесь улучшить, если не усложнять модель?

Можно сделать так, чтобы модель и расчёты стали универсально полезными не для какого-то конкретного шара, а для широкого круга задач. Можно обеспечить оптимальную точность вычислений при численном интегрировании дифференциального уравнения. Можно избавиться от необходимости вручную задавать пределы интегрирования и шаг при расчёте в широком диапазоне параметров. Наконец, можно многое рассказать о динамике полёта нашего шара и без численного решения. И для всего этого служит один давний приём, верный и надёжный, когда-то обязательный при любых расчётах на ЭВМ и до их появления, а сейчас факультативный и часто относимый к магии и искусству – приведение уравнений к безразмерному виду и собственным масштабам. Воспользуюсь задачей о воздухоплавании, как примером и покажу, насколько более осмысленным и изящным становится анализ задачи, при использовании этой техники. А потом объясню почему это может быть важным для программистов, и отчего эта статья попала в хаб «Функциональное программирование».
Читать дальше →
Всего голосов 43: ↑43 и ↓0 +43
Просмотры 7.7K
Комментарии 25

От моноидов к алгебрам де Моргана. Строим абстракции на Haskell

Haskell *Математика *Функциональное программирование *
Из песочницы

Что общего у нормального распределения, конечных автоматов, хеш-таблиц, произвольных предикатов, строк, выпуклых оболочек, афинных преобразований, файлов конфигураций и стилей CSS? А что объединяет целые числа, типы в Haskell, произвольные графы, альтернативные функторы, матрицы, регулярные выражения и статистические выборки? Наконец, можно ли как-то связать между собой булеву алгебру, электрические цепи, прямоугольные таблицы, теплоизоляцию труб или зданий и изображения на плоскости? На эти вопросы есть два важных ответа: 1) со всеми этими объектами работают программисты, 2) эти объекты имеют сходную алгебраическую структуру: первые являются моноидами, вторые — полукольцами, третьи — алгебрами де Моргана.

Читать дальше →
Всего голосов 35: ↑34 и ↓1 +33
Просмотры 11K
Комментарии 12

Информация

В рейтинге
256-й
Откуда
Петропавловск-Камчатский, Камчатский край, Россия
Дата рождения
Зарегистрирован
Активность