Пары и списки

В предыдущих частях мы научились задавать новые типы данных, определять функции над ними и доказывать их корректность с помощью распространенных тактик. Настало время определить некоторые структуры данных и функции высших порядков (далее ФВП) над ними.

Внимание: перед тем как читать текст ниже, вы уже должны иметь представление о том, что такое монады. Если это не так, то прежде прочитайте вот этот пост!

Перед нами функция half:


И мы можем применить её несколько раз:

half . half $ 8
=> 2

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

half x = (x `div` 2, "Я только что располовинил  " ++ (show x) ++ "!")

Что ж, отлично. Но что будет если вы теперь захотите применить half несколько раз?

half . half $ 8

Вот то, что мы хотели бы, чтобы происходило:


Спойлер: автоматически так не сделается. Придётся всё расписывать ручками:

finalValue = (val2, log1 ++ log2)
    where (val1, log1) = half 8
          (val2, log2) = half val1

Фу! Это ни капли не похоже на лаконичное

half . half $ 8

А что, если у вас есть ещё функции, имеющие лог? Напрашивается такая схема: для каждой функции, возвращающей вместе со значением лог, мы бы хотели объединять эти логи. Это побочный эффект, а никто не силён в побочных эффектах так, как монады!

Предисловие

Случается, что навязчивая идея так прочно заседает в голове, что ты возвращаешься к ней снова и снова на протяжении многих лет. Пытаешься подойти к проблеме с другой стороны, воспользоваться новыми знаниями, или же просто начать все еще раз с чистого листа — и так до тех пор, пока вопрос не будет исчерпан раз и навсегда. Для меня такой идеей-фикс стали языки программирования. Сам факт того, что одна программа позволяет создавать другие программы, в моих глазах наделял ее непостижимой фрактальной красотой. Написание такой программы самому стало лишь вопросом времени.

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

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

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

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

Пример программирования валидации на CoffeeScript.

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

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

Теперь я пишу на Питоне и с ООП знаком. И паттерны мне теперь намного понятней. Но меня по-прежнему воротит от развесистых схем классов. Многие паттерны прекрасно работают в функциональной парадигме. Опишу несколько примеров.

Язык InterSystems Caché ObjectScript (COS) развивается с каждым годом, в него добавляются новые команды и функционал. К сожалению, в настоящий момент подпрограммы в COS не являются объектами первого класса, то есть подпрограмму (функцию, метод) нельзя передать как параметр в подпрограмму или вернуть из подпрограммы.

Тем не менее, существуют способы смягчить эти ограничения.

Под катом рассмотрим несколько вариантов передачи кода как аргумента подпрограммы.

Вот некое простое значение:


И мы знаем, как к нему можно применить функцию:


Элементарно. Так что теперь усложним задание — пусть наше значение имеет контекст. Пока что вы можете думать о контексте просто как о ящике, куда можно положить значение:


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

data Maybe a = Nothing | Just a

Позже мы увидим разницу в поведении функции для Just a против Nothing. Но сначала поговорим о функторах!

Доказательство упрощением

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

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

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

Большой бедой Узким местом статической типизации являются гетерогенные коллекции и вариадические функции. Поэтому в RPC-библиотеках часто встречается подход, когда входящие данные так и лежат одним ADT-куском, а для методов один такой же плоский тип "[Foo] -> IO Foo", реализации которого копипастят десериализацию/сериализацию, что неудобно и плодит ошибки, в т.ч. рантаймовые.

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

Предисловие

Ни для кого не секрет, что ошибки в программах могут привести печальным последствиям. История знает множество случаев, когда переполнение счетчика или необработанное исключение приводило к большим материальным затратам и человеческим жертвам. Так, например, 4 июня 1996 года европейская ракета-носитель «Ariane 5» буквально развалилась на части на 39-й секунде полета. Анализ инцидента показал, что авария произошла из-за ошибки в программном обеспечении. Ущерб составил около $7 млрд. В феврале 1991 года ракета «Patriot» промахнулась мимо цели из-за ошибки округления, успела пролететь лишние 500 метров. Ущерб: 28 убитых и более сотни раненых. Подобного рода ошибки встречаются и в аппаратном обеспечении. Недавний баг в процессорах Pentium, связанный с неправильным делением чисел с плавающей точкой, вынудил Intel пойти на замену бракованных чипов. Эта ошибка стоила компании $475 млн.

Введение

