Как стать автором
Поиск
Написать публикацию
Обновить
1.6

Haskell *

Чистый функциональный язык программирования

Сначала показывать
Порог рейтинга
Уровень сложности

Легкая прогулка от функтора через монаду к стрелке

Время на прочтение8 мин
Количество просмотров28K

Давайте совершим прогулку по цепочке Pointed, Functor, Applicative Functor, Monad, Category, Arrow, в процессе которой я попытаюсь показать что все это придумано не для того что бы взорвать мозг, а для решения вполне реальных проблем, притом существующих не только в haskell. Большая часть кода написана на C#, но думаю и без его знания можно будет понять что к чему.
Читать дальше →

Динамические мат. функции в C++

Время на прочтение5 мин
Количество просмотров16K
Здравствуйте, Хабраюзеры.
Недавно я прочитал здесь статью об анонимных функциях в С++, и тут же у меня в голове возникла мысль: нужно срочно написать класс для работы с функциями, которые нам знакомы из математики. А именно, принимающими вещественный аргумент и возвращающими вещественное же значение. Нужно дать возможность обращаться с такими объектами максимально просто, не задумываясь о реализации.
И вот, как я это реализовал.
Читать дальше →

Монада ContT в картинках (Haskell)

Время на прочтение5 мин
Количество просмотров4.7K
На хабре уже были статьи про продолжения и монаду ContT. Я решил поделиться своим пониманием этого вопроса и снабдить его соответствующими иллюстрациями. В отличие от приведенной выше статьи, мне бы хотелось больше внимания уделить внутреннему устройству монады ContT и разобраться, как же она работает.
Читать дальше →

Верифицированный QuickSort на Agda

Время на прочтение11 мин
Количество просмотров10K
Доброго времени суток, уважаемый хабраюзер!

Прочитав несколько книг по типизированному лямбда исчислению, а именно по зависимым типам, увидел интересную закономерность: везде первым примером приводится определение типа «отсортированный список». Все бы хорошо, но дальше этого определения ничего не было. Вот я и придумал восполнить этот пробел и реализовать функцию, принимающую список, и возвращающую другой список и два доказательства. Одно доказывает, что результат — это перестановка входа, а другое доказывает, что результат — отсортированный список.
Поехали!

Задача конкурса ICFPC-2012: робот и λ

Время на прочтение4 мин
Количество просмотров3.2K
Всего несколько часов назад начался конкурс ICFPC-2012, который продлится все выходные. Я решил перевести задачу для этого конкурса в надежде, что кто-то из заинтересовавшихся людей успеет принять участие.

Задача вполне понятная, так что дерзайте.

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

Шахты с лямбдами обнаружены в Шотландии! Ваша задача — прочитав карту шахты суметь составить программу для робота.


Ссылка на красивый симулятор: icfp.stbuehler.de/icfp2012

Подробная спецификация

Меню для Yi

Время на прочтение5 мин
Количество просмотров1.6K
Недавно я всё же решил сесть и разобраться с Yi — текстовым редактором наподобие Vim и Emacs, но написанном на Haskell. В комплекте даже есть Vim и Emacs симуляция.
Из-за отстутствия опыта с Vim или Emacs, мне подошла лишь Cua-симуляция. Хоткеев там мало, но зато они привычные для меня. Поэтому я решил начать с него и написать настройку для себя.
В обычных графических редакторах мне кажется удобным способ использования меню. Нажимаешь alt, открывается меню, где у каждого элемента подчёркнута буква, нажав которую, мы этот элемент выберем.
Таким образом не надо запоминать все команды сразу, а можно начинать пользоваться, подглядывая в меню, постепенно доводя до автоматизма.
Нечто подобное я решил прикрутить и в Yi.

image
Заглядываем под капот Yi

Структуры данных в haskell и как они влияют на garbage collector

Время на прочтение3 мин
Количество просмотров2.6K
Для решения одной из задачек из стэнфордского курса по криптографии понадобилось создать таблицу соответствия Word64 -> Integer и несколько миллионов раз проверить в ней наличие элемента и добавить новый. Решение очевидно: хэш-таблицы. hoogle предложил Data.HashTable, программа была написана, успешно отработала и можно было бы обо всем забыть, но захотелось потренироваться в профайлинге и оптимизации.

