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

Продолжая эту просветительскую работу, я бы хотел остановиться сегодня на — замечательном функциональном языке программирования. Мне уже трижды прислали один и тот же вопрос: с чего начать (продолжить) изучать Haskell?

Наверное, пора дать короткий ответ-совет. Вот общий алгоритм захода в эту тему от меня.

0 этап — Введение. Haskell? Чо за хрень?

Хорошо известный в среде рекрутеров программистов парадокс, часто называемый как « », и он формулируется примерно так:

Если компания выбирает в качестве основного языка программирования некий малораспространенный эзотерический язык программирования, то у такой компании наибольшие шансы получить самых лучших программистов на рынке. Почему? Дело в том, что наняться в такую «странную компанию» захотят в первую очередь те программисты, для которых изучение нового не проблема; те, для которых малоизвестное и труднодоступное не является препятствием; и, наконец, те, у кого достаточно высокая самооценка, чтобы предлагать себя в таких заведомо жестких условиях.

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

Могу привести в качестве отвлеченного примера полностью аналогичного скрытного таргетирования фокус-групп с заданными свойствами, историю из своей недавней юности. Когда я ещё учился, у нас был припод "со странностями", который демонстративно при изложении матанализа никогда не обращал внимание на правую сторону аудитории. То есть в аудитории было два ряда — левый и правый, — и вот он читает лекцию, объясняет что-то, но при этом НИКОГДА не смотрит на правый ряд — всё внимание только на студентов с левого ряда. Также и с ответами на вопросы — правого ряда для него не существовало. Оттуда он ни-че-го не слышит.

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

3. Этап — поиск глубины и чувства нового языка

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

Вот её выходные данные:

The Functional Programming Using Haskell course
(Language: English)
35 hours | 1280×720 | XviD — 1326Kbps
25.00fps | Mp3 — 96Kbps | 20.06 GB

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

4. Завершающий этап — практика

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

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

И в заключение для приверженцев других языков программирования:

Haskell — священный язык программирования, дарованный шаманам Бубенлэнд их верховным божеством Комонада как универсальное средство для общения и духовного очищения, подходящее как божественным сущностям, так и (некоторым) простым смертным, переболевшим тяжёлыми стадиями интеллекта. Из-за своего происхождения язык всегда был функционально чист. В среднем обучение Haskell’у начинается в 10-12 лет. Своевременное начало обучения гарантирует, что вы достигнете третьего уровня Силы уже к 75 годам. Не стоит откладывать на следующую жизнь то, что можно по крайней мере начать в этой.

На Haskell вызов функции не требует заключения аргумента в скобки.

Скобки используются для группировки аргументов:

acos (cos pi)

Функция нескольких аргументов:

max 5 42

Операция применения функции ассоциативна влево:

(max 5) 42

Функция max последовательно применяется к двум аргументам.
Компилятор понимает конструкцию f x y как (f x) y , а не наоборот f (x y) .

Выражение (max 5) это так называемое частичное применение функции. В общем виде его можно сформулировать следующим образом: если у нас имеется функция N переменных и мы смотрим на неё как на функцию N переменных, то мы можем взглянуть на неё с другой стороны и сказать, что это функция одной переменной возвращающая нам функцию N - 1 переменной.

3 + sin 42

3 + (max 5) 42

Синтаксис объявления пользовательской функции

Функция, которая осуществляет суммирование квадратов двух переданных в неё аргументов:

SumSquares x y = x ^ 2 + y ^ 2 rock"n"roll = 42

Функция трех аргументов, которая вычисляет длину трехмерного вектора:

LenVec3 x y z = sqrt (x ^ 2 + y ^ 2 + z ^ 2 )

Let sumSquares x y = x ^ 2 + y ^ 2

Свойство чистоты функции

Функция, которая не принимает ни одного аргумента это константа. Такая функция всё время возвращает одно и то же значение независимо ни от каких обстоятельств.

Prelude > let fortyTwo = 39 + 3 Prelude > fortyTwo 42

На Haskell нельзя определить функцию не принимающую никаких аргументов, которая бы возвращала разные значения при разных вызовах.

Механизм определения функций с помощью частичного применения

На любую функцию мы можем смотреть как на функцию одного аргумента возвращающую некоторую функцию.

Prelude > let max5 x = max 5 x Prelude > max5 4 5 Prelude > max5 42 42

Prelude > let max5" = max 5 Prelude > max5" 4 5 Prelude > max5" 42 42

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

Часто дизайн функций в Haskell настраивается таким образом чтобы частичное применение было удобным;

Prelude > let discount limit proc sum = if sum >= limit then sum * (100 - proc) / 100 else sum Prelude > let standardDiscount = discount 1000 5 Prelude > standardDiscount 2000 1900.0 Prelude > standardDiscount 900 900.0

Параметры limit и proc меняются редко. А вот параметр sum меняется часто. Фактически при каждом вызове этой функции.

Предположим, мы разрабатываем на Haskell интерфейс системы перевода для естественных языков. Он должен содержать функцию translate с параметрами text, languageFrom и languageTo. Для того чтобы было удобно реализовывать следующие функции:

• translateFromSpanishToRussian,
• translateFromEnglishToRussian
• и translateToRussian

Оператор над типами ->

Prelude > : t not not :: Bool -> Bool Prelude > (&& ) False True False Prelude > ((&& ) False ) True False

Тип последнего выражения может быть записан следующим образом:
Bool -> (Bool -> Bool)
Оператор над типами рассматривается как право-ассоциативный. Поэтому Bool -> (Bool -> Bool) можно переписать как Bool -> Bool -> Bool

Prelude > : t (&& ) (&& ) :: Bool -> Bool -> Bool

Вспомним функцию discount, которая возвращала итоговую сумму покупки с возможной скидкой. В качестве параметров ей передавались сумма без скидки sum, процент скидки proc, причем скидка начислялась, если переданная сумма превышает порог limit. Все эти параметры, как и возвращаемое значение, можно хранить в типе Double. Тип функции можно задать в файле исходного кода вместе с ее определением:

discount :: Double -> Double -> Double -> Double discount limit proc sum = if sum >= limit then sum * (100 - proc) / 100 else sum

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

StandardDiscount :: Double -> Double standardDiscount = discount 1000 5

Рассмотрим функцию twoDigits2Int, которая принимает два символа и возвращает число, составленное из этих символов, если оба символа числовые, и 100 в противном случае. (Первый символ рассматривается как количество десятков, второй — единиц.)

Import Data.Char twoDigits2Int :: Char -> Char -> Int twoDigits2Int x y = if isDigit x && isDigit y then digitToInt x * 10 + digitToInt y else 100

