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


Только лишь одна загвоздка, хотя и достаточно парадоксальная. В самой квантовой механике нет ничего парадоксального в парадоксе ЭПР! Ни граммульки!

Так почему же его так пристально изучают?

И да, при чём тут эфир?!

Да-да, вам не привиделось и вы не ослышались — именно высокого рода. Род (kind) — это термин теории типов, означающий по сути тип типа [данных].

Но вначале немного лирики.

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

Эта статься — мои пять копеек в этот хайп. Мы рассмотрим валидацию данных в Хаскеле.

Валидация типом

Ранее было рассмотрен пример методики валидации при помощи валидации типом:

type EmailContactInfo  = String
type PostalContactInfo = String

data ContactInfo = EmailOnly EmailContactInfo | 
                   PostOnly PostalContactInfo | 
                   EmailAndPost (EmailContactInfo, PostalContactInfo)

data Person = Person 
  { pName :: String,
  , pContactInfo :: ContactInfo,
  }

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

Валидация данными высокого рода

В этой статье мы посмотрим иной метод валидации — при помощи данных высокого рода.

Пусть у нас есть тип данных:

data Person = Person
  { pName :: String
  , pAge  :: Int
  }

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

Тут можно и поэтому данный метод широко используется среди авторов библиотек на Хаскеле.

НовыйТип (newtype) — это специализированное объявление типа данных. Такое, что содержит лишь один конструктор и поле.

newtype Foo a = Bar a
newtype Id = MkId Word

Типичные вопросы новичка

В чём же отличие от data типа данных?

data Foo a = Bar a
data Id = MkId Word

Главная специфика newtype состоит в том, что он состоит из тех же частей, что и его единственное поле. Более точно — отличаясь от оригинала на уровне типа, но имеет такое же представление в памяти, да и вычисляется строго (не лениво).
Если вкратце — newtype более эффективны благодаря своему представлению.

Да это ничего не значит для меня… Буду использовать data
Не, ну в конце-концов, всегда можно включить расширение -funpack-strict-fields :) для строгих(не ленивых) полей или указать прямо

data Id = MkId !Word

Всё же сила newtype не ограничивается лишь эффективностью вычислений. Они значительно сильнее!

Так уж случилось, что игры я писал лишь для себя, и профессионально этим никогда не занимался.
А вот опыт писать DSL (Domain Specific language) для уменьшения рутины написания совершенно разного кода хоть какой-то есть.
Именно этим и хочется поделится: как упорядочить необъятное.



Наш хороший хабр-юзер GlukKazan пишет много статей о том какие есть замечательные продукты для создания различных досочных игр. Такие как Zillions of Games и Axiom Development Kit.
Однако эти программы не универсальны. И всегда хочется улучшить их. Но данные продукты не свободны, поэтому приходится писать программный продукт заново.
GlukKazan работает над открытым проектом Dagaz, о чём делится отличными статьями (например тут: Dagaz: Новое начало).

Итак, предположим, мы хотим создать универсальный игровой движок для настольных игр, и его основой мы хотим видеть скриптовый язык, который помогает растолковать движку правила игры.
Каким мы хотим его видеть?
1) Язык должен быть универсальным, насколько можно, дабы описать почти любые правила игры.
2) Тем не менее, язык должен быть как можно проще, минимум конструкций.
3) Описание правил должны быть легки для чтения игроделу и для написания своих игр
4) Для большинства случаев игры можно писать, дополняя/изменяя уже написанные
5) Коммуникация (АПИ) со скриптом должна быть насколько простой, насколько это возможно. Так, что бы можно легко писать ботов и ИИ.
На первый взгляд кажется, что потраченные усилия вообще никому не нужны будут, поскольку рутину не уменьшить, проще писать игры сразу готовыми.
Но это не так.
Всё куда проще!

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

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

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

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

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

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

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

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

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

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



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

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

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

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

В этой статье мы попытаемся рассмотреть всё разнообразие Алгебраических Типов Данных.

Надо сказать, задача это достаточно неподъёмная, и понять человеку, если он ранее с Алгебраическими Типами не имел дело — не очень просто.
АТД были впервые использованы в языке Hope, но основную популярность они приобрели благодаря языкам ML, такими как Standart ML, OCaml, F#, и языку Haskell.
Ныне АТД в той или иной мере поддерживаются в значительно большем количестве языков: Scala, Rust, Nemerle, Racket,…
АТД — это универсальный тип данных. С помощью него можно представить большинство типов данных.
АТД называются алгебраическими, потому что их можно представить как некую алгебраическую композицию типов его составляющих. Это знание даёт своё преимущество: понимая свойства алгебраической композиции, можно посчитать какой тип необходим для построения тех или иных данных.
Будем рассматривать типы на основе языка Haskell, однако подобного с лёгкими изменениями можно добиться в других языках с поддержкой АТД.