Запуск с +RTS -sstderr вызвал легкий шок: почти половина времени уходила на сборку мусора.
Читать дальше →

Реактивное программирование

Время на прочтение7 мин
Количество просмотров35K
Как известно, функциональный подход к программированию имеет свою специфику: в нём мы преобразовываем данные, а не меняем их. Но это накладывает свои ограничения, например при создании программ активно взаимодействующих с пользователем. В императивном языке намного проще реализовать такое поведение, ведь мы можем реагировать на какие либо события «в реальном времени», в то время как в чистых функциональных языках нам придётся откладывать общение с системой до самого конца. Однако относительно недавно стала развиваться новая парадигма программирования, решающая эту проблему. И имя ей — Functional Reactive Programming (FRP). В этой статье я попытаюсь показать основы FRP на примере написания змейки на Haskell с использованием библиотеки reactive-banana.
Читать дальше →

Что не так с циклами for?

Время на прочтение6 мин
Количество просмотров7.5K
Возможное появление замыканий в Java стало горячей темой для обсуждений. Готовится предложение по добавлению замыканий в грядущую версию языка, однако же предлагаемый синтаксис вкупе с усложнением языка подвергаются критике со стороны многих Java программистов.

Сегодня Эллиотт Расти Харольд (Elliotte Rusty Harold) опубликовал свои сомнения по поводу возможных изменений. Один из главных заданных им вопросов: “Почему вы ненавидите цикл for”(«Why Hate the for Loop?»)?
Читать дальше →

Решение задачи о миссионерах и каннибалах на языке Haskell

Время на прочтение4 мин
Количество просмотров6.5K
Изучая язык Haskell, я в очередной раз встал перед проблемой поиска какой-нибудь задачи для отработки новых навыков. После непродолжительных раздумий решено было реализовать написанный давным-давно на python алгоритм поиска в ширину для задачи о переправах миссионеров и каннибалов. Решение показалось мне довольно лаконичным, посему я решил поделиться им с людьми (а заодно и выслушать критику).
image
Интересующихся прошу проследовать под кат.
Читать дальше →

Haskell — Эстетика

Время на прочтение32 мин
Количество просмотров5.1K
Я придумываю особенную игру в жанре космического симулятора. Согласно одной из ключевых концепций, в игре будет встроенный язык программирования, с помощью которого можно разрабатывать и улучшать алгоритмы взаимодействия игровых элементов. Дизайн такого языка — дело непростое, учитывая его «натуральность», а не «текстовость». То есть, конструкции языка выражены в виде разных графических объектов. Рисуя эскизы его конструкций, я неожиданно для себя отвлекся и вместо языка для игры стал придумывать язык для визуализации Haskell-кода. Получалось так интересно, что я не мог оставить эскизы просто бумажными рисунками. В январе 2012 года я начал писать сервер визуализации, и вот что получилось…



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

В поисках жирного (The Quest For FAT)

Время на прочтение17 мин
Количество просмотров4.2K
При разработке некоего программно-аппаратного комплекса потребовалось создать клиентское устройство, которое для прочих устройств должно выглядеть как обычная USB-флешка, или если более формально, то USB Mass Storage Device. Необычность устройства в том, что оно должно имитировать для внешнего мира файловую систему FAT с файлами достаточно большого размера (2GB и и более), при том, что сами файлы на устройстве, конечно, отсутствуют и находятся в сети. Да и вообще это не файлы, а некие аудио-потоки.

Задача, на первый взгляд, простая: на каждый запрос на чтение блока (команду SCSI) отдаем содержимое этого блока. Блок может либо принадлежать какому-нибудь из «файлов», либо содержать служебную информацию FAT.
Читать дальше →

Эндофункторы категории Hask и их моноидальная структура

Время на прочтение7 мин
Количество просмотров9.7K

Введение


В предыдущей статье я рассказал о понятиях категории и функтора в контексте категории Hask, состоящей из типов данных и функций языка Haskell. Теперь я хочу рассказать о другом примере категории, построенном из уже известных нам понятий, а так же о весьма важном понятии моноида.