GHCi > twoDigits2Int "4" "2" 42

Рекурсия

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

Факториал

Factorial n = if n == 0 then 1 else n * factorial (n - 1 )

Factorial5 n | n >= 0 = helper 1 n | otherwise = error "arg must be >= 0" helper acc 0 = acc helper acc n = helper (acc * n) (n - 1 )

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

Двойной факториал

DoubleFact :: Integer -> Integer doubleFact n = if n <= 0 then 1 else n * doubleFact (n - 2 )

Последовательность чисел Фибоначчи

На Haskell данное определение задаётся следующей функцией:

Fibonacci :: Integer -> Integer fibonacci n | n == 0 = 0 | n == 1 = 1 | n > 1 = fibonacci (n - 1 ) + fibonacci (n - 2 ) | n < 0 = fibonacci (n + 2 ) - fibonacci (n + 1 ) | otherwise = undefined

Реализация функции для вычисления числа Фибоначчи, основанная на прямом рекурсивном определении, крайне неэффективна - количество вызовов функции растет экспоненциально с ростом значения аргумента. GHCi позволяет отслеживать использование памяти и затраты времени на вычисление выражения, для этого следует выполнить команду :set +s :

* Fibonacci > : set + s * Fibonacci > fibonacci 30 832040 (16.78 secs, 409 ,318 ,904 bytes)

С помощью механизма аккумуляторов можно написать более эффективную реализацию, имеющую линейную сложность (по числу рекурсивных вызовов):

Fibonacci" :: Integer -> Integer fibonacci" n = helper n 0 1 helper n a b | n == 0 = a | n > 0 = helper (n - 1 ) b (a + b) | n < 0 = helper (n + 1 ) b (a - b) | otherwise = undefined

Функции высших порядков

Prelude > : t ($ ) ($ ) :: (a -> b) -> a -> b

Это полиморфный тип. Оператор доллар представляет собой функцию двух аргументов. Его левый операнд или первый аргумент (a -> b) это функция. Его правый операнд a это значение произвольного типа. Оператор доллар просто применяет свой первый аргумент(a -> b) ко своему второму аргументуa . Поэтому здесь необходимо чтобы типы были согласованы. Тип второго аргумента оператора доллар должен совпадать с типом параметра функции, которая передается в первом аргументе. Более того результатом выполнения оператора доллар служит результат выполнения функции, которая передана в качестве первого аргумента. Поскольку тип результата это b то результатом выполнения оператора доллар служит тип b.

Следующее применение допустимо только когда a и b это одно и то же.

Prelude > let apply2 f x = f (f x) Prelude > : t apply2 apply2 :: (t -> t) -> t -> t Prelude > apply2 (+ 5 ) 22 32 Prelude > apply2 (++ "AB" ) "CD" "CDABAB"

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

Функция flip из стандартной библиотеки определена следующим образом: flip f y x = f x y.

Prelude > flip (/ ) 4 2 0.5 Prelude > (/ ) 4 2 2.0 Prelude > flip const 5 True True Prelude > : t flip flip :: (a -> b -> c) -> b -> a -> c Prelude > : t flip const flip const :: b -> c -> c

{- В модуле Data.Function определена полезная функция высшего порядка -} on :: (b -> b -> c) -> (a -> b) -> a -> a -> c on op f x y = f x `op` f y {- Она принимает четыре аргумента: 1) бинарный оператор с однотипными аргументами (типа b), 2) функцию f:: a -> b, возвращающую значение типа b, 3,4) и два значения типа a. Функция on применяет f дважды к двум значениям типа a и передает результат в бинарный оператор. Используя on можно, например, записать функцию суммирования квадратов аргументов так: -} sumSquares = (+ ) `on` (^ 2 ) {- Функция multSecond, перемножающая вторые элементы пар, реализована следующим образом -} multSecond = g `on` h g = (* ) h = snd

Анонимные функции

Prelude > (\ x -> 2 * x + 7 ) 10 27 Prelude > let f" = (\ x -> 2 * x + 7 ) Prelude > f" 10 27

Это анонимная функция или лямбда-функция.

Существует синтаксический сахар упрощения записи.

Prelude > let lenVec x y = sqrt $ x^ 2 + y^ 2 Prelude > let lenVec x = \ y -> sqrt $ x^ 2 + y^ 2 Prelude > let lenVec = \ x -> \ y -> sqrt $ x^ 2 + y^ 2 Prelude > lenVec 3 4 5.0 Prelude > let lenVec = \ x y -> sqrt $ x^ 2 + y^ 2 Prelude > lenVec 3 4 5.0

{- Функция on3, имеет семантику, схожую с on, но принимает в качестве первого аргумента трехместную функцию -} on3 :: (b -> b -> b -> c) -> (a -> b) -> a -> a -> a -> c on3 op f x y z = op (f x) (f y) (f z) {- Сумма квадратов трех чисел может быть записана с использованием on3 так -} sum3squares = (\ x y z -> x+ y+ z) `on3` (^ 2 )

Каррированные и некаррированные функции

Prelude > fst (1 ,2 ) 1

* Demo > : t on on :: (b -> b -> c) -> (a -> b) -> a -> a -> c * Demo > : t curry fst `on` (^ 2 ) curry fst `on` (^ 2 ) :: Num b => b -> b -> b

Avg :: (Double ,Double ) -> Double avg p = (fst p + snd p) / 2

Функция curry avg `on` (^2) это функция, которая вычисляет среднее значение квадратов двух переданных в неё значений.

Устройство функции curry:

Prelude > let cur f x y = f (x,y) Prelude > : t cur cur :: ((t1, t2) -> t) -> t1 -> t2 -> t Prelude > : t curry curry :: ((a, b) -> c) -> a -> b -> c

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

Есть и обратная функция uncurry:

