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

    • Перевод

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


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

    Читать дальше →
    • +29
    • 6,1k
    • 5
  • Теория счастья. Статистика, как научный способ чего-либо не знать

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


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




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

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



        В этой главе мы рассмотрим закон бутерброда и организуем целое исследование с применением метода Монте-Карло, и анализа размерностей. И, наконец, развенчаем популярный миф о том, что именно масло является причиной этого закона подлости.
        Читать дальше →
      • Теория счастья. Случайности неслучайны?

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



          В этой главе мы порассуждаем о предопределённости полёта монетки, о топографических картах, о математических катастрофах и о природе случайности. А по пути заглянем в такие разделы математики, как теория мер и теория динамического хаоса.
          Читать дальше →
        • Учим поросёнка на моноидах верить в себя и летать

          • Tutorial

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



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

          Читать дальше →
        • Стековая машина на моноидах

          • Tutorial

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


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


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

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

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



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


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

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





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

              Читать дальше →
              • +32
              • 11,5k
              • 6
            • Теория счастья. Закон зебры и чужой очереди

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





                Мы поговорим о фатуме, землетрясениях, очередях и замечательных процессах: пуассоновском потоке, случайном блуждании и немного о цепях Маркова.
                Читать дальше →
              • Теория счастья. Введение в мерфологию

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



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

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

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



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

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

                    • Tutorial

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

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

                    Можно сделать так, чтобы модель и расчёты стали универсально полезными не для какого-то конкретного шара, а для широкого круга задач. Можно обеспечить оптимальную точность вычислений при численном интегрировании дифференциального уравнения. Можно избавиться от необходимости вручную задавать пределы интегрирования и шаг при расчёте в широком диапазоне параметров. Наконец, можно многое рассказать о динамике полёта нашего шара и без численного решения. И для всего этого служит один давний приём, верный и надёжный, когда-то обязательный при любых расчётах на ЭВМ и до их появления, а сейчас факультативный и часто относимый к магии и искусству – приведение уравнений к безразмерному виду и собственным масштабам. Воспользуюсь задачей о воздухоплавании, как примером и покажу, насколько более осмысленным и изящным становится анализ задачи, при использовании этой техники. А потом объясню почему это может быть важным для программистов, и отчего эта статья попала в хаб «Функциональное программирование».
                    Читать дальше →
                  • От моноидов к алгебрам де Моргана. Строим абстракции на Haskell

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

                    Читать дальше →