• Tutorial

Привет Habr! Сегодня я достал свои старые конспекты по курсу «Haskell как первый язык программирования» Сергея Михайловича Абрамова и попробую максимально доходчиво и с примерами рассказать об этом замечательном языке тем, кто с ним еще не знаком. Рассказ ориентирован на неподготовленного читателя. Так что, даже если вы впервые услышали слово Haskell…

Базовые типы Haskell

Базовые типы языка Haskell - это:
Числа
Логические величины
Символы
Списки
Упорядоченные множества (tuples)
Функции

Числа
Целые:
Integer (-∞,∞)
Int (-2^31, 2^31-1)
В прелюдии (стандартной библиотеке) определенно много полезных функций для целых чисел, в том числе, и преобразование в число с плавающей точкой (fromInt и fromInteger)

Числа с плавающей точкой:
Float (7 знаков после запятой)
Double (16 знаков после запятой)

Логические величины
Bool (True | False)
Операции конъюнкции, дизъюнкции и отрицания (&&, ||, not)

Символы
Char (’a’)
И функции Char в Int и Int в Char (ord, chr)

Списки
Списки могут быть разные:
- список целых чисел
- список символов (строка)
[] - массив
- это список функций
и т. д.

Несколько стандартных операций в примерах:
Main> head
1
Main> tail
Main> length
2
Main> reverse
Main> 0:
Main> - строка приглашения в консоли компилятора ghci
«:» - операция присоединения элемента к списку.

Упорядоченные множества
Примеры:
(2.4, ”cat”) (Float, )
(’a’, True, 1) (Char, Bool, Int)
(,sqrt) (, Float->Float)
(1, (2, 3)) (Int, (Int, Int))

Но, сердце Haskell и всего функционального программирования - это, конечно, сами функции!

Функции

Функция, в современной математике, это закон соответствия, который сопоставляет каждому элементу x из данного множества A один единственный (или ни одного) элемент y из множества B.
Haskell, по своему назначению, это, прежде всего, язык математиков, поэтому синтаксис тут максимально точно соответствует этому определению.
Пример:
square:: Integer -> Integer square x = x*x
Как вы, наверное, догадались, это функция возведения числа в квадрат. Разберем её подробно:

Первая строка - это объявление функции:
Имя_функции:: область_определения - > область _значений
square:: Integer -> Integer
Тут следует сказать, что в Haskell совсем необязательно всегда объявлять функцию. В ряде случаев интерпретатор и так поймет какие у данной функции области определения и значения. Однако, опускать объявления - моветон.

Вторая строка - это определение функции:
Имя_функции параметры = правило_вычисления
square x = x*x

Функция без параметров есть ничто иное, как константа:
e:: Float e = exp 1.0

Функция с несколькими параметрами:
Спасибо janatem за разъяснения ().
abcFormula:: Float -> Float -> Float -> abcFormula a b c = [ (-b+sqrt(b*b-4.0*a*c))/(2.0*a), (-b-sqrt(b*b-4.0*a*c))/(2.0*a) ] -- находит корни уравнения ax^2+bx+c=0

Определения функций с альтернативами

Как и в любом языке, в Haskell есть конструкции ветвления.
Разберем их на примере функции abs (модуль).
If … then … else …
abs1 x = if x>=0 then x else -x

Case … of …
abs2 x = case x>=0 of True -> x False -> -x

Но, помимо стандартных if и case, в Haskell есть очень красивая и наиболее используемая конструкция ветвления. Так называемые, охранные выражения . Пример:
abs3 x | x>0 = x | x<0 = -x | otherwise = 0
Прямую черту следует читать, как: «при».
Читаем: «Функция abs3, с входным параметром x, при x>0 принимает значение x, при x<0 принимает значение -x, и в любом другом случае принимает значение 0».
Конечно, мы могли записать все с помощью двух охранных выражений, но я записал три, что бы было понятно, что их может быть сколько угодно.
Otherwise в прелюдии определен очень просто:
otherwise:: Bool otherwise = True
То есть, можно спокойно написать вместо «otherwise» «True», но это, опять же, моветон.

Сопоставление с образцом

Один из наиболее распространенных и эффективных приемов в Haskell - это сопоставление с образцом. Вместо параметра мы можем подсунуть функции пример того, как должен выглядеть параметр. Если образец подошел функция выполняется, если нет - переходит к следующему образцу. Например, определение факториала через рекурсию с помощью образцов:
fact:: Integer -> Integer fact 0 = 1 fact n = n * fact (n-1)
Тоже самое, но, с помощью охранных выражений:
fact:: Integer -> Integer fact n | n==0 = 1 | n>0 = n*fact (n-1)
Есть очень распространенный образец для списка: (x:xs). X - обозначает первый элемент, XS - остальной список (кроме первого элемента). «:» - операция присоединения элемента к списку. Примеры из прелюдии:
head:: [a] -> a head (x:_) = x head = error "Prelude.head: empty list" tail:: [a] -> [a] tail (_:xs) = xs tail = error "Prelude.tail: empty list"
Функция head принимает на вход список чего угодно [a] и возвращает первый элемент этого списка. Функция tail принимает на вход список чего угодно [a] и изымает из этого списка первый элемент.
«_» - означает, что данный элемент нас не интересует.

Ну вот, на сегодня и все. Если будет интерес, в ближайшее время напишу продолжение.

Синтаксис двух последовательных идентификаторов означает применение функции foo к своему аргументу bar:

На 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 )

Для определения функции в интерпретаторе GHCi нам нужно использовать ключевое слово let.

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

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

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

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

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

надо расположить параметры в таком порядке: translate languageTo languageFrom text.

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

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

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 )

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

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

Рассмотрим функцию, вычисляющую двойной факториал, то есть произведение натуральных чисел, не превосходящих заданного числа и имеющих ту же четность. Например: 7!!=7⋅5⋅3⋅1, 8!!=8⋅6⋅4⋅2. Предполагается, что аргумент функции может принимать только неотрицательные значения.

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

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

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

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

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

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

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 )

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

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

Prelude > fst (1 ,2 ) 1

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

* 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:

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 в большинстве случаев гарантирует, что программа не завершится с ошибкой доступа к памяти, как, скажем C++, или с ошибкой преобразования типов, как, скажем, Python или Ruby. Большинство подобных ошибок будут обнаружены на этапе компиляции программы.

В основе функционального программирования лежит простое представление о том, что функции в языке ничем не отличаются от переменных. Обычно к этому добавляют, что функции в целом должны быть функциями в математическом смысле, то есть не должны иметь некого внутреннего состояния и не должны неявно изменять внешнего состояния (окружения). Прямым следствием отсутствия состояния является тот факт, что функция, вызванная с одними и теми же аргументами возвращает одно и то же значение. Следствием неизменности внешнего состояния является отсутствие побочных эффектов. Например, printf в C/C++ принимает некие аргументы, и возвращает число. Но кроме этого, printf выводит символы в терминал. Последнее является побочным эффектом. В общем случае, неявные изменения внешнего (по отношнению к программе) состояния считаются побочными эффектами.