Prelude > : t uncurry uncurry :: (a -> Prelude > : t uncurry (flip const) uncurry (flip const) :: (b, c) -> c Prelude > : t snd snd :: (a, b) -> b

В модуле Data.Tuple стандартной библиотеки определена функция swap:: (a,b) -> (b,a), переставляющая местами элементы пары:

GHCi > swap (1 ,"A" ) ("A" ,1 )

Эта функция может быть выражена в виде:

Prelude > let swap = uncurry (flip (,)) Prelude > swap (1 ,"A" ) ("A" ,1 )

Строгие и нестрогие функции

Const42 :: a -> Int const42 = const 42

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

* Demo > const42 True 42 * Demo > const42 123 42 * Demo > const42 (1 + 3 ) 42 * Demo > const42 undefined 42

Функции подобные const42 называются нестрогими функциями. Если в функцию передано в качестве аргумента расходящееся вычисление, а результатом является какое-то значение не расходящееся, то такая функция называется нестрогой. Строгой называется функция такая, что если мы передаем в нее расходящийся аргумент, то значение этой функции обязательно является расходящимся. Функция двух аргументов может быть строгой или нестрогой по второму аргументу в зависимости от значения своего первого аргумента. Анализ строгости необходим для того чтобы делать программу на Haskell очень эффективной.

Типы

Программы на языке Haskell представляют собой выражения, вычисление которых приводит к значениям. Каждое значение имеет тип. Интуитивно тип можно понимать просто как множество допустимых значений выражения. Для того, чтобы узнать тип некоторого выражения, можно использовать команду интерпретатора:type (или:t). Кроме того, можно выполнить команду:set +t, для того, чтобы интерпретатор автоматически печатал тип каждого вычисленного результата.
Основными типами языка Haskell являются:
Типы Integer и Int используется для представления целых чисел, причем значения типа Integer не ограничены по длине.
Типы Float и Double используется для представления вещественных чисел.
Тип Bool содержит два значения: True и False, и предназначен для представления результата логических выражений.
Тип Char используется для представления символов. Имена типов в языке Haskell всегда начинаются с заглавной буквы.
Язык Haskell является сильно типизированным языком программирования. Тем не менее в большинстве случаев программист не обязан объявлять, каким типам принадлежат вводимые им переменные. Интерпретатор сам способен вывести типы употребляемых пользователем переменных.
Однако, если все же для каких-либо целей необходимо объявить, что некоторое значение принадлежит некоторому типу, используется конструкция вида: переменная:: Тип. Если включена опция интерпретатора +t, он печатает значения в таком же формате.
Ниже приведен пример протокола сессии работы с интерпретатором. Предполагается, что текст, следующий за приглашением Prelude>, вводит пользователь, а следующий за этим текст представляет ответ системы.

Prelude>:set +t
Prelude>1
1:: Integer
Prelude>1.2
1.2:: Double
Prelude>’a’
’a’ :: Char
Prelude>True
True:: Bool

Из данного протокола можно сделать вывод, что значения типа Integer, Double и Char задаются по тем же правилам, что и в языке Си.
Развитая система типов и строгая типизация делают программы на языке Haskell безопасными по типам. Гарантируется, что в правильной программе на языке Haskell все типы используются правильно. С практической точки зрения это означает, что программа на языке Haskell при выполнении не может вызвать ошибок доступа к памяти (Access violation). Также гарантируется, что в программе не может произойти использование неинициализированных переменных. Таким образом, многие ошибки в программе отслеживаются на этапе ее компиляции, а не выполнения.

Арифметика

Интерпретатор Hugs можно использовать для вычисления арифметических выражений. При этом можно использовать операторы +, -, *, / (сложение, вычитание, умножение и деление) с обычными правилами приоритета.
Кроме того, можно использовать оператор ^ (возведение в степень). Таким образом, сеанс работы может выглядеть следующим образом:

Prelude>2*2
4:: Integer
Prelude>4*5 + 1
21:: Integer
Prelude>2^3
8:: Integer
Кроме того, можно использовать стандартные математические функции sqrt (квадратный корень), sin, cos, exp и т.д. В отличие от многих других языков программирования, в Haskell при вызове функции не обязательно помещать аргумент в скобки. Таким образом, можно просто писать sqrt 2, а не sqrt(2). Пример:

Prelude>sqrt 2
1.4142135623731:: Double
Prelude>1 + sqrt 2
2.4142135623731:: Double
Prelude>sqrt 2 + 1
2.4142135623731:: Double
Prelude>sqrt (2 + 1)
1.73205080756888:: Double

Из данного примера можно сделать вывод, что вызов функции имеет более высокий приоритет, чем арифметические операции, так что выражение sqrt 2 + 1 интерпретируется как (sqrt 2) + 1, а не sqrt (2 + 1). Для задания точного порядка вычисления следует использовать скобки, как в последнем примере. (В действительности вызов функции имеет более высокий приоритет, чем любой бинарный оператор.)
Также следует заметить, что в отличие от большинства других языков программирования, целочисленные выражения в языке Haskell вычисляются с неограниченным числом разрядов (Попробуйте вычислить выражение 2^5000.) В отличие от языка Си, где максимально возможное значение типа int ограничено разрядностью машины (на современных персональных компьютерах оно равно 231-1 = 2147483647), тип Integer в языке Haskell может хранить целые числа произвольной длины.

Кортежи
Помимо перечисленных выше простых типов, в языке Haskell можно определять значения составных типов. Например, для задания точки наплоскости необходимы два числа, соответствующие ее координатам. В языке Haskell пару можно задать, перечислив компоненты через запятую и взяв их в скобки: (5,3). Компоненты пары не обязательно должны принадлежать одному типу: можно составить пару, первым элементом которой будет строка, а вторым - число и т.д.
В общем случае, если a и b - некоторые произвольные типы языка Haskell, тип пары, в которой первый элемент принадлежит типу a, а второй - типу b, обозначается как (a,b). Например, пара (5,3)имеет тип (Integer, Integer); пара (1, ’a’) принадлежит типу (Integer, Char). Можно привести и более сложный пример: пара((1,’a’),1.2) принадлежит типу ((Integer,Char),Double). Проверьте это с помощью интерпретатора. Следует обратить внимания, что хотя конструкции вида (1,2) и (Integer,Integer) выглядят похоже, в языке Haskell они обозначают совершенно разные сущности. Первая является значением, в то время как последняя - типом. Для работы с парами в языке Haskell существуют стандартные функции fst и snd, возвращающие, соответственно, первый и второй элементы пары (названия этих функций происходят от английских слов «first» (первый) и «second» (второй)). Таким образом, их можно использовать следующим образом

Prelude>fst (5, True)
5:: Integer
Prelude>snd (5, True)
True:: Bool
Кроме пар, аналогичным образом можно определять тройки, четверки и т.д. Их типы записываются аналогичным образом.
Prelude>(1,2,3)
(1,2,3) :: (Integer,Integer,Integer)
Prelude>(1,2,3,4)
(1,2,3,4) :: (Integer,Integer,Integer,Integer)
Такая структура данных называется кортежем. В кортеже может хранится фиксированное количество разнородных данных. Функции fst и snd определены только для пар и не работают для других кортежей. При попытке использовать их, например, для троек, интерпретатор выдает сообщение об ошибке. Элементом кортежа может быть значение любого типа, в том числе и другой кортеж. Для доступа к элементам кортежей, составленных из пар, может использоваться комбинация функций fst и snd. Следующий пример демонстрирует извлечение элемента ’a’ из кортежа
(1, (’a’, 23.12)):
Prelude>fst (snd (1, (’a’, 23.12)))
’a’ :: Integer

Списки
В отличие от кортежей, список может хранить произвольное количество элементов. Чтобы задать список в Haskell, необходимо в квадратных скобках перечислить его элементы через запятую. Все эти элементы должны принадлежать одному и тому же типу. Тип списка с элементами, принадлежащими типу a, обозначается как [a].

Prelude>
::
Prelude>[’1’,’2’,’3’]
[’1’,’2’,’3’] ::
В списке может не быть ни одного элемента. Пустой список обозначается как .
Оператор: (двоеточие) используется для добавления элемента в начало списка. Его левым аргументом должен быть элемент, а правым - список:
Prelude>1:
::
Prelude>’5’:[’1’,’2’,’3’,’4’,’5’]
[’5’,’1’,’2’,’3’,’4’,’5’] ::
Prelude>False:
::
С помощью оператора (:) и пустого списка можно построить любой список:
Prelude>1:(2:(3:))
:: Integer
Оператор (:) ассоциативен вправо, поэтому в приведенном выше выражении можно опустить скобки:
Prelude>1:2:3:
:: Integer
Элементами списка могут быть любые значения - числа, символы, кортежи, другие списки и т.д.
Prelude>[(1,’a’),(2,’b’)]
[(1,’a’),(2,’b’)] :: [(Integer,Char)]
Prelude>[,]
[,] :: []
Для работы со списками в языке Haskell существует большое количество функций. В данной лабораторной работе рассмотрим только некоторые из них.
Функция head возвращает первый элемент списка.
Функция tail возвращает список без первого элемента.
Функция length возвращает длину списка.
Функции head и tail определены для непустых списков. При попытке применить их к пустому списку интерпретатор сообщает об ошибке. Примеры работы с указанными функциями:
Prelude>head
1:: Integer
Prelude>tail
::
Prelude>tail
:: Integer
Prelude>length
3:: Int
Заметьте, что результат функции length принадлежит типу Int, а не типу Integer.
Для соединения (конкатенации) списков в Haskell определен оператор ++.
Prelude>++
:: Integer

Строки
Строковые значения в языке Haskell, как и в Си, задаются в двойных кавычках. Они принадлежат типу String.
Prelude>"hello" "hello" :: String
В действительности строки являются списками символов; таким образом, выражения "hello", [’h’,’e’,’l’,’l’,’o’] и

’h’:’e’:’l’:’l’:’o’: означают одно и то же, а тип String является синонимом для . Все функции для работы со списками можно использовать при работе со строками:
Prelude>head "hello"
’h’ :: Char
Prelude>tail "hello"
"Hello" ::
Prelude>length "hello"
5:: Int
Prelude>"hello" ++ ", world"
"hello, world" ::
Для преобразования числовых значений в строки и наоборот существуют функции read и show:
Prelude>show 1
"1" ::
Prelude>"Formula " ++ show 1
"Formula 1" ::
Prelude>1 + read "12"
13:: Integer
Если функция show не сможет преобразовать строку в число, она сообщит об ошибке.

Функции
До сих пор мы использовали встроенные функции языка Haskell. Теперь пришла пора научиться определять собственные функции. Для этого нам необходимо изучить еще несколько команд интерпретатора (напомним, что эти команды могут быть сокращены до одной буквы):
Команда:load позволяет загрузить в интерпретатор программу на языке Haskell, содержащуюся в указанном файле.
Команда:edit запускает процесс редактирования последнего загруженного файла.
Команда:reload перечитывает последний загруженный файл. Определения пользовательских функций должны находиться в файле, который нужно загрузить в интерпретатор Hugs с помощью команды:load.
Для редактирования загруженной программы можно использовать команду:edit. Она запускает внешний редактор (по умолчанию это Notepad) для редактирования файла. После завершения сеанса редактирования редактор необходимо закрыть; при этом интерпретатор Hugs перечитает содержимое изменившегося файла. Однако файл можно редактировать и непосредственно из оболочки Windows. В этом случае, для того чтобы интерпретатор смог перечитать файл, необходимо явно вызывать команду:reload.
Рассмотрим пример. Создайте в каком-либо каталоге файл lab1.hs. Пусть полный путь к этому файлу - с:\labs\lab1.hs (это только пример, ваши файлы могут называться по-другому). В интерпретаторе Hugs выполните следующие команды:

Prelude>:load "c:\\labs\\lab1.hs"
Если загрузка проведена успешно, приглашение интерпретатора меняется на Main>. Дело в том, что если не указано имя модуля, считается, что оно равно Main.
Main>:edit
Здесь должно открыться окно редактора, в котором можно вводить текст программы. Введите:
x =
Сохраните файл и закройте редактор. Интерпретатор Hugs загрузит файл
с:\labs\lab1.hs и теперь значение переменной x будет определено:
Main>x
::
Обратите внимание, что при записи имени файла в аргументе команды:load символы \ дублируются. Также, как и в языке Си, в Haskell символ \ служит индикатором начало служебного символа (’\n’ и т.п.) Для того, чтобы ввести непосредственно символ \, необходимо, как и в Си, экранировать его еще одним символом \.
Теперь можно перейти к определению функций. Создайте, в соответствие с процессом, описанным выше, какой-либо файл и запишите в него следующий текст:

square:: Integer -> Integer
square x = x * x

Первая строка (square:: Integer -> Integer) объявляет, что мы определяем функцию square, принимающую параметр типа Integer и возвращающую результат типа Integer. Вторая строка (square x = x * x) является непосредственно определением функции. Функция square принимает один аргумент и возвращает его квадрат. Функции в языке Haskell являются значениями «первого класса». Это означает, что они «равноправны» с такими значениями, как целые и вещественные числа, символы, строки, списки и т.д. Функции можно передавать в качестве аргументов в другие функции, возвращать их из функций и т.п. Как и все значения в языке Haskell, функции имеют тип. Тип функции, принимающей значения типа a и возвращающей значения типа b обозначается как a->b.
Загрузите созданный файл в интерпретатор и выполните следующие команды:

Main>:type square
square:: Integer -> Integer
Main>square 2
4:: Integer
Заметим, что в принципе объявление типа функции square не являлось необходимым: интерпретатор сам мог вывести необходимую информацию о типе функции из ее определения. Однако, во-первых, выведенный тип был бы более общим, чем Integer -> Integer, а во-вторых, явное указание типа функции является «хорошим тоном» при программировании на языке Haskell, поскольку объявление типа служит своего рода документацией к функции и помогает выявлять ошибки программирования.
Имена определяемых пользователем функций и переменных должны начинаться с латинской буквы в нижнем регистре. Остальные символы в имени могут быть прописными или строчными латинскими буквами, цифрами или символами _ и ’ (подчеркивание и апостроф). Таким образом, ниже перечислены примеры правильных имен переменных:

var
var1
variableName
variable_name
var’

Условные выражения

В определении функции в языке Haskell можно использовать условные выражения. Запишем функцию signum, вычисляющую знак переданного ей аргумента:

signum:: Integer -> Integer
signum x = if x > 0 then 1
else if x else 0

Условное выражение записывается в виде:
if условие then выражение else выражение. Обратите внимание, что хотя по виду это выражение напоминает соответствующий оператор в языке Си или Паскаль, в условном выражении языка Haskell должны присутствовать и then-часть и else-часть. Выражения в then-части и в else-части условного оператора должны принадлежать одному типу. Условие в определении условного оператора представляет собой любое выражение типа Bool. Примером таких выражений могут служить сравнения. При сравнении можно использовать следующие операторы:
, = - эти операторы имеют такой же смысл, как и в языке Си (меньше, больше, меньше или равно, больше или равно).
== - оператор проверки на равенство.
/= - оператор проверки на неравенство.
Выражения типа Bool можно комбинировать с помощью общепринятых логических операторов && и || (И и ИЛИ), и функции отрицания not.
Примеры допустимых условий:
x >= 0 && x x > 3 && x /= 10
(x > 10 || x Разумеется, можно определять свои функции, возвращающие значения типа Bool, и использовать их в качестве условий. Например, можно определить функцию isPositive, возвращающую True, если ее аргумент неотрицателен и False в противном случае:
isPositive:: Integer -> Bool
isPositive x = if x > 0 then True else False

Теперь функцию signum можно определить следующим образом:
signum:: Integer -> Integer
signum x = if isPositive x then 1
else if x else 0
Отметим, что функцию isPositive можно определить и проще:
isPositive x = x > 0

Информация бралась с: http://sguprog.narod.ru/

Рефакторинге, TDD, багтрекерах, и даже (наконец-то!) о моем любимом Haskell. К сожалению, тема «чем же так хорош этот ваш Haskell» не была в должной мере раскрыта. Такое чувство, что большинство айтишников действительно не понимают плюсов функционального программирования. В этой заметке я постарался развернуто описать, за что лично мне нравится Haskell.

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

1. Красота и декларативность языка

Будучи вещью субъективной и не имеющей строгого определения, «красота языка программирования» является прекрасной темой для холиваров. Потому скажу так — лично мне Haskell кажется очень красивым языком. Некоторые считают, что Haskell сложен, но на самом деле это не так. Одной из причин, по которым мне нравится Haskell, является простое и логичное ядро языка.

Грустный и несчастный Java-программист, который вынужден писать всякие private static final transient volatile List> dramaticallyTerribleList = new ArrayList>; когда где-то совсем рядом есть чудесный Haskell // «о себе» одного хабраюзера

Приведу немного цифр. Описание языка в «Справочнике по языку Haskell» Романа Душкина занимает всего лишь 100 страниц. Остальные 430 страниц занимает описание модулей, которое мне еще ни разу не понадобилось. Объем книги Learn You a Haskell for Great Good! (кстати, скоро будет издан русский перевод) составляет 400 страниц. Лично мне кажется, что при желании ее можно ужать вдвое, ничего при этом не потеряв. Для сравнения, Язык программирования Си Кернигана и Ритчи имеет объем 300 страниц, а Язык программирования C++ Страуструпа — почти 1100 страниц. Вы действительно считаете сложным язык, описание которого даже по самым скромным оценкам имеет примерно тот же объем, что и описание языка Си, которое в свою очередь в 3-4 раза короче описания языка C++ ?

Тут самое время привести немного кода, продемонстрировав, как любят выражаться некоторые программисты, «высокую декларативность» языка. Например, вот так задается функция, возвращающая список делителей некого числа num:

getDivisors num
| num < 1 =
| otherwise = [ x | x <- [ 1 .. num] , num `mod ` x == 0 ]
-- ^ очевидная оптимизация -

Прямо как написать определение! Если обозначить множество делителей числа n, как D(n), и перевести написанное выше на язык математики, то получим D(n) = { x | x ∈ ℤ + , x ≤ n, mod(n, x) = 0 } , где n ∈ ℤ + . А теперь давайте напишем функцию проверки числа на простоту:

isPrime num
| num <= 1 = False
| otherwise = getDivisors num == [ 1 , num]

И снова — как будто пишешь математическую формулу. Теперь получим список всех простых чисел:

allPrimeNumbers = [ 2 ] ++ filter isPrime [ 3 , 5 .. ]

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

Если думаете, что «высокая декларативность» Haskell распространяется только на математические задачи, то вы ошибаетесь. Посмотрите, к примеру, как выглядит код GUI-приложения на Haskell . Или как к базе данных с помощью библиотеки HaskellDB. Фактически, в запросе используется обычная реляционная алгебра. Преимущество перед SQL здесь заключается в том, что корректность запроса проверяется на этапе компиляции программы. Впрочем, если хотите писать запросы на обычном SQL , никто не будет вам препятствовать.

А еще борцы против оператора goto будут рады узнать, что в Haskell его нет.

2. Автоматическое управление памятью

Haskell полностью берет управление памятью на себя. Цитата из WikiBooks :

Функциональные языки освобождают программиста от этой непростой обязанности. Память выделяется неявно, автоматически, а специальный сборщик мусора (garbage collector) возвращает системе неиспользуемые куски памяти. Оптимальные алгоритмы управления памятью сложны, но сегодня уже достаточно хорошо проработаны. Использование этих алгоритмов не сильно увеличивают время работы программы в целом (в сравнении с тем, когда программист сам, по-умному, занимается выделением и освобождением памяти).

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

Кстати, далеко не все из перечисленных проблем по-настоящему решены в таких высокоуровневых языках, как Java, Perl и Python (о проблемах C++ я вообще молчу). Например, в книге Дэвида Бизли приводится пример программы (в моем экземпляре — на стр 174), использующей паттерн «наблюдатель» , в которой сборщик мусора не в состоянии освободить память, если только не воспользоваться weakptr.

Люди, 21-ый век на дворе! Будем еще 90 лет управлять памятью с помощью костылей типа счетчиков ссылок и weakptr, а то и вообще вручную? Или наконец забудем, как страшный сон, и будем двигаться дальше?

3. Чистые функции

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

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

Вот что написано в книге Роберта Мартина Чистый код — создание, анализ и рефакторинг по поводу побочных эффектов:

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

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

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

4. Быстродействие

Повторюсь на счет ленивых вычислений. В Haskell что-то начинает вычисляться только тогда, когда оно действительно понадобится. Вы можете объявить список из 9000 элементов, но если вам понадобятся только один из них (и он не будет зависеть от других элементов списка), то будет вычислено значение только этого одного элемента. И этот принцип работает везде , а не только в списках. В каком-нибудь C++ такое тоже можно сделать, но придется самому написать соответствующий код или подключить какую-нибудь библиотеку, а в Haskell все уже есть «из коробки».

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

Рассмотрим другой пример. Допустим, у нас есть некая функция f(a, b) . Пусть аргументы a и b — результаты вычислений неких других функций, которые по счастливому стечению обстоятельств являются чистыми. В этом случае a и b могут быть вычислены параллельно! Согласитесь, в эпоху многоядерных процессоров это немаловажно. В ООП языках такую оптимизацию провести намного сложнее.

Кроме того, что мы получаем прирост производительности, мы также автоматически распараллеливаем программу и синхронизируем потоки выполнения! А ведь многопоточное программирование с его дэдлоками — это чуть ли не вторая по важности проблема современного программирования после ручного управления памятью. Если вы думаете, что описанное выше — лишь теория, посмотрите список расширений компилятора GHC и проект Data Parallel Haskell . Все уже реализовано!

Дополнение: См также проект Haskell STM . Транзакционная память интересна тем, что позволяет избавиться от блокировок в многопоточных приложениях.

К сожалению, мне не удалось найти ни одного бэнчмарка программ на Haskell, кроме shootout.alioth.debian.org . «К сожалению» — потому что у меня к этому бенчмарку много вопросов . Я отказываюсь верить, что программы на Pascal выполняются в 2 раза медленнее программ на Си. Также вызывают сомнения погрешности в стиле ±100% для скриптовых языков. Тем не менее, если верить этому бенчмарку, Haskell на сегодняшний день является самым быстрым языком функционального программирования. По скорости он сравним с языками Java и C#.

5. Меньше рефакторинга

Давайте откроем оглавление книги Рефакторинг — улучшение существующего кода Фаулера и посмотрим, какие типы рефакторинга бывают. Выделение метода, встраивание метода, перемещение метода, встраивание временной переменной, замена временной переменной вызовом метода, введение пояснительной переменной, расщепление временной переменной, замена ссылки значением, замена значения ссылкой… как считаете, многое ли из перечисленного применимо в Haskell при условии, что в этом языке нет ни ссылок, ни переменных (let и where не считаются)?

Недавно я провел на Хабре два опроса, один — в блоге «Java», второй — в блоге «Haskell». Вопрос был одним и тем же — «Как часто вам приходится производить рефакторинг кода на %PROGRAMMING_LANGUAGE%?». На этих опросах я слил почти всю свою карму (кому-то правда глаза режет?), но оно того стоило:

Я готов признать, что часть опрошенных могла ответить, что не занимается рефакторингом на Haskell, потому что не пишет на нем, но едва ли это сильно исказило картину. Во-первых , в опросах есть кнопочка «воздержаться», а во-вторых , вероятно, среди читателей блога «Java» также далеко не все пишут на Java .

Что интересно, сам синтаксис Haskell подталкивает к написанию кода, состоящего из большого количества простых функций. Это связано с тем, что код на Haskell очень любит разрастаться в ширину экрана, а не в высоту, как в ООП языках. Кроме того, если внутри конструкции if-then-else требуется нечто большее, чем просто вернуть значение, то вместо if-then-else намного удобнее определить новую функцию. В действительности, благодаря сопоставлению с образцами и охране , на Haskell можно писать вообще без использования конструкции if-then-else.

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

6. А нужны ли TDD и UML?

Вспомним, чему нас учит любой учебник по Python или Java. Все является объектом. Используйте объекты, и ваш код станет намного легче сопровождать, расширять и повторно использовать. Уверуйте и покайтесь! Вот, правда, чтобы сопровождать код, извольте составить диаграммы классов, иначе в нем будет невозможно разобраться. И обязательно напишите тесты, покрывающие как можно бо льшую часть кода, иначе любое его изменение сделает вашу программу нерабочей. Прошу вопросы. Да, пожалуйста. Что-что, простите? В каком это смысле «всего лишь надстройка над процедурным программированием »?! Вы что, не слушали? Инкапсуляция, наследование, полиморфизм!

Нет, правда, вы никогда не задумывались, сколько нужно использовать костылей, чтобы ООП работало? Скачайте хотя бы уже упомянутый 253-ий выпуск Radio-T и послушайте, что там говорят о TDD . Фактически, нам предлагают делать в два, а то и в три раза (считая UML) больше работы!

Люди иногда спрашивают, «Что служит аналогом UML для Haskell?». Когда меня впервые спросили об этом 10 лет назад, я подумал, «Ума не приложу. Может быть, нам стоит придумать свой UML». Сейчас я думаю, «Это просто типы!». // Саймон Пейтон Джонс

При этом обычно умалчивается, что далеко не любая задача легко вписывается в рамки ООП. Фактически, ООП неплохо себя зарекомендовало только в игростроении, создании GUI и графических редакторов. Зайдите, к примеру, на CPAN . Возьмите 10 случайных модулей и посмотрите, сколько из них действительно используют ООП (да, в Perl есть ООП), а не просто оформляют модуль в виде класса. Или загляните на Hackage и посчитайте, сколько модулей вполне успешно решают практические задачи вообще без единого намека на ООП.

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

Почему мне кажется, что «костылей» должно быть меньше при использовании Haskell? Ну, во-первых, раз нет классов (не путать с классами типов ) — не нужно рисовать их диаграммы:) Теоретически ничто не мешает рисовать диаграммы классов типов, но лично мне такие еще ни разу не попадались. Во-вторых, как мы уже выяснили, Haskell — «очень декларативный» язык. То есть, обычно мы пишем на нем, что хотим получить, а не как . Таким образом, программа документирует сама себя. И в-третьих, строгая статическая типизация языка позволяет ликвидировать целые классы ошибок еще на этапе компиляции программы. Это не отменяет необходимость временами писать тесты, но существенно сокращает их количество.

Кстати, важными свойствами Haskell являются отсутствие побочных эффектов и кроссплатформенность языка, притом настоящая кроссплатформенность, а не как у C++. Программа, написанная один раз, одинаково хорошо работает под любой ОС и любой архитектурой процессора без необходимости писать какие-то макросы или вроде того. Это приводит к тому, что программисты на Haskell часто (!) вообще не компилируют свои программы.

Знаю, звучит нелепо. Сам не верил, пока не попробовал. Это выглядит примерно так. Создаем новый модуль. Вводим пару новых типов, объявляем первую функцию. Запускаем интерпретатор ghci, проверяем функцию на типичных данных и паре краевых случаев. Если работает — забываем про только что написанную функцию и пишем следующую. Когда весь необходимый функционал реализован, смотрим, какие сущности следует экспортировать из модуля и вносим соответствующие правки. Все, работа выполнена! Без единой компиляции. Если программа заработала в ghci, то ее правильно соберет любой компилятор Haskell, под любую платформу. Вот, что такое настоящая кроссплатформенность.

7. Широкая область применения

Распространенное заблуждение в отношении Haskell заключается в том, что этот язык якобы пригоден для решения только узкого круга хитроумных математических задач. И действительно, как прикажете решать «обычные» задачи, если у нас даже циклов нет? На самом деле, рекурсия ничем не хуже циклов. Думать итерациями или думать рекурсиями — это всего лишь дело привычки. И нет, рекурсия совсем не обязательно должна использовать какую-то память. Вообще-то , именно злоупотребление ООП в конечном счете приводит к мышлению по шаблону, и выводам в стиле «видимо, эта задачка с олимпиады по спортивному программированию , раз я не знаю, как ее решить».

Однако вернемся к области применения. Как я уже отмечал, Haskell прекрасно подходит для написания GUI приложений . Писать на нем для веб я еще не пробовал, но, судя по отзывам, Haskell и тут справляется не хуже PHP:

Я только что закончил написание простенькой FastCGI программы на Haskell. Мне хотелось понять, как работают веб-приложения на Haskell и подходит ли этот язык для создания сайта, посвященного изучению языков. Haskell не только справился с задачей. Оказалось, что писать на нем намного веселее, чем на PHP // jekor.com . На Haskell можно писать даже.

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

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

Дополнение: Книгу «Learn You a Haskell for Great Good!» в русском переводе уже можно заказать в интернет-магазинах . Также на просторах интернета была найдена годная книга Антона Холомьёва «Учебник по Haskell» . Если у вас «нет времени» на изучение Haskell, попробуйте ознакомиться с учебником Макеева Григория , в нем всего лишь 114 страниц.

Функциональное программирование на Haskell

Часть 1. Введение

Серия контента:

Императивное программирование

Наиболее распространены императивные языки , в которых вычисление сводится к последовательному выполнению инструкций. Решение задачи на императивном языке сводится к описанию того, что необходимо проделать, чтобы получить результат. Классические примеры – FORTRAN (1957), ALGOL (1958) и C (1972).

Императивные языки близки к архитектуре фон Неймана . В них весомую часть кода занимают присваивания значений переменным.

Переменные рассматриваются как изменяющиеся во времени ячейки памяти. Текущие значения переменных в программе образуют изменяющееся состояние.

Пример императивного кода – процедура для вычисления факториала на C:

Здесь повторение операции умножения выражено через цикл. В процессе вычисления изменяются значения переменных x и n .

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

Функции и функциональность

В математическом смысле функция f: X → Y – это правило, сопоставляющее элементу x из множества X (области ) элемент y = f x из множества Y (кообласти ).

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

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

Как и в математике, в интересующих нас функциональных языках не существует ячеек, хранящих различные значения. Переменные являются просто именами значений .

Обычно для задания функции в функциональном языке используются уравнения. Например,

n – формальный аргумент функции fac . В правой части после знака = описано, что функция делает со своим аргументом. Базовые функции для умножения и вычитания записаны через инфиксные (указываемые между аргументами) операторы * и - .

Здесь уравнений два. При вычислении функции уравнения просматриваются по порядку. Если n = 0, то будет использовано первое уравнение. Если n ≠ 0, то оно не подойдет, и задействуется второе.

Обратите внимание: аргументы функции перечисляются рядом с ее именем через пробел. Это удобно, потому что применение функции очень часто встречается в функциональных программах (таблица 1).

Таблица 1. Запись применения функции в математике и в Haskell

Уравнения для fac составляют точное определение функции, а не последовательность действий по вычислению, как это было в императивном коде.

Используется рекурсия, т. е. fac определяется через саму себя. Такое определение работает, потому что fac выражается через более простой случай и, в конечном счете (если n ≥ 0), доходит до базового случая n = 0. Вычисление fac 3 по такому определению можно произвести так (на каждом шаге подчеркнуты упрощаемые выражения):

Здесь мы применили f к значению 3 . При этом 3 называется фактическим аргументом .

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

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

Обратите внимание, что для n < 0 наше определение будет вычисляться бесконечно, поэтому наша функция является частичной (если ее областью считать все целые числа).

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

При k ≥ 0 мы имеем выражение, где в знаменателе стоит только что определенный факториал числа k, а в числителе – убывающая факториальная степень (falling factorial power)

Запишем для нее рекурсивное определение:

В первом уравнении r не используется, поэтому можно использовать заменитель _ и писать ffp _ 0 = 1 .

Можно убедиться, что

(проверьте это). Поэтому уравнения факториала можно заменить на

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

Рисунок 2. Черный ящик, вычисляющий убывающую факториальную степень

Возьмем еще один черный ящик (/) с двумя входами x и y и выходом, равным частному x/y:

будет вычислять такая схема:

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

Она соответствует выражению

Определим искомую функцию:

Такая запись называется уравнением с условиями (сравните с математической записью определения). После | и до знака = стоят условия. « otherwise » означает «иначе». Подробно это будет рассмотрено в последующих статьях.

Пример вычисления binc 6 2:

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

Это приводит к важному понятию чистоты.

Чистота

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

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

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

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

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

Каждое выражение в функциональном языке соответствует своему значению; вычисление только модифицирует выражение, но на значение не влияет.

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

Язык без побочных эффектов называется чисто функциональным .

Такие языки, как ML и Scheme, в целом являются функциональными по стилю, однако допускают как присваивания, так и побочные эффекты.

Примеры чисто функциональных языков: Miranda , Haskell и Clean .

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

Ленивость и нестрогость

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

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

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

Например, наша функция binc всегда будет требовать значение k , но значение r требуется, только если k ≥ 0.

В соответствии с этим, говорят о языках со строгой семантикой и языках с нестрогой семантикой. («Нестрогость» и «ленивость» – не одинаковые, но близкие понятия.)

Строгий язык вычисляет аргументы, прежде чем применять функцию. Таким образом, если вычисление выражения e не завершается (зацикливается или останавливается с ошибкой), то применение функции f e также не вычислится.

В нестрогом языке вычисление производится по необходимости. Если f нестрогая, то вычисление f e может завершиться, даже если вычисление e не завершается.

Например,

обозначает список из трех элементов. Вычисление fac (-1) зацикливается. Значит, вычисление списка также зациклится.

Пусть теперь функция length возвращает длину списка. Выражение

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

Примеры нестрогих языков: Miranda и Haskell. Строгие языки – ML и Scheme.

Вопрос строгости достаточно тонок, и его нельзя свести к простому «Что удобнее и эффективнее?» >Передача отложенных вычислений вместо значений в ходе вызова функции связана с определенными затратами. Вместе с тем во многих ситуациях ленивость позволяет экономить на вычислениях или записывать такие выражения, которые бы не вычислились или вычислялись бы бесконечно в энергичном языке.

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

Краткая история

Функциональное программирование черпает идеи из комбинáторной логики и лямбда-исчисления .

Одними из первых языков с функциональным стилем были LISP (1958), APL (1964), ISWIM (1966) и (1977).

К концу 1980-х годов уже имелось много функциональных языков. Среди тех, которые оказали значительное влияние на Haskell:

• (1973) – первый язык с типизацией Хиндли–Милнера.
• SASL , KRC , Miranda (1972–1985) – одни из первых ленивых языков.
• Hope (1980) – один из первых языков с алгебраическими типами данных. Haskell разрабатывался многочисленной группой исследователей с 1987 г. Он назван в честь Хаскелла Карри .

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

Нововведения Haskell – монады и классы типов. Другие сильные стороны, заимствованные из других языков – каррирование, алгебраические типы данных, сопоставление с образцом. (Здесь мы просто приводим набор ключевых слов; все эти понятия скоро будут разъяснены.)

Последнее зафиксированное описание – Haskell 98, однако язык постоянно развивается и усложняется; сейчас планируется выход Haskell" .

Haskell стал самым популярным нестрогим чисто функциональным языком. На Haskell реализовано много сложных проектов:

• Компиляторы и другие средства разработки.
• Распределенная система управления версиями Darcs .
• Оконный менеджер xmonad .
• Сервер Web-приложений HAppS .
• Интерпретатор/компилятор Pugs для языка Perl 6.
• Операционная система House .
• Язык описания аппаратных средств Lava .
• Система обработки натурального языка LOLITA.
• Системы доказательства теорем Equinox / Paradox и Agda .

Основные источники информации по Haskell

У Haskell имеется широкое и дружелюбное сообщество.

Основной источник информации – сервер haskell.org .

• [email protected] – свободное обсуждение.
• [email protected] – более простые темы для новичков.

  Есть очень оживленный IRC-канал #haskell на irc.freenode.net . В нем можно быстро получить любезный ответ практически на любой вопрос.

  Множество тематических блогов собирается на http://planet.haskell.org/

• Хорошим введением в Haskell может быть руководство A Gentle Introduction to Haskell 98 .
• Документацию по обширным библиотекам смотрите по адресу http://haskell.org/ghc/docs/latest/html/libraries/
• Формальный отчет – The Haskell 98 Report .

Редактирование и выполнение кода

Реализации Haskell

Формально, Haskell не имеет какой-то одной «стандартной» реализации.

Для интерактивной работы подойдет легковесный интерпретатор Hugs .

Также есть интересный проект Yhc , компилирующий исходные тексты в байткод, и Helium – учебный вариант Haskell, дружественный к новичкам (например, выдающий более ясные сообщения об ошибках). Однако они еще находятся в процессе разработки.

Де-факто стандартным стал компилятор/интерпретатор GHC. Он является наиболее продвинутым, во всём соответствует стандарту и предлагает ряд экспериментальных расширений. Мы сконцентрируемся на нем.

GHC можно загрузить по адресу http://haskell.org/ghc/ . Если вы используете GNU/Linux, то посмотрите готовые сборки в своем дистрибутиве. Для MacOS X и Windows можно также найти бинарные файлы. (Учтите, что сборка GHC прямо из исходников может быть довольно утомительным занятием.)

Нас в первую очередь будет интересовать интерактивная программа ghci, в которой удобно испытывать учебные примеры.

Итак, после установки GHC вы можете запустить в терминале ghci:

Здесь Prelude – это название загруженного модуля. В Prelude содержатся основные определения, и он всегда задействуется по умолчанию. Изучая или переписывая самостоятельно код Prelude, начинающие могут узнать много нового. (Мы с вами тоже отчасти будем это делать.)

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

Клавишами ← и → можно перемещать курсор по командной строке ghci. и ↓ пролистывают историю команд назад и вперед.

Вместо Prelude> или других имен модулей мы дальше будем писать ghci> (если хотите сделать так же, выполните в ghci команду:set prompt "ghci> ").

Для начала ghci можно использовать как продвинутый калькулятор:

Операторы совпадают с принятыми в других языках (таблица 2).

Таблица 2. Арифметические операторы из Prelude

Для них используется инфиксная запись и соответствующий приоритет. Например, 2*3+4 соответствует (2*3)+4 , а 2^3^4 – 2^(3^4) . Чтобы изменить принятый приоритет, можно расставить скобки.

В ghci имеется специальная переменная it , равная значению последнего успешно вычисленного выражения.

Редактирование исходного кода

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

• Расширение для Emacs : http://www.iro.umontreal.ca/~monnier/elisp/
• Расширение для Vim : http://projects.haskell.org/haskellmode-vim/

Другие средства разработки описаны на странице http://haskell.org/haskellwiki/Libraries_and_tools/Program_development

Для кода Haskell используется расширение файлов.hs .

Если вы запишете код на Haskell в файл foo.hs , то определения загружаются в ghci командой:load foo . Параллельно файл можно редактировать и при необходимости перезагружать определения при помощи:reload .

Текущая директория изменяется командой:cd (например, :cd /home/bob).

Вы можете загрузить прилагающийся к статье исходный код и вычислить выражения:

Эти и другие команды можно сокращать – вместо:load использовать:l , вместо:reload – :r и так далее.

Список команд интерпретатора выводит:help . Для выхода из ghci нужно набрать:quit .

В ходе нашего изложения часто будут встречаться простые примеры, состоящие из одного-двух уравнений. Их можно сразу вводить в ghci при помощи let:

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

Заключение

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