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

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

Это перевод статьи Tony DiPasquale «Efficient JSON in Swift with Functional Concepts».

Предисловие переводчика

Передо мной была поставлена задача: закачать данные в формате JSON с Flickr.com о 100 топ местах, в которых сделаны фотографии на данный момент, в массив моделей:

Тем, кто сталкивался с функциональными языками программирования наверняка знакома такая конструкция:

  fact(0) -> 1
  fact(N) -> N * fact(N - 1)

Это один из классических примеров ФП — вычисление факториала.
Теперь это можно делать и на CoffeeScript с библиотекой f_context, просто оборачивая код в f_context ->, например:

  f_context ->
    fact(0) -> 1
    fact(N) -> N * fact(N - 1)

У наших друзей из Японии есть замечательное событие, называемое F#-ский адвентский календарь. Каждый день, начиная с первого декабря по 31 декабря, один класный чел-доброволец пишет новую статью о F#. Это же просто замечательный подход для празднования Рождества, не правда ли?

Давайте же поддержим эту инициативу и сделаем английскую версию такого календаря. Две блог статьи в день лучше одного, неправда ли? Нам нужен 31 доброволец, готовый подготовить и опубликовать статью о F# в назначенный день.

Если издали видно общую картину, то вблизи можно понять суть. Концепции, которые казались мне далекими и, прямо скажем, странными во время экспериментов с Haskell и Scala, при программировании на Swift становятся ослепительно очевидными решениями для широкого спектра проблем.

Взять вот обработку ошибок. Конкретный пример – деление двух чисел, которое должно вызвать исключение если делитель равен нулю. В Objective C я бы решил проблему так:

NSError *err = nil;
CGFloat result = [NMArithmetic divide:2.5 by:3.0 error:&err];
if (err) {
    NSLog(@"%@", err)
} else {
    [NMArithmetic doSomethingWithResult:result]
}

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

Верни мне значение. Если не получится – то дай знать, чтобы ошибку можно было обработать.

Я передаю параметры, разыменовываю указатели, возвращаю значение в любом случае и в некоторых случаях потом игнорирую. Это неорганизованный код по следующим причинам:

• Я говорю на машинном языке – указатели, разыменование.
• Я должен сам предоставить методу способ, которым он уведомит меня об ошибке.
• Метод возвращает некий результат даже в случае ошибки.

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