Но если внешнее состояние неизменно, программа неизбежно превращается в некую Кантовскую “вещь в себе” – она не может читать/записывать файлы, терминал, и т.д. Это не выглядит очень полезным. На самом деле, ФЯП выходят из положения, вводя некую псевдопеременную “мир”, которая может явно быть передана главной функции программы (main), и ее измененное состояние явно возвращается главной функцией программы. Таким образом, функциональную программу можно алгебраически представить как некую функцию:

\[ W_{n+1} = P(W_{n}), \]

где \(W\) – состояние окружения (“мир”), а \(P\) – это программа.

Другая особенность ФЯП, прямо следующая из того, что функции не имеют и не изменяют состояния заключается в том, что в ФЯП очень часто нет “переменных”. Любые выражения являются константами, если смотреть с точки зрения императивных языков. Это свойство называется “ссылочной прозрачностью”: если вы видите, что функция принимает переменную, вы всегда точно знаете, какое значение имеет эта переменная.

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

Использование чистых функций, помимо прочего, позволяет значительно упростить реализацию функций высших порядков, т.е. функций, оперирующих с функциями (которые тоже могут оперировать с функциями, и так далее). Поэтому, большинство ФЯП имеют поддержку функций высшего порядка “встроенными” в язык интуитивным образом. В качестве небольшого примера, приведу сравнение реализаций функции for_each , работающей со списком на C++ и Haskell.

Функции высшего порядка

На Haskell аналогичный код будет выглядеть так:

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

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

Каррирование

Очень интересным мометном здесь является использование (1+) для добавления 1. Для этого придется рассказать про нотацию Хаскеля Брукса Карри (американского математика, 1900-1982), в честь которого назван язык. Эта нотация называется частичной аппликацией функций или каррирование .

Вкратце, любая функция нескольких аргументов \(f(x,y)\) может быть разложена на последовательное применение нескольких функций одного аргумента. Например, \(f(2,3)\) может быть разложена как:

\[ g(y) = f(2,y) \] \[ f(2,3) = h(g(3)) \]

Можно заметить, что функция двух аргументов \(f(x,y)\) превращается в функцию одного аргумента \(g(y)=f(x,y)\) . Это и есть каррирование. Если записать то же самое в нотации Haskell:

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

Какое отношение это имеет к (1+) ? Самое прямое. (1+) . Сложение является функцией двух аргументов и может быть записано как x+y = (+) x y . Тогда применение к одному аргументу (+) 1 даст нам функцию одного аргумента, которая прибавляет к аргументу 1. (1+) – это просто синтаксическое соглашение (“сахар”), которое сводится к (+) 1 .

Порядок применения функции

Чтобы каррирование работало, аргументы функции применяются слева направо (или лево-ассоциативно). Таким образом, выражение вида

Означает то же самое, что

Это отвечает на вопрос, почему нельзя записать print for_each (1+) и ожидать адекватных результатов (на самом деле такой код просто не скомпилируется, поскольку print for_each не может принимать аргументы)

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

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

Эта-редукция, композиция функций и pointfree-нотация

Другой способ экономии – это эта-редкукция.

Эта-редукция позволяет писать достаточно компактный и при этом вполне понятный код, опуская “лишние” переменные. Такая нотация называется “pointfree” (аргументы иногда называют “точками”, отсюда такое название). Напишем программу, которая читает строки и выводит их в обратном порядке.

Пока не обращая внимания на последнюю строчку (считаем что там магия), рассмотрим функцию revlines. Очевидно, что x здесь вполне избыточен. В математике есть нотация композиции функций, обозначаемая точкой:

\[ f(g(x)) = (f\cdot g)(x) \]

Haskell имеет аналогичную нотацию: f (g x) = (f . g) x . Тогда мы можем переписать revlines в виде

Или, применяя эта-редукцию:

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

Аннотации типов

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

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

Оператор -> – право -ассоциативен (ввиду каррирования), поэтому

т.е. “функция принимает два аргумента”, эквивалентно

т.е. “функция принимает один аргумент и возвращает функцию одного аргумента”

map как функция высшего порядка

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

Получаем чудовищное, по виду, сообщение об ошибке

Couldn"t match type ‘Char’ with ‘’ Expected type: -> Actual type: -> In the first argument of ‘withLines’, namely ‘indent’ In the expression: withLines indent

Почему это происходит? Давайте запишем типы всех функций.

Ошибка становится вполне очевидна: withLines ожидает функцию типа -> , а мы ему даем String->String . Вообще, String определен как , т.е. список символов. Это объясняет сообщение компилятора.

Вспомним про функцию map , которая производит операцию над каждым элементом массива. Ее тип

Подставляя a,b=String , обнаруживаем то, что ищем:

Оказывается, map – это функция высшего порядка, которая преобразует функцию над элементами в функцию над массивами (списками). Подобные операции называются “поднятием” (lift), поскольку “поднимают” функцию из более простой категории типов в более сложную. Вообще, система типов Haskell сильно основана на теории категорий. Однако про теорию категорий сейчас не будем.

Секционирование операторов

Еще один пример использования функций высшего порядка

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

Вообще, `op` – это использование бинарной функции op как бинарного оператора

C тем же успехом можно частично применить второй аргумент:

Этот синтаксический сахар называется “секционирование операторов”

. – это бинарная функция высшего порядка:

Соответственно, если мы перепишем, скажем, withLines с аргументом, то получим:

Типы данных

В примерах раннее мы использовали тип данных списка (массива). Как этот тип устроен? Давайте попробуем сделать пользовательский тип списка.

Теперь мы можем записать что-то такое, например:

В Haskell, естественно, есть встроенный тип списка. Он определен следующим образом:

Можно просмотреть параллели. : – это Добавить, или cons , – это Пусто, или nil , а Список а – это [a] . Мы можем легко определить собственные операторы:

Или использовать их сразу в определении типа.

Единственное, что встроено в язык – это синтаксис вида , который автоматически преобразуется в x:y:...: .

Здесь Добавить и Пусто называются конструкторами типа Список . Это функции, которые “конструируют” значение типа Список. Не имеют практически ничего общего с конструкторами объектов в C++/Java.

Несколько примеров с нашим пользовательским типом:

С mystery1 , mystery2 все должно быть понятно. mystery3 – это бесконечный список, и Haskell все устраивает (поскольку это ленивый язык – значения вычисляются только при использовании), mystery4 – это ошибка типа. Int и String не могут находиться в одном списке.