F* – это новый язык с зависимыми типами, разработанный в недрах Microsoft Research для построения доказательств свойств программ. F* компилируется в байткод .Net и прозрачно интегрируется с другими языками, включая F#, на основе которого он и построен. Вы можете попробовать F* в браузере или скачать альфа-версию компилятора и сопутствующих примеров тут. Формализация F* в системе Coq доступна для всех желающих.

Введение

Прочитав недавно статью про список на Haskell, решил тоже немного рассказать о реализации базовых структур на ФЯП (F#). Статья не несёт практической ценности, поскольку готовых реализаций полно в интернете. Цель статьи — рассказать о том, как можно реализовать неизменяемую очередь на F# и как она работает.
Для начала немного терминологии.
F# — это язык программирования из семейства .NET, который, помимо объектно-ориентированного и императивного подходов, реализует функциональный подход в программировании.
Неизменяемые объекты – это такие объекты, которые будучи созданными один раз, в дальнейшем не могут быть изменены. Например, в C# есть такой тип данных, как string, экземпляры которого являются неизменяемыми. Добавляя символ в строку, вы получаете новую строку и имеете неизменной старую. Подробнее тут.

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

Эта статья раскрывает лишь верхушку айсберга под названием picoLisp. За бортом остались интересные моменты, касающиеся внутренностей базы данных, организация распределенной БД, отладка, функциональный I/O, объектная модель с множественным наследованием, PicoLisp Prolog…

Я всё-таки надеюсь, что отечественные программисты присмотрятся к этому мощному инструменту.

Осторожно, под катом много текста и скобок!

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

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

Самый главный результат, который даёт эта теория — хороший способ решать полиномиальные системы уравнений от нескольких переменных. Даже если вы не знакомы с высшей алгеброй или с Haskell, я советую вам прочитать эту статью, так как эти самые методы решения объяснены на уровне, доступном школьнику, а вся теория нужна только для обоснования. Можно спокойно пропустить всё, что связано с высшей алгеброй, и просто научиться решать системы уравнений.

Если вас заинтересовало, прошу под кат.

Примечание переводчика: Оригинал здесь. Все примеры в оригинале написаны на JavaScript, но я решил перевести их на Scheme. Уверен, менее понятно не стало, но зато видна вся красота этого языка.
UPD: добавил ко всем примерам справа еще и оригинальные примеры на JavaScript.


Если закрыть глаза на практическую сторону компьютеров — размер, вес, цену, тепло и т.п., что же на самом деле должен уметь язык программирования? Давайте исследуем этот вопрос.

Для понимания примеров в этой статье необходимы базовые понятия о функциях в LISP (Scheme). Если вы понимаете, что напечатает этот код, можно смело читать дальше:

(define x 10) (define (f y) (display x) (newline) (display y) (newline) ) (define g f) (f 1) (g 2)

var x = 10; var f = function(y) { console.log(x); console.log(y); } var g = f; f(1); g(2);

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

Рассмотрим вариант реализации связных списков через замыкания.

Для обозначения списков будем использовать нотацию, похожую на Haskell: x:xs, где x — начало списка (head), xs — продолжение (tail).



В качестве языка реализации я выбрал JavaScript.

Конструируем список

Вот уже несколько лет функциональное программирование набирает популярность. Это, конечно, не значит, что люди забрасывают свои старые языки и ООП и массово переходят на Haskell, Lisp или Erlang. Нет. Функциональная парадигма проникает в наш код через лазейки мультипарадигменных языков, а вышеупомянутые языки чаще служат флагами в этом наступлении, чем используются непосредственно.

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

Привет,
в этом посте я расскажу рецепт добавления функциональности в Перл.

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

f(0) = 1
f(n) = n * f(n-1)

Функциональные языки программирования позволяют определять такие функции достаточно просто, в Erlang это делается следующим образом:

factorial(0) ->
    1;
factorial(N) ->
    N * factorial(N-1).

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

#!/usr/bin/perl -I./lib
use strict;
use bigint;
 
use Recurrent;
 
recurrent fac => {
    arg(0) => lambda { my($n) = @_; return 1 },
    arg(n) => lambda { my($n) = @_; return $n * fac($n-1) },
};
 
print fac(100);

Из примера видно, что у нас появились новые функции recurrent, arg, n и lambda. На самом деле, практическая польза есть только у recurrent, все остальные нужны лишь для получения более «красивого» кода.

Давайте напишем модуль Recurrent.pm