Метка «haskell»

Квантовый поиск при помощи алгоритма ГровераСегодня вслед за первыми квантовыми алгоритмами, которые мы уже рассмотрели (см. алгоритм Дойча и алгоритм Дойча-Йожи — если кто-то ещё не читал эти статьи, то предлагаю предварительно с ними ознакомиться, поскольку без этого изложение может показаться несколько туманным), предлагаю изучить алгоритм Гровера для неструктурируемого квантового поиска. Этот алгоритм был разработан американским математиком Ловом Гровером в 1996 году (уже намного позже того, как модель квантовых вычислений стала в моде). Этот алгоритм использует свойство квантовой интерференции для того, чтобы решать крайне насущную задачу по поиску значения некоторого параметра, на котором заданная функция выдаёт определённый результат.

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

Эта статья является продолжением в цикле статей по модели квантовых вычислений, поэтому если начать читать её без ознакомления с предыдущими статьями цикла, что-то может показаться непонятным. Так что читателя, который впервые набрёл на эти мои заметки, я отправляю к первым статьям: 1, 2, 3, 4.

Итак, если кто-то заинтересовался, то как обычно добро пожаловать под кат.

Читать полностью »

Поиск закономерностей в последовательности «случайных» событийВ июне 2014 года, как это обычно бывает по чётным месяцам, был проведён конкурс по функциональному программированию, который проводится под эгидой Фонда Поддержки Функционального Программирования ФП(ФП). Традиционно я хотел бы подвести итоги конкурса и рассказать о решении конкурсной задачи при помощи языка программирования Haskell. Так что всех заинтересованных я приглашаю ознакомиться с этой небольшой заметкой.

В качестве задачи на конкурс была предложена задача по поиску закономерностей в ряду проявлений казалось бы «случайного» события. Но как и всё в этом мире чисто случайными являются, видимо, результаты измерения квантовых состояний, так что во всём другом можно найти какие-то закономерности. Так и здесь. Был дан список дат, когда произошло некоторое событие, и предлагалось дать ответы на два вопроса:

  1. Каков минимальный период, в котором частотная вероятность проявления события хотя бы в один день периода равна или более 50 %?
  2. Необходимо было дать прогноз проявления события с даты конкурса до конца текущего года.

Только два конкурсанта смогли предоставить решения. Впрочем, оба они были неправильными, поскольку правильным ответом на первый вопрос является число 24. А вот вторая задача будет обработана в конце года, когда будет явлена статистика по проявлениям событий. Так что приз за первый вопрос остался неразыгранным, а приз за второй вопрос будет предоставлен тому конкурсанту, прогноз которого наберёт больше очков, в следующем году.

Ну а здесь остаётся рассмотреть решение этих задач на языке программирования Haskell.

Читать полностью »

Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life)

life_anim
Читать полностью »

Задача о выкидывании негра за бортТак уж вышло, что на февральский конкурс по функциональному программированию в 2014 году была предложена очень смешная и совершенно неполиткорректная задача, которая, однако же, привлекла небывалое для последних времён количество конкурсантов. В итоге на конкурс было подано 10 решений, а участвовало 9 конкурсантов (то есть один из участников решил задачу на двух языках программирования). Из представленных языков программирования же в порядке убывания были следующие: Haskell (4 решения), Erlang (2 решения), Clojure, JavaScript, Prolog и Scala (по 1 решению). Что, собственно, очень радует.

  • Постановка задачи: здесь.
  • Отчёт о проведении конкурса: здесь.

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

Читать полностью »

Альманах 2013 вышел в светВсем заинтересованным лицам и сочувствующим субъектам спешу сообщить, что я, наконец-то, составил третий сборник отчётов по ежемесячным конкурсам по функциональному программированию, проводимых в 2013 году каждые два месяца под эгидой ФП(ФП). Сборник содержит шесть моих отчётов, несколько отчётов участников, а также исходные коды на языке Haskell по каждому конкурсу. Всем, кто интересуется функциональным программированием и собирает литературу по нему, данная книга будет интересна (в том числе и потому, что это уже третий экземпляр в серии). Кроме того, как периодическое издание Альманах зарегистрирован и получил ISSN, что тоже немаловажно.

Альманах выпущен только в виде электронного издания и распространяется на безвозмездной основе (но всякий всегда может перечислить благодарность в пользу ФП(ФП), и я буду этому очень рад). Скачать электронную книгу можно здесь. Те, кто ещё не может отказаться от бумажных вариантов книг, всегда смогут воспользоваться технологией печати по требованию (print on demand) и заказать себе экземпляр в малой типографии (о возникновении возможности для этого я сообщу дополнительно в официальном блоге ФП(ФП): haskell98.blogspot.ru).

Далее в этой заметке будет приведено расширенное содержание Альманаха, в том числе и для того, чтобы здесь был набор ссылок на отдельные заметки, которые я публиковал на Хаброхабре в течение 2013 года.Читать полностью »

Приветствую всех Хабражителей!

Представляю вашему вниманию книгу о языке Haskell. Впрочем, «книга» — это громко сказано: 160-страничное руководство для обыкновенных программистов, которые хотят наконец понять, как же можно жить без оператора присваивания и что такое монада.

Озвучу причины, с чего это вдруг мне, самому заурядному C++-разработчику, взбрело в голову написать про Haskell.
Читать полностью »

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

Это статья попытка показать, что сила функциональных языков и в первую очередь Хаскеля — это в том числе и силе функторов и монад.
Зачем нужны все эти фунткоры и монады?
Читать полностью »

Добрый день!
Мы в издательстве «Питер» подумали, что в России не хватает книг по Haskell и решили обратиться к сообществу с вопросом, стоит ли делать перевод одной из таких книг и, если да, — то какой именно?
image
На наш взгляд, на рынке присутствует только одна достойная книга — русский перевод Learn You a Haskell for Great Good (в русском названии «Изучай Haskell во имя добра!»)

Из кандидатов на русское издание мы рассматриваем следующие книги:
Читать полностью »

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

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

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

Читать полностью »

Представлен первый в этом году выпуск русскоязычного журнала Pragmatic Perl. Какими интересными событиями в мире Perl запомнился прошлый год и что важного произошло в русскоязычном Perl-сообществе? Как ведётся разработка на Perl под Raspberry PI и сравнение функционального программирования на Haskell и Perl. Это и многое другое доступно на страницах свежего одиннадцатого номера.

Читать полностью »