Аналогично пишутся прочие типы данных.

Шаблоны аргументов

Для простоты, переопределим наш тип списка в латинице и сразу используем оператор:

Напишем несколько функций для нашего пользовательского списка:

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

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

Если мы не указываем все возможные варианты, то компилятор сообщает об этом, например:

Приводит к сообщению

Pattern match(es) are non-exhaustive In an equation for ‘isOne’: Patterns not matched: Nil

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

Тип Maybe

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

undefined – ключевое слово, которое подходит под любой тип и аварийно завершает программу при попытке вычисления. Другой вариант undefined – это error x , где x имеет вид String . error выведет строку x перед завершением.

На помощь приходит тип Maybe . Он определен так:

В целом похоже на список, только без списка. takeOne можно переписать в виде:

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

Попробуем написать поиск символа в строке с использованием типа Maybe:

Pattern guards

Предыдущий код можно переписать несколько короче:

Этот синтаксис называется “pattern guards”, или ограничители шаблонов в вольном переводе на русский. По сути, если выражение после | вычисляется как True , то шаблон срабатывает. Если нет – то проверяется следующий ограничитель, или следующий шаблон, если это был последний. otherwise – это просто более читаемый синоним для True .

В ограничителях так же возможно производить сравнения шаблонов. Синтаксис для этого:

Тогда код выше можно переписать в виде:

Классы типов

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

Мы изменили только сигнатуру типа, остальное осталось прежним. Сигнатура выглядит странновато: в ней появилось выражение Eq a => . Оно означает, что тип a принадлежит классу Eq – классу типов, для которых определена эквивалентность, т.е. опреатор (==) .

Eq определен следующим образом:

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

Каким конкретно образом реализовано сравнение символов – довольно долгая история. Примитивные типы типа Int , Char или скажем Double достаточно глубоко встроены в язык. Мы, однако, можем определить экземпляры для более сложных типов:

Здесь мы опять вводим ограничение на класс. По сути мы утверждаем, что для всех типов a в классе Eq существует тип Maybe a , так же в классе Eq . Ничто не мешает добавлять собственные типы.

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

Опять про Maybe

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

Это гораздо лучше, чем возвращать NULL , как в C/C++ . Во-первых, глядя на сигнатуру типа, сразу становится ясно, чего можно ожидать от функции. Во-вторых, компилятор не позволит производить вычисления с несуществующим значением. Если в “классических” языках типы в основном служат компилятору, то в функциональных типы служат в первую очередь программисту.

Очевидный вопрос с Maybe заключается в следующем: допустим у нас есть функция

Рассмотрим такой код:

Каков результат такого кода? Правильный ответ – ошибка типа. 1 имеет тип Int , в то время как takeOne возвращает тип Maybe Int . Проблема очевидна. Наивное решение этой проблемы в том, чтобы написать условие:

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

Теперь давайте вспомним, что, когда я говорил про map , я сказал, что эта функция “поднимает” свой первый аргумент в категорию списков. Эта же концепция применима ко всем производным типам. В языке сущесвтует обобщенная функция fmap . Посмотрим, как она работает:

Это выражение возвращает Just 2 . fmap “поднимает” свой аргумент в категорию производных типов. Каких именно – компилятор выводит автоматически из контекста.

Тип fmap определен как

Здесь используется класс Functor , единственное требование которого – чтобы был определен fmap . Для Maybe экземпляр определяется тривиально:

В общем случае класс Functor – это класс типов, принимающих один аргумент типа. Другой пример функтора – список. Таким образом, map является всего лишь частным случаем fmap .

Монады

Пока скажу только, что Maybe , и список являются монадами. Понятие монады происходит из теории категорий. Это понятие в большинстве функциональных языков является ключевым, поскольку, например, Haskell, инкапсулирует состояние окружения (то, которое функции не изменяют) в монаде IO (ввод-вывод). Наконец мы можем записать сигнатуру для main:

Функция main возвращает “пустоту” (на самом деле читается как unit, и аналогично по смыслу void в С) в монаде IO . IO , в свою очередь, где-то “внутри” содержит информацию о состоянии окружения.

Сточка, которая часто нам встречалась

использует следующие функции:

return и (>>=) (читается как bind) определены в классе Monad . return просто “поднимает” значение в монаду, а bind берет значение в монаде и передает его в функцию, возвращающую монаду. При этом некое “состояние”, инкапсулированное монадой (если оно есть), может неявно передаваться из функции в функцию через оператор bind.

Для интересующихся, хорошее объяснение:

Если есть интерес, выделим лекцию на продолжение.

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

Конспект лекций

Рыбинск 2010

Введение..................................................................................................................... 3

1 История функционального программирования.................................................... 4

2 Особенности функциональных языков................................................................... 5

2.1 Основные свойства........................................................................................ 5

2.2 Преимущества............................................................................................... 9

2.3 Недостатки................................................................................................... 11

3 Обзор существующих языков............................................................................... 13

4 Базовые принципы языка Haskell......................................................................... 16

4.1 Интерактивная среда.................................................................................. 16

4.2 Структура программы............................................................................... 18

4.3 Типы функций............................................................................................. 22

4.4 Условные вычисления (ветвление).............................................................. 24

4.5 Сопоставление с образцом......................................................................... 27

4.6 Списки......................................................................................................... 29

4.7 Локальные определения............................................................................. 33

4.8 Дополнительные возможности интерактивной среды.............................. 35

4.9 Функции высшего порядка......................................................................... 36

4.10 Бесконечные структуры данных.............................................................. 37

5 Типы данных и модули......................................................................................... 40

5.1 Пользовательские типы и структуры данных........................................... 40

5.2 Модули........................................................................................................ 44

6 Классы и монады................................................................................................... 47

6.1 Классы......................................................................................................... 47

6.2 Ввод-вывод.................................................................................................. 49

7 Примеры................................................................................................................ 53

Заключение.............................................................................................................. 54

Список использованных источников...................................................................... 55

Введение

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

Но даже ассемблеры не могли стать тем инструментом, которым смогли бы пользоваться многие люди, поскольку мнемокоды всё ещё оставались слишком сложными, а всякий ассемблер был жёстко связан с архитектурой, на которой исполнялся. Следующим шагом после ассемблера стали так называемые императивные языки высокого уровня: Бейсик, Паскаль, Си, Ада и прочие, включая объектно-ориентированные. Императивными («предписывающими») такие языки названы потому, что ориентированы на последовательное исполнение инструкций, работающих с памятью (т. е. присваиваний), и итеративные циклы . Вызовы функций и процедур, даже рекурсивные, не избавляли такие языки от явной императивности.

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