Обозначения


В прошлый раз я хотел обозначить морфизм/функцию буквой f, но она была занята для обозначения функтора/переменной типа f – никакой проблемы с точки зрения языка Haskell в этом нет, но при невнимательном прочтении это может вызвать путаницу, и я использовал для морфизма букву g. Пустяк, но всё же, я считаю, что полезно визуально разделять сущности, имеющие разную природу. Обычные типы я буду называть их обычными именами, а вот переменные типов я буду называть маленькими греческими буквами, причём простые () – буквами из начала алфавита, а параметрические (∗ → ∗) – буквами из конца алфавита (θ не из конца, но она смотрится лучше, чем χ, которая слишком похожа на X). Итак, в терминологии категории Hask:
  • Объекты: α, β, γ, δ ∷ ∗
  • Функторы: θ, φ, ψ, ω ∷ ∗ → ∗
  • Морфизмы: f, g, h ∷ α → β
Ввиду того, что GHC довольно давно поддерживает unicode, эти обозначения ничего не меняют в отношении синтаксиса и носят чисто косметический характер.

Ещё одно замечание, касательно терминологии: как вы уже заметили, то, что я в прошлый раз называл словом “кайнд” (kind), я теперь называю словом “сорт” – это считается общепринятым переводом.

Категория с объектом Hask


Давайте рассмотрим категорию, в которой будет только один объект – сама категория Hask. Что же будет морфизмами в такой категории? Это должны быть какие-то отображения HaskHask, и мы уже знаем такой тип отображений – это эндофункторы категории Hask, то есть типы сорта ∗ → ∗, воплощения класса Functor. Теперь нужно продумать как устроены единичный морфизм и композиция в этой категории, так чтобы они удовлетворяли аксиомам.
Читать дальше →

Ближайшие события

Категория Hask

Время на прочтение7 мин
Количество просмотров16K

Вступление


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

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

Эта статья во многом повторяет (в том числе заимствует иллюстрации) раздел из английской Haskell Wikibook, но тем не менее не является непосредственным переводом.

Что такое категория?



Примеры


Для наглядности рассмотрим сначала пару картинок изображающих простые категории. На них есть красные кружочки и стрелки:

Красные кружочки изображают «объекты», а стрелки – «морфизмы».

Я хочу привести один наглядный пример из реальной жизни, который даст какое-то интуитивное представление о природе объектов и морфизмов:

Можно считать города «объектами», а перемещения между городами – «морфизмами». Например, можно представить себе карту авиарейсов (как-то не нашёл я удачную картинку) или карту железных дорог – они будут похожи на картинки выше, только сложнее. Следует обратить внимание на два момента, которые кажутся в реальности само собой разумеющимися, но для дальнейшего имеют важное значение:
  • Бывает, что из одного города в другой никак не попасть поездом или самолётом – между этими городами нет морфизмов.
  • Если мы перемещаемся в пределах одного и того же города, то это тоже морфизм – мы как бы путешествуем из города в него же.
  • Если из Санкт-Петербурга есть поезд до Москвы, а из Москвы есть авиарейс в Амстердам, то мы можем купить билет на поезд и билет на самолёт, “скомбинировать” их и таким образом попасть из Санкт-Петербурга в Амстердам – то есть можно на нашей карте нарисовать стрелку от Санкт-Петербурга до Амстердама изображающую этот скомбинированный морфизм.
Надеюсь, с этим примером всё понятно. А теперь немного формализма для чёткости.
Читать дальше →

Введение в Template Haskell. Часть 3. Прочие аспекты TH

Время на прочтение6 мин
Количество просмотров2.6K
Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика. Предыдущие части:


Материализация


Материализация (reification) — это средство Template Haskell, позволяющее программисту получить информацию из таблицы символов компилятора. Монадическая функция reify ∷ Name → Q Info возвращает информацию о данном имени: если это глобальный идентификатор (функция, константа, конструктор) – вы получите его тип, если это тип или класс – вы получите его структуру. Определение типа Info можно найти в модуле Language.Haskell.TH.Syntax.
Материализация может быть использована для того, чтобы получить структуру типа, но таким образом нельзя получить тело функции. Если вам нужно материализовать тело функции, то определение функции нужно процитировать и дальше можно будет работать с этим определением с помощью другого шаблона. Например так:
$(optimize [d| fib = … |])