Это достаточно вольный перевод статьи. Дело в том, что несмотря на конструкции в одну строчку, материал сложен для понимания.
Беря во внимание то, что в комментариях Прелюдия или как полюбить Haskell просили, чтобы код был понятный, я внёс достаточно ремарок, и, надеюсь, код будет понятен и тем, кто далёк от Хаскеля.

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

Странные петли — это запутанные категории, когда двигаясь вверх или вниз в иерархической системе, находишь то же самое, откуда начал движение.
Зачастую такие петли содержат само-референтные ссылки.
Например, подобной странной петлёй обладает рекурсивные акронимы: «PHP — PHP: Hypertext Preprocessor».
Ну, и на сегодняшний день наиболее загадочным словом, содержащим странные петли, является понятие «я».

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

Немецкий математик Лёб мигрировал в 39-м году ХХ-го столетия в Великобританию. Лёб, в частности, развивал математическую логику и миру прежде всего известен Теоремой Лёба. Это теорема развивала труды Гёделя о неполноте математики. Теорема Лёба о взаимосвязи между доказуемостью утверждения и самим утверждением, она гласит, что

во всякой теории, включающей аксиоматику Пеано (аксиоматика о натуральных числах), для любого высказывания P доказуемость высказывания «если доказуемо P, тогда P истинно» возможна только в случае доказуемости самого высказывания P.

Всю эту сложность высказывания можно записать символически:


Можно ли такую функцию написать на Хаскеле?! Можно! И всего в одну строчку!

Так уж завелось на хабре, что на каждую холиварную статью «Pro» всегда найдётся статья «Contra».
Я тоже решил не оставлять в одиночестве пост «Что не так с ООП и ФП».



Прямо противоречить написанному смысла не имеет, там ведь описан «вкус», а, как известно, на вкус и цвет… каждый любит свой ЯП.
Нет никакой проблемы с ООП и ФП. Чистота функций — это всего лишь инструмент, равно как и «всё является объектом».
Критика права лишь в одном — в борьбе за миллиметры хорошо видны яркие прорехи, а в любых вырожденных методах недостатки ярко проявляются.
Другое дело, что любые невырожденные методы так же имеют недостатки, только их больше, зато они не так легко заметны.
Любители С++ гнобят полное ООП, Javа гнобит Си++ за неполное ООП, Haskell гнобит другие ФП за грязные функции, остальные ФП гнобят Haskell за излишне чистые функции.
Всё имеет свою оборотную сторону медали.
Тогда почему досталось всё объектам и функциям, а не массивам и указателям?!

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

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

Линзы

Ваш билет к элегантному коду — это библиотека линз (lens).

Предисловие

Когда я начал изучать Хаскель, я был почти сразу поражён. Для начала, нырнув с головой в актуальные рабочие проекты, открыл, что большинство настоящих библиотек используют языковые расширения, присутствующие только в GHC (Glasgow Haskell Compiler). Это меня покоробило слегка, прежде всего потому, кто захочет использовать язык настолько немощный, что будет необходимо использовать расширения, присутствующие лишь у одного поставщика. Ведь так?
Хорошо, я решился снова это осилить и узнать всё об этих расширениях, и я вывел три горячих топика для общества Хаскеля, которые решали похожие проблемы: Обобщённые Алгебраические Типы Данных, Семьи Типов и Функциональные Зависимости. Пытаясь найти ресурсы, которые обучают о них, я смог найти только статьи, описывающие, что это такое, и как их использовать. Но никто, на самом деле, не объяснял зачем они нужны!.. Поэтому я решил написать эту статью, используя дружественный пример, пытаясь объяснить зачем всё-таки нужны Семьи Типов.



Вы когда-нибудь слышали про Покемонов? Это замечательные существа, которые населяют Мир Покемонов. Вы можете считать, что они как животные с экстраординарными способностями. Все покемоны владеют стихией, и все их возможности зависят от этой стихии. Например, покемон Огненной стихии может дышать огнём, в то время как покемон Водной стихии может брызгать струями воды.
Покемоны принадлежат людям, и их специальные способности могут быть использованы во благо для продуктивной деятельности, но некоторые люди всего лишь используют своих покемонов для борьбы с другими покемонами других людей. Эти люди называют себя Тренерами Покемонов. Это может сначала звучать как жестокое обращение с животными, но это очень даже весело и все, похоже, рады, включая покемонов. Имейте в виду, что в мире покемонов, кажется, всё в порядке, даже если 10-летние покидают дом, дабы рисковать своими жизнями ради того, чтобы стать самыми лучшими Тренерами Покемонов, как будто никто и никогда таковыми не становился.

Мы собираемся использовать Хаскель для того, что бы представить ограниченную (и даже несколько упрощённую, да простят меня фанаты) часть мира покемонов.

Хотелось бы остановиться и посмотреть на развитие языков программирования с точки зрения развития пользовательских типов данных (ПТД).
Сразу хочу оговориться, под пользователями понимаются программисты, как люди, пишущие код на этих языках. Ну, и те, кто этот код сопровождает или просто читает.

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

Пользователи желают иметь примерно такие типы данных

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