2 История функционального программирования

Как известно, теоретические основы императивного программирования были заложены ещё в 1930-х годах Аланом Тьюрингом и Джоном фон Нейманом . Теория, положенная в основу функционального подхода, также родилась в 20-х - 30-х годах. В числе разработчиков математических основ функционального программирования можно назвать Моисея Шейнфинкеля и Хаскелла Карри, разработавших комбинаторную логику, а также Алонзо Чёрча, создателя λ-исчисления (лямбда-исчисления).

Теория так и оставалась теорией, пока в начале 1950-х годов Джон Маккарти не разработал язык Лисп (Lisp), который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется, после многих лет эволюции он удовлетворяет современным запросам .

В связи с все возрастающей сложности программного обеспечения всё большую роль начинает играть типизация. В конце 70-х - начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм . Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов. Практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов.

3 Особенности функциональных языков

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

3.1 Основные свойства

Среди свойств функциональных языков обычно выделяют следующие:

– краткость и простота;

– строгая типизация;

– функции – это значения;

– чистота (отсутствие побочных эффектов);

– отложенные (ленивые) вычисления;

– модульность.

Рассмотрим каждое из этих свойств подробнее.

Краткость и простота

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

На императивном языке C быстрая сортировка обычно реализуется следующим образом:

void qsort (int a, int l, int r)

int i = l, j = r, x = a[(l + r) / 2];

while (a[i] < x) i++;

while (x < a[j]) j--;

int temp = a[i];

while (i <= j);

if (l < j) qsort (a, l, j);

if (i < r) qsort (a, i, r);

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

qsort (x:xs) = qsort

++ [x] ++ qsort

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

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

Строгая типизация

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

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

– функции могут принимать и возвращать значения, имеющие строго тот же тип данных, что указан при описании функции;

– каждая операция требует аргументов строго определённых типов;

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

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

Функции как значения

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

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

Чистота

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

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

Отложенные вычисления

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

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

Модульность

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

3.2 Преимущества

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

Надежность программирования

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

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

Удобство модульного тестирования

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

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

Возможности оптимизации

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

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

Доказательство свойств функций

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

3.3 Недостатки

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

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

4 Обзор существующих языков

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

Рассмотрим особенности каждого из этих языков:

– Lisp . Получил название от английского LISt Processing – обработка списков. Lisp является одним из самых первых языков функционального программирования. Программы и данные в Lisp представляются системами линейных списков символов. Язык Lisp, наряду с языком Ada, прошел процесс фундаментальной стандартизации для использования в военном деле и промышленности, в результате чего появился стандарт Common Lisp. Его реализации существуют для большинства платформ. Первые области применения Лиспа были связаны с символьной обработкой данных и процессами принятия решений . Наиболее популярный сегодня диалект Common Lisp является универсальным языком программирования. Он широко используется в самых разных проектах: Интернет-серверы и службы, серверы приложений и клиенты, взаимодействующие с базами данных , научные расчёты и игровые программы.

– Haskell . Является одним из самых распространённых ленивых языков программирования. Имеет очень развитую систему типизации. В последнее время расширяется набор прикладных библиотек, язык интегрируется в распространённые программные системы, что делает язык всё более и более привлекательным для профессиональных программистов. Основные особенности языка: возможность использования лямбда-абстракции; функции высшего порядка; частичное применение; недопустимость побочных эффектов (чистота языка); ленивые вычисления (lazy evaluation); сопоставление по образцу, функциональные образцы (pattern matching); параметрический полиморфизм и полиморфизм классов типов; статическая типизация; автоматическое выведение типов (основано на модели типизации Хиндли – Милнера); алгебраические типы данных; типы данных с параметрами; рекурсивные типы данных; абстрактные типы данных (инкапсуляция); списочные включения (list comprehensions); охраняющие выражения (guards); возможность писать программы с побочными эффектами без нарушения парадигмы функционального программирования с помощью монад; возможность интеграции с программами, реализованными на императивных языках программирования посредством открытых интерфейсов (стандартное расширение языка Foreign Function Interface).

– ML (Meta Language) – семейство строгих языков функционального программирования с развитой полиморфной системой типов и параметризуемыми модулями. ML преподаётся во многих западных университетах. Сильно типизированный язык со статическим контролем типов и аппликативным выполнением программ. Основные достоинства ML – высокая верифицируемость программ, простота отладки, потенциал для высокой оптимизации, уникальная краткость записи. Основные недостатки – сложность синтаксиса, непривычность принятых соглашений и ограничений, практическая невозможность макротрансформаций.

– Erlang – функциональный язык программирования, позволяющий писать программы для разного рода распределённых систем. Разработан и поддерживается компанией Ericsson. Язык включает в себя средства порождения параллельных процессов и их коммуникации с помощью посылки асинхронных сообщений. Программа транслируется в байт-код, исполняемый виртуальной машиной, что обеспечивает переносимость. Главное в Erlang – его модель легковесных процессов. Перефразируя для Erlang слоган «Everything is an object» («Всё является объектом»), можно сказать «Everything is a process» («Всё является процессом»). Процессы дёшевы, создание процесса занимает не больше ресурсов, чем вызов функции. Единственным способом взаимодействия процессов является асинхронный обмен сообщениями.

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

5 Базовые принципы языка Haskell

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

Для начала рассмотрим необходимый инструментарий для работы. Самым распространенным и эффективным на сегодняшний день является компилятор GHC (Glasgow Haskell Compiler). Он распространяется под открытой лицензией, и любой желающий может загрузить его исходные коды или скомпилированную версию для популярных операционных систем с официального сайта http://haskell. org/ghc/ (кроме того, на сайте http://haskell. org/ можно найти много дополнительной информации по языку).

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

К сожалению, полнофункциональной среды разработки для Haskell еще не разработано (кроме, возможно, Leksah - среды разработки для Haskell, написанной на Haskell, и нескольких плагинов для Visual Studio и Eclipse), но зачастую хватает возможностей лишь расширенного текстового редактора (например, Notepad++, gedit, kate) с подсветкой синтаксиса и некоторыми другими возможностями.

5.1 Интерактивная среда

Интерактивная среда GHCi может вычислять любые выражения на языке Haskell. Рассмотрим основы работы с этой средой. Для ее запуска (после установки GHC или Haskell-Platform) достаточно запустить в консоли программу ghci (либо выбрать соответствующую программу в списке всех программ). После запуска в консоли появится приглашение:

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

Здесь мы можем вычислить любое выражение, например обыкновенное арифметическое выражение:

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

Prelude> 1-2*(4-3^2)

Возведение в степень (^) является стандартным оператором, определенным в стандартном модуле Prelude наравне с операциями сложения и умножения.

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

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