или так
fib = $(optimize [| … |])

На самом деле, в оригинальной статье больше ничего не говорится про материализацию. Не знаю, насколько это содержательная тема – необходимый минимум знаний о ней ограничивается функцией reify и типом Info, но есть некоторые тонкости, связанные например с тем, что можно получить информацию не о любом имени. Если эта тема интересна, я могу собрать какую-нибудь информацию и написать об этом отдельную заметку (или вклеить сюда).

Облегчённое цитирование имён


Чтобы получить имя (∷ Name), соответствующее интересующему идентификатору, можно использовать функцию mkName, но это не безопасное решение, потому что mkName возвращает не квалифицированное имя, которое может интерпретироваться по-разному в зависимости от контекста. А вот код VarE id ← [| foo |] безопасен в этом смысле, так как цитирование квалифицирует имена (получится что-то типа My.Own.Module.foo), но этот код слишком многословный и требует монадический контекст для использования. К счастью, Template Haskell, имеет другую простую форму цитирования имён: 'foo (одинарная кавычка перед foo) имеет тип Name и содержит квалифицированное имя, соответствующее идентификатору foo, так что код let id = 'foo эквивалентен по смыслу коду VarE id ← [| foo |]. Обратите внимание, что эта конструкция имеет простой тип Name (а не Q Exp или Q Name), так что она может быть использована там, где не возможно использование монад, например:
f ∷ Exp → Exp
f (App (Var m) e) |  m == 'map  =  …

Эта новая форма тем не менее является цитированием и подчиняется тем же правилам, что и цитирующие скобки [| … |]. Например, она не может быть использована внутри этих скобок (так нельзя: [| 'foo |]), но и вклеивание к ней не может быть применено (так тоже нельзя: $( 'foo )), потому что для вклейки нужен тип Q …. Более важно то, что эта форма определяется статически, возвращая полностью квалифицированное имя, с однозначной интерпретацией.
Haskell’евские пространства имён немного всё усложняют. Цитата [| P |] означает конструктор данных P, в то время как [t| P |] означает конструктор типа P. Поэтому для “облегчённого цитирования” необходим такой же способ разделения этих сущностей. Для контекста типов используется просто две одинарные кавычки:
  • 'Foo означает “конструктор данных Foo в контексте выражения”
  • 'foo означает “имя foo в контексте выражения”
  • ''Foo означает “конструктор типа Foo в контексте типов”
  • ''foo означает “переменная типа foo в контексте типов”
Облегчённая форма цитирования используется в примере генерации воплощений класса Show, который разбирается в конце.
Читать дальше →

Как питонистам читать Haskell

Время на прочтение8 мин
Количество просмотров7.7K
Сталкивались ли вы с тем, что иногда надо быстро понять, что делает кусок кода на неком незнакомом языке? Если язык похож на то, к чему вы привыкли, как правило, можно догадаться о назначении большей части кода — даже если вы не очень хорошо знакомы со всеми фичами языка.
С Haskell все по-другому, так как его синтаксис выглядит совсем иначе, нежели синтаксис традиционных языков. Но, на самом деле, разница не так велика — нужно просто взглянуть под правильным углом. Здесь приводится быстрое, по большей части некорректное, и, надеюсь, полезное руководство по интерпретации питонистами (автор использует слово «Pythonista» — прим. переводчика) кода на Haskell. К концу вы будете способны понять следующий кусок (часть кода опущена за троеточиями):
runCommand env cmd state = ...
retrieveState = ...
saveState state = ...

main :: IO ()
main = do
    args <- getArgs
    let (actions, nonOptions, errors) = getOpt Permute options args
    opts <- foldl (>>=) (return startOptions) actions
    when (null nonOptions) $ printHelp >> throw NotEnoughArguments
    command <- fromError $ parseCommand nonOptions
    currentTerm <- getCurrentTerm
    let env = Environment
            { envCurrentTerm = currentTerm
            , envOpts = opts
            }
    saveState =<< runCommand env command =<< retrieveState

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

