• Решаем задачи Яндекс.Интервью в функциональном стиле

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


    Зарегистрировавшись в системе, моё внимание сразу привлекла возможность решать задачи на Haskell. Дело в том, что я хоть и увлекаюсь программированием на этом языке, но не продвинулся дальше реализации задач из различных курсов образовательных on-line платформ. Решив, что их решение может оказаться интересным вызовом и повысит мой уровень, как разработчика, я приступил к их решению.


    Кому интересно, что в итоге из этого вышло, добро пожаловать под кат.

    Читать дальше →
    • +30
    • 7.9k
    • 7
  • Arend – язык с зависимыми типами, основанный на HoTT (часть 1)

      В данном посте мы поговорим о только что выпущенном JetBrains языке с зависимыми типами Arend (язык назван в честь Аренда Гейтинга). Этот язык разрабатывался JetBrains Research на протяжении последних нескольких лет. И хотя репозитории уже год назад были выложены в открытый доступ на github.com/JetBrains, полноценный релиз Arend случился лишь в июле этого года.

      Мы попробуем рассказать, чем Arend отличается от существующих систем формализованной математики, основанных на зависимых типах, и о том, какая функциональность уже сейчас доступна его пользователям. Мы предполагаем, что читатель настоящей статьи в целом знаком с зависимыми типами и слышал хотя бы про один из языков, основанных на зависимых типах: Agda, Idris, Coq или Lean. При этом мы не рассчитываем, что читатель владеет зависимыми типами на продвинутом уровне.

      Для простоты и конкретности наш рассказ об Arend и гомотопических типах будет сопровождаться реализацией на Arend простейшего алгоритма сортировки списков — даже на этом примере можно почувствовать отличие Arend от Agda и Coq. На Хабре уже есть ряд статей, посвященных зависимым типам. Скажем, про реализацию сортировки списков методом QuickSort на Agda есть вот такая статья. Мы будем реализовывать более простой алгоритм сортировки вставками. При этом основное внимание уделим конструкциям языка Arend, а не самому алгоритму сортировки.
      Читать дальше →
    • Деревянные игрушки, часть пятая — 1991

        В 1991 году всё больше игр выходило с поддержкой VGA, хотя за EGA ещё держались и не так много игр именно требовали VGA. Для меня же в 1991 начинался период отлучения от РС. Регулярному доступу приходил на смену эпизодический, гораздо больше времени начал проводить за MSX в школе. На РС же, к которым был доступ, был паскаль, а не игрушки. Это тоже было интересно, но всё же проходило по другому ведомству.



        Содержание:
        Деревянные игрушки — эпилог, что осталось прибитым к потолку
        Деревянные игрушки, часть последняя — 1997
        Деревянные игрушки, часть десятая — 1996
        Деревянные игрушки — неписи
        Деревянные игрушки, часть девятая — 1995
        Деревянные игрушки, часть восьмая — 1994
        Деревянные игрушки, часть седьмая — 1993
        Деревянные игрушки, часть шестая — 1992
        Деревянные игрушки, часть пятая — 1991
        Деревянные игрушки, часть четвертая — 1990
        Деревянные игрушки, часть третья — 1989
        Деревянные игрушки, часть вторая — 1986-1988
        Деревянные игрушки, часть первая — 1982-1985
        Читать дальше →
      • Привет, люди с аутистическими нарушениями



          В смысле, привет, Хабр! Если вы можете сказать про себя слово «интроверт» (как и я) то вас, скорее всего, можно заносить в эту категорию. Другое дело, что категория, мягко говоря, размыта. И в неё от души навалено сразу несколько синдромов.

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

          Плюс отклонений аутистического спектра — это когда вся вот эта мощность, направленная на выявление тысяч закономерностей в социальной жизни, была переброшена на что-то другое. Например, на анализ сложных систем в математике или разработке. Или на теоретическую физику. Или на музыку. Или на искусство. Гипотеза, разумеется, пока не так чтобы очень доказуемая, и не факт, что эта «мощность» была вообще. Но, тем не менее, этой моделью легко пользоваться, рассуждая про лёгких аутистов.

          А теперь давайте разбираться в деталях.
          Читать дальше →
        • 22 компьютерных музея: путеводитель для путешествующих по Европе инженеров



            Мы составили список интересных коллекций, посвященных истории IT, доступных для посещения в разных частях континентальной Европы. Думаем, остановка в любом из них, может здорово скрасить отпуск или командировку.

            ***

            Первые индустриальные музеи появились еще во второй половине XIX века. Основу их коллекций составляли механизмы, приборы и материалы, ранее выставлявшиеся на всемирных выставках, которые с 1851 года вызывали повышенный интерес во всем мире. Тогда же начали формироваться и собрания, ставшие основой научно-технических музеев ХХ века. А специальный метод повествования, характерный для такого рода экспозиций, сложился уже в 1960-70-е годы, когда даже самые старые ЭВМ в музеи еще никто списывать не собирался.
            Читать дальше →
          • Почему для открытия меню Windows читает один файл сто тысяч раз?

            • Translation

            «Проводник тратит 700 мс на то, чтобы открыть контекстное меню панели задач. 75% этого времени он выполняет 114 801 операцию считывания из одного файла, средний объём считываемых данных 68 байт.

            Мне стоит написать пост об этом, или достаточно саркастичного твита?»


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

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

            Этот пост написан как проверка скоростного блогинга. От момента нахождения проблемы и саркастичного твита о ней до публикации поста прошло примерно 90 минут.
            Читать дальше →
          • Как развернуть односвязный список на собеседовании

              Привет, Хабр.


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


              image

              Читать дальше →
            • Подборка полезных слайдов от Джулии Эванс

              • Translation
              Перевели новую порцию слайдов. Права доступа в Unix, файловые дескрипторы, потоки, магия proc. И на закуску пара советов о том, как общаться, когда ты не согласен. А вдруг пригодятся =)



              Читать дальше →
            • Педалируем Vim

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

                Задача


                Сделать педаль, представляющую собой USB HID-устройство, при нажатии и удержании которой печатается i, а при отпускании Esc.

                Решение


                Заказать китайскую педаль PCsensor USB footswitch и запрограммировать её соответствующим образом.

                PCsensor USB footswitch
                Читать дальше →
              • Самые короткие научные статьи

                  Математика


                  В 2005 году ученые Джон Конуэй (John Conway) и Александр Сойфер (Alexander Soifer) решили написать «самую короткую научную статью по математике в мире». Непосредственно тело статьи состоит из двух слов (и двух иллюстраций — в них содержится ответ на вопрос, поставленный в заглавии).

                  image

                  Читать дальше →
                • Анализ сишного Hello World

                  • Translation
                  Hello World — одна из первых программ, которые мы пишем на любом языке программирования.

                  Для C hello world выглядит просто и коротко:

                  #include <stdio.h>
                  
                  void main() {
                    printf("Hello World!\n");
                  }

                  Поскольку программа такая короткая, должно быть элементарно объяснить, что происходит «под капотом».
                  Читать дальше →
                • Восемь малоизвестных опций Bash

                  • Translation
                  • Tutorial
                  Некоторые опции Bash хорошо известны и часто используются. Например, многие в начале скрипта пишут

                  set -o xtrace

                  для отладки,

                  set -o errexit

                  для выхода по ошибке или

                  set -o errunset

                  для выхода, если вызванная переменная не установлена.

                  Но есть много других опций. Иногда они слишком путано описаны в манах, поэтому я собрал здесь некоторые из наиболее полезных, с объяснением.
                  Читать дальше →
                • Интервью с Виталием Брагилевским: «Мир, в котором все будут программировать на Haskell — это вряд ли хороший мир»



                    Виталий Брагилевский (@_bravit) пока что еще преподает в ЮФУ курсы по Haskell и теории алгоритмов. Также, дает выездные курсы в других городах, является редактором и переводчиком множества книг о Haskell и функциональном программировании, состоит в комитетах Haskell 2020 и компилятора GHC и активно выступает на конференциях. К примеру, он прочитает краткий курс компиляторостроения на Haskell на функциональной конференции FPURE в Казани.

                    Ввиду такого огромного количества активностей, итоговая запись вышла почти на целый час (ссылка на аудио)! Ниже читайте ее текстовую расшифровку, где Виталий рассказывает о плюсах карьеры преподавателя, множестве книг о Haskell и не только и, конечно же, о самом Haskell, и нужно ли быть гением, чтобы писать на этом языке.
                    Читать дальше →
                    • +54
                    • 16.9k
                    • 4
                  • Неожиданная полнота по Тьюрингу повсюду

                    • Translation
                    Каталог программных конструкций, языков и API, которые неожиданно являются полными по Тьюрингу; последствия этого для безопасности и надёжности. Приложение: сколько компьютеров в вашем компьютере?

                    Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp. — Десятое правило Гринспена

                    Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.

                    Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин»1). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.
                    Читать дальше →
                  • Лабиринты: классификация, генерирование, поиск решений

                    • Translation

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

                    Классификация лабиринтов


                    Лабиринты в целом (а значит, и алгоритмы для их создания) можно разбить по семи различным классификациям: размерности, гиперразмерности, топологии, тесселяции, маршрутизации, текстуре и приоритету. Лабиринт может использовать по одному элементу из каждого класса в любом сочетании.
                    Читать дальше →
                  • Как я пишу конспекты по математике на LaTeX в Vim

                    • Translation
                    • Tutorial
                    Некоторое время назад на Quora я отвечал на вопрос: как успевать записывать за лектором конспект по математике на LaTeX. Там я объяснил свой рабочий процесс по конспектированию в LaTeX с помощью Vim и Inkscape (для рисунков). Но с тех пор многое изменилось, так что я хочу опубликовать несколько постов в блоге с описанием нового процесса. Это первая из статей.

                    Я начал использовать LaTeX для конспектирования во втором семестре курса математики, и с тех пор написал более 1700 страниц. Вот несколько примеров, как выглядит конспект:


                    Читать дальше →
                  • Каково оно учить JavaScript в 2016

                    • Translation


                    — Эй, я получил новый веб-проект, но, если честно, я не занимался веб-кодингом в течение нескольких лет, и я слышал, все немного поменялось. Ты же самый современный веб-разработчик, правда?

                    — Это теперь называется Front-End инженер, но да, я — именно он. Я работаю с вебом в 2016. Визуализации, музыкальные плееры, летающие дроны, которые играют в футбол, все что угодно. Я только что вернулся из JsConf и ReactConf, так что я знаю новейшие технологии для создания веб-приложений.

                    — Круто. Мне нужно создать страницу, которая отображает последние действия со стороны пользователей, так что мне просто нужно получить данные от REST и отобразить их в какой-то фильтруемой таблице, ну и обновлять её, если что-то изменится на сервере. Я думал, может быть, использовать JQuery для извлечения и отображения данных?

                    — О, Мой Бог! Нет! Никто больше не использует JQuery. Ты должен попробовать React: это — 2016!
                    Читать дальше →
                  • Антипаттерны Vim

                    • Translation
                    • Tutorial
                    Когда вы находитесь в состоянии потока, Vim серьёзно ускоряет редактирование, будь то написание кода, поэзии или прозы. Но поскольку кривая обучения слишком крута для текстового редактора, то очень легко сохранить вредные привычки с тех времён, когда вы только осваивали редактор. Vim настолько ускоряет работу, что искоренить эти привычки особенно трудно, ведь их можно даже не заметить. Но это того стоит. Перечислю некоторые из наиболее распространённых антипаттернов.
                    Читать дальше →
                  • Сколькими способами можно записать факториал на Scheme?

                      Злые языки утверждают, что функциональные языки программирования — «языки для написания факториалов». Чаще всего так определяют язык Haskell, мы же начнем с того функционального языка, который сильно повлиял и на Haskell, и на подмножество средств для функционального программирования многих других языков — язык Scheme. По-крайней мере, map и for-each, filter и reduce, а так же apply и eval пришли в наши любимые языки программирования если не именно из Scheme, то в том числе и оттуда.


                      Рассмотрим некоторые возможные способы записи вычисления факториала. Заодно получится своеобразная ода языку программирования Scheme. Думаю, этот замечательный язык того вполне заслуживает.


                      У меня получилось 10 вариантов записи определений функций, которые можно свести к 3 основным способам вычисления: традиционному линейно-рекурсивному вычислительному процессу, итерации, генерации последовательности чисел с последующей сверткой умножением. Предлагаю рассмотреть эти варианты подробнее. Попутно мы рассмотрим: оптимизацию хвостовой рекурсии, функции высших порядков и метапрограммирование, отложенные вычисления, бесконечные списки, мемоизацию, способ создать статическую переменную в Scheme и гигиенические макросы.

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