Prelude> max 7 100

В данном примере вычисляется максимальное из двух чисел - семи и ста. Как мы видим, результатом вычисления функции является число 100.

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

Prelude> max (2^^3)

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

Prelude> max (2^10) 10^3

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

Кроме того, интерактивная среда GHCi может автоматически дополнять имена вводимых функций. Если набрать только начальную часть имени функции и нажать на клавиатуре клавишу «Tab», то GHCi попытается дополнить имя функции до имеющегося среди доступных определений (из стандартного модуля, либо подключенных пользователем). Например, если набрать «maxi» и нажать «Tab», то GHCi дополнит имя функции до «maximum». В том случае, если однозначно дополнить невозможно (есть несколько подходящих вариантов), то выводятся все возможные варианты:

max maxBound maximum

Теперь можно уточнить имя функции (дописав несколько букв) и снова нажать клавишу «Tab».

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

5.2 Структура программы

Компиляторы и интерпретаторы языка Haskell работают с файлами с расширением *.hs , содержащими текст программы. Текст программы имеет следующую структуру:

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

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

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

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

В данном примере объявляется символ с именем five, который имеет значение, равное целому числу 5. Имена в Haskell чувствительны к регистру, то есть Five и five являются различными именами. Кроме того, вводится дополнительное ограничение на первую букву имени - имена функций и их аргументов могут начинаться только со строчной буквы (five, max, min, x, y), а имена типов данных (Bool, Integer, Double), модулей (Main, Test) и классов (Eq, Ord, Num) - только с прописной (заглавной).

Рассмотрим пример посложнее:

three = one + two

Здесь объявляется три символа - one, two, three. Как видно из примера, каждое определение занимает одну строчку и разделяются они только концом строки (пустые строчки будут игнорироваться). Символы one и two определены также, как и символ five в предыдущем примере, а при определении символа three используются уже существующие определения. Как несложно догадаться, символ three будет иметь значение 3.

Порядок определений не важен, то есть следующий пример будет совершенно аналогичен предыдущему:

three = one + two

Загрузим наш пример в интерактивную среду GHCi. Для этого достаточно при запуске ghci в качестве параметра командной строки указать имя файла с текстом программы (например, Test. hs) (в ОС семейства Windows достаточно просто открыть файл, установленный GHC автоматически назначает ghci для открытия файлов *.hs). Если программа не содержит ошибок, то мы увидим уже знакомое приглашение:

Здесь Main - имя текущего модуля (подробнее модули рассматриваются в соответствующей главе). GHCi позволяет вычислять любые функции из текущего модуля. Например, вычислим наш символ three:

Более сложные выражения также возможны:

*Main> (three+two)^2

*Main> max one two

Далее рассмотрим функции с аргументами. В отличие от привычных языков программирования для передачи аргументов не требуется записывать их в скобках и через запятую. Вызов функции происходит в следующем виде: func x1 x2 x3… xN, где func – имя функции, а xi – i-й аргумент. Результатом функции будет являться какой-либо объект, например, число, список, функция, лямбда-выражение либо любая другая структура данных.

Описание функции с аргументами практически не отличается от описания символов в предыдущих примерах. Определение функции располагается на отдельной строчке и имеет следующий вид: func x1 x2 x3… xN = expression, где func - имя новой функции, xi – имя i-го аргумента, expression - выражение.

Например, добавим функцию, складывающую два числа, в существующий файл Test. hs.

Теперь мы можем перезагрузить в интерактивной среде измененный модуль. Для этого достаточно перезапустить ghci, либо воспользоваться стандартной командой «:r»:

Compiling Main (Test. hs, interpreted)

Ok, modules loaded: Main.

После этого новая функция становится доступной из интерактивной среды:

*Main> plus one 8

Еще один пример функции с аргументами:

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

Однострочные комментарии в языке Haskell начинаются с двух тире:

plus x y = x+y --функция сложения

Блочный комментарий начинается с “” и заканчивается “”:

эта функция возвращает число на 1 большее

чем полученное в качестве аргумента

5.3 Типы функций

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

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

	Описание
	целое число от - до
	длинное целое число, без границ (предусмотрено использование встроенной длинной арифметики)
	вещественное число
	вещественное число удвоенной точности
	список элементов некоторого типа a, например, список целых чисел записывается как
	строка (или список символов), эквивалент
	логический тип (принимает значения True или False)
	кортеж из двух элементов типа a и b (например, (String, Bool))
	кортеж из трех элементов типа a, b и c (например, (String, Bool, Int))

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

Первая строчка означает, что функция pi имеет тип Double, затем идет само определение функции, означающее, что функция pi возвращает приближенное значение числа пи. Если же функция имеет один аргумент, то ее тип описывается следующим образом:

inc:: Integer -> Integer

Данная запись означает, что функция inc преобразует аргумент типа Integer в результат типа Integer.

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

power:: Double -> Integer -> Double

Функция power принимает два аргумента – вещественное основание x и целая степень n, результатом же вычисления функции является вещественное число.

В общем виде описание типа функции выглядит так так:

name:: X1 -> X2 -> ... ->XN -> Y

Здесь name – имя функции, Xi – тип i-го аргумента, Y – тип функции.

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

Перечислим некоторые стандартные функции.

Функции	Описание
	традиционные арифметические операции
	деление вещественных чисел
	возведение числа в целочисленную положительную степень
	возведение числа в вещественную степень
	целочисленное деление и остаток от деления целых чисел
	квадратный корень
	тригонометрические функции
asin, acos, atan	обратные тригонометрические функции
	сравнение на равенство и неравенство
>, <, >=, <=	сравнение
	логические операции
	первый элемент пары (кортежа из двух элементов)
	второй элемент пары
	хвост (все элементы кроме первого) списка

5.4 Условные вычисления (ветвление)

В традиционных языках программирования основными способами организации ветвления являются условный оператор (if then else) и оператор выбора (case или switch). Кроме них в языке Haskell используется сопоставление с образцом в определениях функций и так называемые охраняющие выражения. Рассмотрим подробнее каждый из этих способов.

Конструкция if-then-else

Синтаксическая конструкция «if-then-else» позволяет вычислять различные выражения в зависимости от результатов некоторого условия:

if <условие> then <выражение1> else <выражение2>

Здесь <условие> - некоторое выражение, имеющее тип Bool. В отличие от императивных языков, в языке Haskell конструкция «if-then-else» является выражением, которое обязательно должно иметь какой-либо результат. В связи с этим ветка else является обязательной и типы выражений <выражение1> и <выражение2> должны совпадать.

Рассмотрим в качестве примера функцию вычисления максимального из двух чисел:

max a b = if a>b then a else b