Введение в Template Haskell. Часть 2. Инструменты цитирования кода

Время на прочтение6 мин
Количество просмотров3.2K
Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика. Другие части:


Монада цитирования


Поскольку шаблоны должны возвращать свои значения обёрнутыми в монаду Q, для этого имеется набор вспомогательных функций, которые “поднимают” (оборачивают в Q) конструкторы типов Exp, Lit, Pat: lamE (соотв. LamE), varE, appE, varP и т.д. В их сигнатурах так же используются переобозначенные поднятые типы: ExpQ = Q Exp, LitQ = Q Lit, PatQ = Q Pat… (все их можно найти в модуле Language.Haskell.TH.Lib). Используя эти функции, можно значительно сократить код, реже используя do-синтаксис.
В TH также есть функция lift, которая поднимает до Q Exp значение любого типа из класса Lift.
В некоторых редких случаях, вам может понадобиться не генерация уникального имени, а использование точного имени идентификатора из внешнего (по отношению к шаблону) кода. Для этих целей есть (чистая) функция mkName ∷ String → Name. Есть также вспомогательная функция dyn s = return (VarE (mkName s)), которая возвращает значение Exp представляющее переменную с данным именем (dyn ∷ String → Q Exp).

Цитирующие скобки


Построение значений Exp, представляющих абстрактное синтаксическое дерево — трудоёмкая и скучная работа. Но к счастью, в Template Haskell есть цитирующие скобки, которые преобразуют конкретный Haskell-код в структуру, представляющую его.
Читать дальше →

Введение в Template Haskell. Часть 1. Необходимый минимум

Время на прочтение4 мин
Количество просмотров9.3K

Данный текст является переводом документации Template Haskell, написанной Булатом Зиганшиным. Перевод всего текста разбит на несколько логических частей для облегчения восприятия. Далее курсив в тексте — примечания переводчика.



Template Haskell (далее TH) — это расширение языка Haskell предназначенное для мета-программирования. Оно даёт возможность алгоритмического построения программы на стадии компиляции. Это позволяет разработчику использовать различные техники программирования, не доступные в самом Haskell’е, такие как, макро-подобные расширения, направляемые пользователем оптимизации (например inlining), обобщённое программирование (polytypic programming), генерация вспомогательных структур данных и функций из имеющихся. К примеру, код
yell file line = fail ($(printf "Error in file %s line %d") file line)

может быть преобразован с помощью TH в
yell file line = fail ((\x1 x2 -> "Error in file "++x1++" line "++show x2) file line)

Другой пример, код

data T = A Int String | B Integer | C
$(deriveShow ''T)

может быть преобразован в

data T = A Int String | B Integer | C
instance Show T
    show (A x1 x2) = "A "++show x1++" "++show x2
    show (B x1)    = "B "++show x1
    show C         = "C"

В TH код на Haskell’е генерируется обычными Haskell’евскими функциями (которые я буду для ясности называть шаблонами). Минимум того, что вам необходимо знать, чтобы использовать TH — это следующие темы:
  1. Как Haskell-код представляется в шаблонах (TH-функциях)
  2. Как монада цитирования используется для унификации имён
  3. Как сгенерированный TH-код вставляется в программу
Читать дальше →

Ленивые вычисления

Время на прочтение8 мин
Количество просмотров17K
Одной из «визитных карточек» Хаскеля являются отложенные, или ленивые, вычисления. Эта особенность языка не только открывает множество возможностей, но и создаёт некоторые проблемы, особенно со скоростью работы программ.

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

Динамическое программирование и ленивые вычисления

Время на прочтение4 мин
Количество просмотров5.2K
Динамическое программирование является довольно важным подходом в решении многих сложных задач, основанным на разбиении задачи на подзадачи и решении этих подзадач единожды, даже если они являются частью нескольких других подзадач. Перед людьми, которые только начинают овладевать функциональным программированием часто возникает вопрос: «как избежать повторного решения подзадач, если не использовать переменные для сохранения результатов?». В этом вопросе одна особенность функционального программирования — отсутствие переменных — мешает кешировать результаты решения подзадач, но другая особенность поможет — ленивые вычисления.
Читать дальше →

Вклад авторов