Статья будет состоять из 3х частей:
Пальчиковые деревья (часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (часть 3. Применение)

Пальчиковые Деревья как Последовательности

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

Введение

Несколько дней назад я открыл для себя замечательный ЯП Clojure — один из современных диалектов Lisp, особенностью которого является хорошая реализация средств многопоточности, компиляция в байткод jvm, соответственно возможность использования java — библиотек, jit-компиляция и т.д. Про Clojure можно почитать например тут. Но в этой статье речь пойдёт о метапрограммировании. Lisp устроен таким образом, что данные и код в нём — одно и то же. Объявления функций, макросов, вызовы функций, развёртывание макросов — в Lisp это всё просто списки, возможно вложенные друг в друга.

(defn square [foo] (* foo foo))
(defmacro show-it [foo] `(println ~foo))

Такое единство кода и данных предоставляет мощные возможности для метапрограммирования — код который пишет код, который пишет код, который пишет код и т.д. — это самое обычное дело для программирования на Lisp. В compile-time нам полностью доступен весь функционал языка, мы можем вызывать функции, развёртывать макросы, возможно рекурсивно. Например, если мы определим вот такой макрос:

Вышла недавно статья на Хабре о том, как можно самому создать на функциональном языке такие структуры как Очередь (первый зашёл, первый вышел) и Дек (напоминает двусторонний стек — первый зашёл, первый вышел с обоих концов). Посмотрел я на этот код и понял, что он жутко неэффективен — сложность порядка O(n). Быстро сообразить, как создать структуры с O(1) у меня не вышло, поэтому я открыл код библиотечной реализации. Но там была не лёгкая и понятная реализация, а <много кода>. Это было описание пальчиковых деревьев, необходимость и элегантность которых для этой структуры данных хорошо раскрывается текущей статьёй.

Пальчиковые деревья

В этой статье мы рассмотрим пальчиковые деревья. Это функциональные неизменяемые структуры данных общего назначения, разработанные в работе Гинце и Паттерсона. Пальчиковые деревья обеспечивают функциональную структуру данных Последовательность (sequence), которая обеспечивает амортизированной доступ постоянный во времени для добавления как в начало, так и в конец последовательности, а также логарифмическое время для конкатенации и для произвольного доступа. В дополнение к хорошему времени асимптотических исполнения, структура данных оказывается невероятно гибкой: в сочетании с моноидальными тегами на элементах, пальчиковые деревья могут быть использованы для реализации эффективных последовательностей с произвольным доступом, упорядоченных последовательностей, интервальных деревьев и очередей приоритетов.

Статья будет состоять из 3-х частей:

Пальчиковые деревья (Часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (Часть 3. Применение)

Разрабатывая структуру данных

Основа и мотивация пальчиковых деревьев пришла от 2-3 деревьев. 2-3 деревья — это деревья, которые могут иметь две или три ветви в каждой внутренней вершине и которые имеют все свои листья на одном и том же уровне. В то время, как бинарное дерево одинаковой глубины d должны быть 2^d листьев, 2-3 деревья гораздо более гибкие, и могут быть использованы для хранения любого числа элементов (количество не должно быть степенью двойки).
Рассмотрим следующее 2-3 дерево:



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

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

Данная статься продолжает серию публикаций о технологиях, которые мы используем для разработки сервиса проверки доступности веб сайтов HostTracker.
Сегодня речь пойдет о…

MailboxProcessor

6-7 ноября 2014 года в Перми будет проведен конкурс «Открытый регион. Хакатон» по разработке приложений и сервисов на основе открытых данных Пермского края.

На сайте opendata.permkrai.ru опубликовано примерно 1400 статистических показателей по различным областям жизнедеятельности края. Что можно сделать с этими данными? Первая мысль, которая пришла мне в голову, — создать аналог сайта Spurious Correlations (ложные корреляции).

TL; DR:
Исходники: github.com/yakov-bakhmatov/odpr
Приложение: odpr.bakhmatov.ru

Язык Julia не поддерживает такую технику программирования, хорошо зарекомендовавшую себя в языках Haskell, Prolog, Erlang, Scala, Mathematica, как pattern matching. Но разрешает писать макросы, которые позволяют исправить этот фатальный недостаток. Выглядит это примерно так:

julia> immutable X a end

julia> immutable Y a ; b end

julia> @case(Y(X(9),2),  Y(4,3)-> 55, Y(X(k),2)->1+k)
10

Исходный код доступен на github.
Похожую (но гораздо более развитую и готовую для использования) можно взять здесь, но она слишком большая, что бы разбирать ее как пример в статье.

Оригинальная статья — Understanding Monads With JavaScript (Ionuț G. Stan).
Буду признателен за комментарии об ошибках/опечатках/неточностях перевода в личку

От автора

Последние несколько недель я пытаюсь понять монады. Я все еще изучаю Haskell, и, честно говоря, думал, что знаю, что это такое, но когда я захотел написать маленькую библиотечку — так, для тренировки — я обнаружил, что хотя и понимаю, как работают монадические bind (>>=) и return, но не представляю, откуда берется состояние. Так что, вероятно, я вообще не понимаю, как это все работает. В результате, я решил заново изучить монады на примере Javascript. План был тот же, когда я выводил Y Combinator: взял изначальную задачу (здесь это взаимодействие с неизменяемым явно состоянием), и проделал весь путь к решению, шаг за шагом изменяя изначальный код.

Всем привет!

Увидел, что статья о трансдьюсерах на JavaScript стала вполне популярной и хотел отметить, что уже давно доступен генератор парсеров на транзисторах^W трансдьюсерах. По крайней мере, очень на это похоже. У меня есть статья с подробным описанием на английском «Generating Functional Parsers» и, собственно, исходники.

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

В первой части мы остановились на следующей спецификации: Трансдьюсер — это функция принимающая функцию step, и возвращающая новую функцию step.

step⁰ → step¹

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

result⁰, item → result¹

Чтобы получить новый текущий результат в функции step¹, нужно вызвать функцию step⁰, передав в нее старый текущий результат и новое значение, которое мы хотим добавить. Если мы не хотим добавлять значение, то просто возвращем старый результат. Если хотим добавить одно значение, то вызываем step⁰, и то что он вернет возвращаем как новый результат. Если хотим добавить несколько значений, то вызываем step⁰ несколько раз по цепочке, это проще показать на примере реализации трансдьюсера flatten:

function flatten() {
  return function(step) {
    return function(result, item) {
      for (var i = 0; i < item.length; i++) {
        result = step(result, item[i]);
      }
      return result;
    }
  }
}

var flattenT = flatten();

_.reduce([[1, 2], [], [3]], flattenT(append), []); // => [1, 2, 3]

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

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

Итак, сейчас мы можем:

1. Изменять элементы (прим. map)
2. Пропускать элементы (прим. filter)
3. Выдавать для одного элемента несколько новых (прим. flatten)

Рич Хикки, автор языка Clojure, недавно придумал новую концепцию — Трансдьюсеры. Их сразу добавили в Clojure, но сама идея универсальна и может быть воспроизведена в других языках.

Сразу, зачем это нужно:

• трансдьюсеры могут улучшить производительность, т.к. позволят не создавать временные коллекции в цепочках операций map.filter.takeWhile.etc
• могут помочь переиспользовать код
• могут помочь интегрировать библиотеки между собой, например underscore/LoDash могут уметь создавать трансдьюсеры, а FRP библиотеки (RxJS/Bacon.js/Kefir.js) могут уметь их принимать
• могут упростить FRP библиотеки, т.к. можно будет выбросить кучу методов, добавив один метод для поддержки трансдьюсеров

Трансдьюсеры — это попытка переосмыслить операции над коллекциями, такие как map(), filter() и пр., найти в них общую идею, и научиться совмещать вместе несколько операций для дальнейшего переиспользования.

Наверняка многие уже слышали о подходе FRP для организации асинхронного кода. На хабре уже писали об FRP (Реактивное программирование в Haskell, FRP на Bacon.js) и есть хорошие доклады на эту тему (Программировние UI с помощью FRP и Bacon.js, Functional Reactive Programming & ClojureScript, О Bacon.js от Juha Paananen — автора бекона)

Если коротко, FRP это подход похожий на Promise, но с неограниченным количеством возвращаемых значений, и бОльшим количеством методов для комбинирования / модифицирования потоков событий. Другими словами, если Promise позволяют работать со значением, которого у вас еще нет, так, будто оно у вас уже есть, то FRP позволяет работать со значением, меняющимся во времени, так, будто оно не меняется.

Вот что это дает по сравнению с обратными вызовами:

1) Поток событий (Event stream) и значение меняющаяся во времени (Property / Behavior) становятся объектами первого класса. Это значит что их можно передавать в функции и возвращать из функций.

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

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

К примеру можно написать функцию, возвращающую поток перетаскиваний (drag). В качестве параметров она будет принимать 3 потока — начало перетаскивания, движение, конец перетаскивания. Дальше можно передать в эту функцию: либо потоки для соответствующих событий мыши (mousedown, mousemove, mouseup), либо для touch событий (touchstart, touchmove, touchend). Сама же функция не будет ничего знать об источниках событий, а будет работать только с абстрактными потоками. Пример реализации на Bacon.

2) Явный state

Второе большое преимущество FRP это явное управление состоянием. Как известно, state — один из самых главных источников сложности программ, поэтому грамотное управление им позволяет писать более надежные и простые в поддержке программы. Отличный доклад от Рича Хикки о сложности (complexity) «Simple Made Easy».

FRP позволяет писать бОльшую часть кода на «чистых функциях» и управлять потоком данных (dataflow) явно (с помощью потоков событий), а состояния хранить тоже явно в Property.

В языке Wolfram Language небольшой код может делать крайне много. Используя это, мы сделали сервис, который позволит вам получить от этого удовольствие, сегодня мы открываем его — Tweet-a-Program.

Этот сервис соединяет в себе программы на языке Wolfram Language длиной в одно сообщение твиттера и возможность их автоматической отправки в @WolframTaP. Наш Твиттер-бот запустит вашу программу в Wolfram Cloud (Облаке Wolfram), после чего опубликует результат.

(пятница)
Всё началось с того, что я прочитал у Станислава Лема в романе «Мир на Земле» (1985), что в будущем общение на языке будет заменено общением при помощи пиктограмм. Мне показалось это довольно пророческим в связи с возрастающим интересом к различным смайликам и другим видам более крупных картинок и я подумал: а что если программировать при помощи emoji? Поискав в сети я убедился, что мысль такая уже приходила в головы людей и воплотилась в проект https://github.com/wheresaddie/Emojinal
но этот проект меня не впечатлил, во-первых язык не обладает полнотой и вообще подход автора как попытка заменить часть операторов при помощи emoji показалась не сильно интересной.

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

Давайте попробуем реализовать основные типы данных: стек, очередь и дек — на языке F#, по возможности используя чистые функции. Естественно, они будут основаны на списках.

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

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

Стек

Прежде всего начнём со стека. В F# основным типом данных для хранения нескольких однотипных элементов является не массив, а список. Если перед нами стоит задача превратить список в стек, то какие функции нам понадобятся?

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

let push stk el = el :: stk

Довольно простая функция, которая имеет тип 'a list -> 'a -> 'a list, однако не все дальнейшие функции позволят обращаться с собой таким простым способом.

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

Доброе время суток, уважаемая аудитория хабра.

В данной публикации я хотел описать свой опыт перехода с корпоративного Java на Erlang.

Погружения в Erlang в первом приближении

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

После довольно продолжительного времени Java/Python разработки, я решил кардинально изменить сферу деятельность и открыл для себя Erlang.