Как уже было сказано, конструкция «if-then-else» является выражением, которое имеет результат. Следовательно, ее можно использовать как часть другого выражения:

*Main> 5 + if False then 1 else 0

*Main> (if True then 1 else 0) + 5

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

*Main> if True then 1 else 0 + 5

Все, что записано после слова «else» относится к выражению ветки else.

Конструкция case

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

fib n = case n of

_ -> fib (n-1) + fib (n-2)

Также как и условное выражение «if-then-else» выражение case имеет результат и, следовательно, может быть частью других выражений.

Рассмотрим case выражение в общем виде:

case <выражение0> of

<образец1> -> <выражение1>

<образец2> -> <выражение2>

<образецN> -> <выражениеN>

Здесь результат вычисления <выражение0> последовательно сопоставляется с образцами. При удачном сопоставлении с i-м образцом, результатом всего case будет являться результат i-го выражения. Подробнее сопоставление с образцом будет рассматриваться в соответствующем разделе, а пока его можно рассматривать как сравнение с заданными константами.

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

Кроме того, допустим альтернативный способ записи case-выражений без использования отступов:

fib n = case n of {1->1;2->1;_->fib (n-1) + fib (n-2)}

Такой способ более компактен, но менее нагляден. В общем виде:

case <выражение0> of { <образец1> -> <выражение1> ; <образец2> -> <выражение2> ; ... ; <образецN> -> <выражениеN> }

Определения функций

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

Рассмотрим в качестве примера функцию вычисления числа Фибоначчи.

fib n = fib (n-1) + fib (n-2)

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

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

Охраняющие выражения

Последним способом выбора альтернатив при вычислении результата функций является так называемые охраняющие выражения . Они (в отличие от if-then-else и case-выражений) могут использоваться только в определениях функций:

<имя функции> <список аргументов функции>

|<условие1> = <выражение1>

|<условие2> = <выражение2>

|<условиеN> = <выражениеN>

Все символы “|” должны начинаться на своей строке и с одного отступа. При вычислении значения функции перебираются сверху вниз все условия, являющиеся выражениями типа Bool. Когда найдется i-е условие, результат которого равен True, вычисляется выражение i, результат которого будет результатом функции.

Например, запишем функцию нахождения числа Фибоначчи:

|otherwise = fib (n-1) + fib (n-2)

Здесь otherwise – это заведомо истинное условие, всегда равное True.

5.5 Сопоставление с образцом

Сопоставление с образцом (pattern matching) - это удобный способ связать различные части некоторого значения с заданными именами (символами) . Сопоставление с образцом используется в определениях и в case выражениях.

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

f x = fst x + snd x

Данная функция вычисляет сумму элементов кортежа. Стандартные функции fst и snd получают первый и второй элемент кортежа соответственно.

*Main> f (2,4)

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

При вычислении этой функции от (2,4) элементы этого кортежа будут сопоставлены с указанным в определении функции образцом, то есть символ «a» примет значение 2, а символ «b» примет значение 4.

Так мы можем определить аналоги функций fst и snd:

Обратим внимание, что в определении функции fst1 не используется x, а в определении функции snd1 не используется y. В таких случаях, когда часть образца (или целый аргумент) не используется нет необходимости указывать имя этой части (или аргумента) - вместо имени достаточно указать символ подчеркивания «_». Переопределим эти функции:

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

В образцах могут указываться любые конструкторы (в предыдущих примере использовался конструктор кортежа), например, конструкторы списка, кортежа, или любых пользовательских типов данных, а также конкретные значения аргументов (как в примере про числа Фибоначчи). В некоторых случаях сопоставление может оказаться неудачным, тогда происходит попытка использовать следующее сопоставление (из следующего определения или образца case). Рассмотрим пример:

f _ 0 = error "division by zero"

f (a, b) c = (a+b)/c

Здесь при вычислении функции f второй аргумент будет равен 0, то для вычисления функции будет выбрано первое определение, иначе - второе, так как сопоставление с именем всегда удачно. Функция error останавливает выполнение программы с заданным текстом ошибки. Примеры использования описанной функции:

*Main> f (1,2) 3

*Main> f (3,2) 1

*Main> f (5,5) 5

*Main> f (5,5) 0

*** Exception: division by zero

Кроме того, каждый образец может быть поименован для того чтобы к структурированному аргументу был доступ и поэлементно и целиком. Для именования образца используется оператор @. Перед ним идет имя, через которое можно осуществлять доступ к аргументу как к единому целому, а затем сам образец. Например,

func1 p@(a, b) = a + b + func2 p

func2 (a, b) = a*b

5.6 Списки

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

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

Существует и более удобный способ записи списков: перечислением элементов в квадратных скобках. Например, список целых чисел от 1 до 3 может быть записан так:

1: = 1:2: = 1:2:3:

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

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

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

Аналогично можно описать операцию взятия хвоста списка.

Эти две функции (head и tail) вызовут ошибку при передачи им пустого списка, так как сопоставление не будет успешным.

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

length (_:t) = 1 + length t

Если входной список пуст, то в результате сопоставления сработает первое определение, иначе – второе.

Строки в языке Haskell являются списками символов. Символы записываются в апострофах (например, "c"), а строки – в кавычках (например, "string"). Любую строку можно представить в стандартной записи списков, например, строка "string" аналогична списку ["s","t","r","i","n","g"]. Работа со строками выполняется точно так же, как со списками.

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

getN (x:_) 0 = x

getN (_:t) n = getN t (n-1)

Взятие n-го элемента списка реализовано в стандартной функции "!!". Она используется так:

Здесь list – список, n – номер искомого элемента. Нумерация элементов начинается с нуля. Если длина списка окажется меньше или рана номеру искомого элемента, вычисление этой функции приведет к ошибке.

Кроме того, возможно задание списков из перечислимых элементов (например, целые числа или символы) следующим образом:

Здесь X1 – начало арифметической прогрессии, а X2 – ее конец. Например, является списком . Таким способом можно задавать только возрастающие списки с шагом равным единице. Если нужно задать последовательность с другим шагом, то можно использовать следующую запись:

В этом варианте X1 – первый элемент последовательности, X2 – второй, X3 – возможный последний. Шаг последовательности выбирается как X2-X1, и последовательность содержит элементы, расположенные только между X1 и X3. Например, является списком .

Также существует способ задания списков на основе уже существующих. В общем виде этот способ можно записать так:

[<выражение> | <образец> <- <список>, <ограничение1>, ..., <ограничениеN>]

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

[ x^2 | x <- ,mod x 3 == 0]

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

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

map:: (a -> b) -> [a] -> [b]

map f xs =

То есть, она принимает в качестве первого аргумента функцию, преобразующую объекты типа a в объекты типа b, а в качестве второго аргумента – список из элементов типа a. Результатом функции map является список элементов типа b.

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

map (\x->x*x)

Результатом данной функции является список:

Так как в языке Haskell есть встроенная операция возведения в степень, то данный список можно получить так:

map (^2)

Также, можно применять и любые другие функции, например:

map inc

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

Имя функции		Описание
		голова (первый элемент) списка
		хвост (все кроме первого элемента) списка
		последний элемент списка
		все элементы списка кроме последнего
	[a] → Int → a	элемент с заданным номером
		вычисление длины списка
	Int → [a] → [a]	взять из списка n первых элементов
	Int → [a] → [a]	отбросить из списка n первых элементов
		разворачивание списка в обратном порядке
	(Num a) => [a] → a	сумма элементов списка
	(Num a) => [a] → a	произведение элементов списка
	[a] → [a] → [a]	конкатенация списков

5.7 Локальные определения

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

Существует два способа описания локальных функций: с помощью зарезервированного слова where и let . Определение локальных функций с помощью where может использоваться только в определении функции. Определим функцию вычисления среднего арифметического трех чисел:

average3 x y z = s / 3

В общем виде использование where может быть записано так:

<имя функции> <аргументы> = <выражение>

<определение 1>

<определение 2>

<определение N>

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

<имя функции> <аргументы> = <выражение> where { <определение 1> ; <определение 2> ; ... ; <определение N> }

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

average3 x y z =

В общем виде этот способ выглядит так:

<определение 1>

<определение 2>

<определение N>

<выражение>

Все определения должны находиться на одном и том же отступе, но большем чем строка, содержащее let. Слово in должно находится на отступе не меньшем чем let. При желании можно использовать следующий синтаксис:

let { <определение 1> ; <определение 2> ; ... ; <определение N> } in <выражение>

В таком случае отступ игнорируется.

5.8 Дополнительные возможности интерактивной среды

В интерактивной среде GHCi кроме вычисления функций или выражений есть множество дополнительных возможностей. Многие из них доступны через команды, начинающиеся с символа «:». Например, написав в строке GHCi команду «:?» можно увидеть список всех остальных команд (по командам также работает автодополнение). Рассмотрим наиболее полезные команды.

:t - получение типа указанного выражения. Например:

*Main> :t reverse (tail "mama")

reverse (tail "mama") ::

:i - получение информации о функции (тип, в каком модуле или классе определена). Например:

*Main> :i reverse

reverse:: [a] -> [a] -- Defined in GHC. List

:l - загрузить указанный модуль и сделать его текущим.

:m - загрузить или выгрузить указанный модуль.

:q - закрыть GHCi.

Еще одной полезной особенностью является возможность задания определений функций прямо в GHCi. Для этого используется упрощенная конструкция let. Например:

*Main> let f x = x+2*x

Полная же конструкция let действует только в пределах своего выражения:

*Main> let z = 10 in z+z

:1:0: Not in scope: `z"

GHCi сообщает, что данное имя не определено в текущей области видимости.

5.9 Функции высшего порядка

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

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

Дописать как следует этот раздел

Рассмотрим функцию сложения двух чисел:

plus x y = x + y

Функцию plus можно описать иначе:

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

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

Еще вариант описания функции plus:

Используя функцию plus (любую вышеприведенную реализацию), можно написать функцию инкрементации:

inc x = plus 1 x

Используя каррирование можно получить другую реализацию этой же функции:

Получается, что функция inc возвращает функцию, прибавляющую 1 к одному своему параметру.

Кроме такого способа записи функций в Haskell"е существует способ задания с помощью λ-исчислений. Например, функция plus может быть реализована следующим образом:

plus = \x y -> x+y

Здесь “\” означает начало λ-выражения, затем перечисляются параметры (x y), и после стрелки (->) идет выражение.

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

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

(\x y -> x+y) 3 6

Результатом будет число 9.

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

Если какой-либо параметр функции не используется при вычислении ее значения, то его имя можно опустить, заменив символом “_”. Например, функция, возвращающая первый параметр из двух, может выглядеть так:

Либо, в обычной записи:

firstoftwo x _ = x

5.10 Бесконечные структуры данных

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

Очевидно, что её значение не может быть вычислено. При попытке это сделать, произойдет зацикливание. Рассмотрим еще одну функцию:

Её значение не зависит от параметра х. Следовательно нет необходимости его вычислять. И вычисление выражения

не приведет к зацикливанию и вернет результат равный 1.

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

Они задаются только первыми двумя элементами, по которым вычисляется шаг прогрессий. Если второй элемент прогрессии не указан (как в первом примере), то шаг принимается равным 1.

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

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

fact n = factlist !! n

factlist = fl 1 1

where fl x n = x:(fl (x*n) (n+1))

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

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

6 Типы данных и модули

6.1 Пользовательские типы и структуры данных

При описании типов функций могут потребоваться пользовательские синонимы уже существующих типов. Например, при громоздком определении некоторого типа удобно назвать его одним именем. Не очень приятно каждый раз писать что-нибудь наподобие [(Integer,)], удобнее дать этому типу имя, например, MyType1. Такое определение имеет вид:

type MyType1 = [(Integer,)]

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

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

data <имя> = <значение1> | <значение2> | ... | <значениеN>

Таким образом, описывается структура данных с именем <имя>, которая может принимать значение 1, значение 2, и так далее до значения N. Этими значениями типа данных являются конструкторы данных. Каждый конструктор должен иметь уникальное имя, начинающееся с прописной буквы. Имя конструктора данных может совпадать с именем типа данных Например, описание типа данных «цвет» может быть представлено так:

data Color = Red | Green | Blue

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

data Color = Red | Green | Blue | RGB Double Double Double

Такая запись означает, что объекты типа Color могут принимать значения Red, Green, Blue либо RGB r g b, где r g b - вещественные числа. Например, можно определить функцию, возвращающую желтый цвет:

Задание типов данных может быть полиморфным, так же как задание функций. То есть, можно задать такой тип данных, который содержит в себе некоторый другой, но не конкретный тип. Например, стандартный тип Maybe может быть описан следующим образом:

data Maybe a = Nothing | Just a

Это означает, что объект типа (Maybe a) может быть принимать значение Nothing, либо Just x, где x – объект некоторого типа a. Для доступа к таким объектам используется сопоставление с образцом. Например, можно реализовать функцию unJust, которая вернет содержимое контейнерного класса Maybe если оно не равно Nothing.

unJust (Just a) = a

Рассмотрим еще пример:

find:: (Eq a) => a -> [a] -> Maybe Int

find _ = Nothing

| x == a = Just 0

| otherwise = case (find a xs) of

(Just i) -> Just (i+1)

Nothing -> Nothing

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

С помощью ключевого слова data можно описывать любые структуры данных. Опишем в качестве еще одного примера бинарное дерево:

data Tree a = Nil | Node a (Tree a) (Tree a)

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

Опишем функцию добавления элемента в бинарное дерево поиска.

addtotree Nil x = Node x Nil Nil

addtotree (Node y left right) x

|x

|x>y = Node y left (addtotree right x)

|otherwise = Node y left right

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

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

showtree tree = showtr tree 0 where

showtr (Nil) n = replicate n "\t" ++ "-\n"

showtr (Node x left right) n =

showtr right (n+1) ++

replicate n "\t" ++ show x ++ "\n" ++

showtr left (n+1)

Локальная функция showtr принимает два аргумента - дерево и уровень глубины. Используемая функция show является стандартной функцией для перевода в строковый вид практически любых объектов в Haskell.

Теперь в результате вычисления выражения

addtotree (addtotree (addtotree (addtotree

(addtotree (addtotree (addtotree Nil

которое означает последовательное добавление в дерево целых чисел 5, 3, 8, 1, 4, 6, 9, получим некоторый объект типа Tree. Передав его нашей функции showtree, получим строковое представление этого дерева.

Существует еще один способ определения пользовательских данных - ключевое слово newtype. Его использование практически аналогично data, за исключением одного: типы данных, описанные с помощью newtype имеют только один конструктор данных ровно с одним полем. Этот способ используется для создания нового типа данных на основе уже имеющегося:

newtype MyInt = MyInt Int

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

<имя записи> {

<имя поля 1> :: <тип поля 1>,

<имя поля 2> :: <тип поля 2>,

<имя поля N> :: <тип поля N>}

Например:

data Human = Human {

height:: Double,

Для задания объекта данного типа можно записать:

mike = Human{name="Mike",height=173.4,weight=81.3}

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

john = mike{name="John"}

6.2 Модули

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

Каждый модуль должен иметь вид:

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

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

import <модуль1>

import <модульN>

<остальной код>

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

import <модуль> hiding (<скрываемые определения>)

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

module <Имя>(<определения>) where <код>

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

В качестве примера можно привести программу из 3х модулей:

-- Prog . hs

module Prog where

import Mod2 hiding(modfun)

module Mod1(modfun) where

modfun = five * 2

module Mod2 where

Из модуля Prog доступна функция modfun, определенная в модуле Mod1, но не доступна функция five.

7 Классы и монады

7.1 Классы

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

Для определения класса используется следующая запись:

сlass [(<ограничения>) =>] <имя> <переменная типов> where <функции>

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

class Eq a where

(==), (/=) :: a -> a -> Bool

x == y = not (x/=y)

x /= y = not (x==y)

Класс Eq является классом сравнимых типов. Для каждого экземпляра этого класса должны быть определены функции равенства и неравенства. Вторая строка означает, что функции (==) и (/=) должны принимать два аргумента типа a и возвращать объект типа Bool, то есть True или False.

Следующие строчки в определении класса говорят о том, что если определена функция (/=), то функция (==) определяется через нее соответствующим образом, и наоборот. Благодаря этому программисту достаточно определить только функцию сравнения на равенство (или неравенство), а другую функцию интерпретатор определит сам.

Еще пример определения класса, но с наследованием:

class Eq a => MyClass a where

myFunc:: [a] -> a -> Int

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

instance MyClass Double where

|x==z = 1 + myFunc xs z

|otherwise = myFunc xs z

Таким образом мы объявляем стандартный тип Double экземпляром нашего класса MyClass и определяем функцию myFunc как функцию, вычисляющую количество элементов в первом аргументе, равных второму аргументу функции.

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

test = myFunc x 2 where

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

Когда программист описывает свою структуру данных, она не принадлежит ни к какому из классов. При необходимости программист должен реализовать соответствующие функции для своей структуры и указать ее принадлежность к классу. Например, ранее описанную структуру данных Tree можно объявить экземпляром класса Show, для того что бы интерпретатор мог выводить ее на экран, не прибегая к ручному вызову функции showtree. Для этого напишем:

instance Show a => Show (Tree a) where

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

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

data <имя> = <значение1> | <значение2> | ... | <значениеN> deriving (<класс1>,<класс2>,...,<классM>)

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

data Tree a = Nil | Tree a (Tree a) (Tree a)

Теперь возможно сравнение деревьев операцией “==”, и позволяет использовать их в функциях, требующих это.

7.2 Ввод-вывод

Возможно написать побольше про монады

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

putStrLn "Hello world!"

putStrLn "Good bye world!"

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

При использовании нотации do программирование «нечистых» функций с помощью монад сводится практически к привычному императивному программированию.

Каждая следующая строчка должна быть функцией специального типа - монадического типа. В случае работы с вводом-выводом это тип (IO a).

Для работы с командной строкой используются следующие функции:

putChar:: Char -> IOвывод символа

putStr:: String -> IOвывод строки

putStrLn:: String -> IOвывод строки с переходом на новую строку

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

putStrLn "What is you name?"

name <- getLine

Здесь появилось «присваивание». По аналогии с императивными языками можно сказать, что в строке

name <- getLine

произошло присваивание переменной name результата функции getLine. Но, как мы знаем, в Haskell"е нет переменных и значит и присваиваний. В данном случае произошло создание некоторого объекта с именем name, значение которого равно результату вычисления функции getLine. То есть, если после этого написать еще раз

name <- getLine

то создастся новый объект, имя которого перекроет предыдущий.

Таким образом выполняется извлечение результатов монадических функций. Для того чтобы задать подобным образом «переменные» значениями обыкновенных функций используется упрощенная нотация let:

let name = "John"

Ветвление вычислительного процесса осуществляется с помощью тех же if then else и case:

putStrLn "What is you name?"

name <- getLine

"GHC" -> putStrLn "No! I am GHC!"

_ -> putStrLn ("Hi, " ++ name ++ "!")

Если ветвление должно состоять из нескольких функций, то используется ключевое слово do:

putStrLn "What is you name?"

name <- getLine

putStrLn "No! I am GHC!"

_ -> putStrLn ("Hi, " ++ name ++ "!")

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

writeDigit x = do

putStr "Digits:"

mapM_ writeDigit

8 Примеры

Привести различные примеры (деревья поиска, AVL дерево, еще что-нибудь)

Заключение

Заключение

Список использованных источников

1 http://ru. wikibooks. org/wiki/Основы_функционального_программирования

2 http://www. *****/article/funcprog/fp. xml

3 Душкин программирование на языке Haskell – ДМК Пресс, 2007 – 608 с.

4 http://en. wikibooks. org/wiki/Haskell/Pattern_matching

5 http://www. haskell. org/tutorial/

Рефакторинге, 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 страниц.