Функциональное программирование на Haskell: Часть 2.Основные типы и классы

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

Алексей Бешенов, технический писатель, независимый специалист

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



25.02.2010

Основные типы

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

Если выражение e имеет тип T, то мы пишем e :: T. Это называется описанием типа или сигнатурой. :: читается «имеет тип».

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

Вы можете включить вывод типов командой :set +t:

 ghci> :set +t
 ghci> True || False
 True
 it :: Bool

Такое поведение отключается по команде :unset +t.

Строгая статическая типизация избавляет от существенной части ошибок в программах.

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

В ghci тип значения можно узнать при помощи :type:

ghci> :type True
True :: Bool
ghci> :type 'a'
'a' :: Char
ghci> :type 23 < 529
23 < 529 :: Bool

Здесь мы рассмотрим основные типы и средства их комбинирования.

Единичный тип

Самый простой тип – единичный. Он записывается в виде () и содержит единственное значение ().

ghci> :type ()
() :: ()

Он похож на void в языках вроде C и Java.

Булевы значения

Тип Bool состоит из значений False и True. С ними можно манипулировать при помощи операторов & и ||, а также функции not.

ghci> True || False
True
ghci> True & False
False
ghci> not True
False

Символы

Тип Char соответствует множеству символов Unicode. Значения записываются в одинарных кавычках: 'a', 'b', 'c'.

Как и в других языках, для ввода специальных символов можно использовать экранирование: '\'' (кавычка), '\n' (перевод строки), '\t' (табуляция). Подробности см. в Haskell 98 Report.

Числа

Для чисел имеются следующие базовые типы:

  • Int – целое число фиксированной точности (минимум 29 битов).
  • Integer – целое число произвольной точности.
  • Float – число с плавающей точкой одинарной точности.
  • Double – число с плавающей точкой двойной точности.

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

Операции с плавающей точкой оптимизированы для Double; использовать Float в целях экономии нет смысла.


Кортежи

Кортежем называют последовательность компонентов фиксированной длины.

Компоненты перечисляются через запятую в круглых скобках: (1,'a'), (23,"bob",23), и т. д. Тип кортежа с компонентами типов T1, …, Tn записывается как (T1, …, Tn).

Разное количество компонентов и их типы дают разные, не совместимые типы кортежей.

Кортежи с двумя компонентами называются парами, с тремя – тройками, и т. д. Кортежей из одного компонента нет; пустой кортеж (), как мы уже знаем, имеет единичный тип.

Для пар в Prelude определены проекторы, возвращающие первый и второй компоненты:

fst (x,y) = x
snd (x,y) = y

Имейте в виду, что в Haskell запись вида fst (x,y) означает применение функции к одному аргументу-паре.


Функции

Функция типа f :: X -> Y сопоставляет элементам e типа X элементы f e типа Y.

Перед тем как определять функцию, желательно указать ее тип.

Тип может быть выведен автоматически, но он может оказаться более общим, чем предполагаемый, либо вообще не тем – это значит, что вы в чём-то ошиблись. Система сверяет ваши типы с выведенными.

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

square :: Double -> Double
square x = x*x

Тип аргумента должен совпадать с типом, указанным при объявлении функции (или выведенным). Это составляет основу выведения типов: если f :: X → Y и e :: X, то f e :: Y.

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

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

f' :: (X,Y) -> Z

Более распространенный в Haskell подход называется (в честь Хаскелла Карри) каррированием. Функцию n аргументов можно представить в виде функции, принимающей 1-й аргумент и возвращающей функцию, которая принимает 2-й аргумент и т. д. Окончательно, n-я функция будет принимать n-й аргумент и вычислять результат.

Для двух аргументов тип записывается в виде

f :: X -> (Y -> Z)

Неформально, f принимает два аргумента типа X и Y. Применение f к значениям a и b происходит в два этапа:

  • Если a :: X, то f a :: Y -> Z.
  • Если b :: Y, то (f a) b :: Z.

Промежуточное выражение f a называется частичным применением.

  • Применение функции левоассоциативно: запись f a b эквивалентна (f a) b.
  • Оператор -> правоассоциативен: тип f :: X -> Y -> Z интерпретируется как f :: X -> (Y -> Z).

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

hyp :: Double -> Double -> Double
hyp x y = sqrt (square x + square y)

hyp' :: (Double, Double) -> Double
hyp' (x,y) = sqrt (square x + square y)

В первом случае мы не выписываем в явном виде, что hyp зависит только от x, но возвращает другую функцию, зависящую от y. Функции каррируются по умолчанию.

Существенной разницы между hyp' (x,y) и hyp x y нет, но последний вариант выглядит проще и допускает частичное применение.

Если записать hyp x, то, как следует из определения каррирования, это будет функция типа Double -> Double.

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

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

Переход между функцией (a,b) -> c и a -> b -> c, где a, b, c – некоторые типы, можно выразить специальными функциями:

curry f x y     = f (x,y)
uncurry f (x,y) = f x y

curry и uncurry достаточно применить к одному аргументу, а именно к функции (a,b) -> c или a -> b -> c, и мы получим функцию, принимающую два аргумента через каррирование, либо в виде пары.

ghci> hyp 3 4
5.0
ghci> hyp' (3,4)
5.0
ghci> (uncurry hyp) (3,4)
5.0
ghci> (curry hyp') 3 4
5.0

Все эти соображения естественно переносятся на каррирование функций трех, четырех аргументов и т. д. (Но curry и uncurry определены в Prelude для функций двух аргументов.)

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

Композиция

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

(f.g) x = f (g x)

Запись f.g напоминает математическое обозначение f∘g.

Функции должны иметь подходящие типы. Если g :: X -> Y и f :: Y -> Z, то (f.g) :: X -> Z.

Обратите внимание: если записано (f.g), то сначала к аргументу применяется g, а затем к результату применяется f, не наоборот.

В Prelude имеется тождественное отображение:

id x = x
(f.id) = f и (id.g) = g, где id :: Y -> Y.

Все это можно изобразить на диаграмме (рисунок 1), где стрелка от X к Y обозначает функцию X → Y.

Рисунок 1. Функции g :: X -> Y, f :: Y -> Z, (f.g) :: X -> Z, id :: Y -> Y.
Рисунок 1. Функции g :: X -> Y, f :: Y -> Z, (f.g) :: X -> Z, id :: Y -> Y.

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

fourth :: Double -> Double
fourth x = square (square x)

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

fourth x = (square . square) x

Но (square . square) и есть интересующая нас функция:

ghci> (square . square) 2
16

Поэтому лучше использовать определение

fourth = square . square

Если мы хотим фиксировать первый аргумент функции f, то можно записать:

g x = f a x

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

g = f a

Это называется бесточечной записью (point-free). Под точками здесь понимаются аргументы x, y, z, … (по аналогии с точками пространства), а не оператор ..

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

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

Функции могут быть анонимными. Для них используется запись вида

\ x y -> sqrt (x*x + y*y)

Здесь \ – символ, похожий на греческую букву λ. После него перечисляются аргументы. -> обозначает отображение.

Считается, что выражение после -> простирается как можно дальше, так что если анонимную функцию нужно вставить в другое выражение, то ее запись берется в скобки:

… (\ x y -> sqrt (x*x + y*y)) …

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

\ x -> (\ y -> sqrt (x*x + y*y))

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

ghci> (\ x y -> sqrt (x^2 + y^2)) 3 4
5.0

Операторы и функции

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

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

ЗаписьЗначение
(+)(\ x y -> x+y)
(x+)\ y -> x+y
(+y)\ x -> x+y

Таблица 1. Сечения инфиксного оператора на примере +

ghci> (+) 2 3
5
ghci> (2+) 3
5
ghci> (+3) 2
5

Это порождает некоторую путаницу с инфиксным минусом. Запись вроде (-23) – это число, а не функция (\ x -> x - 23). При необходимости используйте предопределенные subtract и negate:

subtract x y =  x - y
negate   x   = -x

Помните, что запись f -23 обозначает разность; применение функции должно записываться со скобками: f (-23).

Кроме того, имеется возможность использовать имя функции как инфиксный оператор; для этого нужно взять имя в обратные кавычки: x `f` y – это то же самое, что и f x y.

Но этим не стоит злоупотреблять.

Оператор $

Применение функции имеет самый высокий приоритет. Так, f x + g x обозначает (f x) + (g x).

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

Особенности оператора $:

  • ($) можно использовать как функцию, которая принимает первый аргумент ко второму.
  • Благодаря низкому приоритету, f $ x + g x обозначает f (x + g x).
  • Благодаря правоассоциативности, f $ g $ h x обозначает f (g (h x)).

Главным образом, $ позволяет писать меньше скобок.


Списки

Список – это последовательность элементов одного типа. Если тип элементов — T, то тип списка обозначается в виде [T].

Список имеет рекурсивную структуру:

  • Списком является пустой список [].
  • Списком является x : xs, где x :: T – голова, xs :: [T] – хвост.

Голова присоединяется в начало к хвосту конструктором списка (:).

Пусть нужно построить список из целых чисел 1, 2, 3 (рисунок 2). Он будет иметь тип [Int]. Нужно начать с пустого списка []. Далее к нему присоединяются значения по одному:

ghci> 3 : []
[3]
ghci> 2 : it
[2,3]
ghci> 1 : it
[1,2,3]

[1,2,3] – это краткая запись для 1 : (2 : (3 : [])). Конструктор : правоассоциативен, можно писать просто 1 : 2 : 3 : [].

Рисунок 2. Дерево списка [1,2,3].
Рисунок 2. Дерево списка [1,2,3].

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

nullПроверка на пустой списокghci> null []
True
headВыбор головы в непустом спискеghci> head [1,2,3]
1
tailВыбор хвоста в непустом спискеtail [1,2,3]
[2,3]
lengthКоличество элементовghci> length [1,2,3]
3
(!!)Доступ по индексу (элементы нумеруются с 0) ghci> [1,2,3] !! 1
2
takeВыбор первых n элементовghci> take 2 [1,2,3]
[1,2]
dropУдаление первых n элементовghci> drop 2 [1,2,3]
[3]
(++)Объединение двух списковghci> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
concatОбъединение списка списковghci> concat
[[1,2],[3,4],[5,6]]
[1,2,3,5,6]
reverseОбращениеghci> reverse [1,2,3]
[3,2,1]
sumСумма элементовghci> sum [1,2,3,4]
10
productПроизведение элементовghci> product [1,2,3,4]
24
zipОбъединение двух списков в список парghci> zip ['a','b','c']
[1,2,3]
[('a',1),('b',2),('c',3)]

Таблица 2. Основные функции для работы со списками

Строки

Тип строк String соответствует списку символов [Char]. Строковые значения, как и в других языках, можно записывать в двойных кавычках: "abc", но это просто удобное сокращение для ['a','b','c']. Пустая строка – ".

ghci> "Bob"++" "++"Dobbs"
"Bob Dobbs"
ghci> concat ["Bob", " ", "Dobbs"]
"Bob Dobbs"
ghci> reverse "Bob Dobbs"
"sbboD boB"

Полиморфизм

Выше упоминались функции, действующие для разных типов. Например, аргумент curry может иметь тип (Int,Int)->Int, (Int,Char)->String, и т.д.

Чтобы отразить это, тип curry описывается с использованием ти́повых переменных:

curry :: ((a, b) -> c) -> a -> b -> c

Ти́повые переменные, в отличие от самих типов, записываются со строчной буквы. Для них принято использовать короткие имена, чаще однобуквенные.

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

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

Теперь можно посмотреть на типы уже упомянутых функций:

ghci> :type id
id :: a -> a
ghci> :type fst
fst :: (a, b) -> a
ghci> :type (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
ghci> :type zip
zip :: [a] -> [b] -> [(a, b)]

Частичные функции

Функции не обязаны быть полными. Выражение, которое не вычисляется успешно (вызывает ошибку или зацикливается), обозначается ⊥. Считается, что элемент ⊥ содержится в любом типе, поэтому он называется дном (bottom).

В Prelude есть функция error :: String -> a для выдачи сообщения об ошибке и полиморфное неопределенное значение undefined :: a.

ghci> error "Something wrong"
*** Exception: Something wrong
ghci> undefined
*** Exception: Prelude.undefined

Классы типов

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

ghci> :type (+)
(+) :: (Num a) => a -> a -> a
ghci> :type (/)
(/) :: (Fractional a) => a -> a -> a

Здесь a, как и прежде, означает переменную типа. Но (C a) => в сигнатуре – ограничение на класс, означающее, что a должно принадлежать классу C.

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

Числа также перегружены. Например, 23 можно рассматривать и как целое число, и как число с плавающей точкой:

ghci> :type 23
23 :: (Num t) => t

Перечислим основные классы, которые можно найти в Prelude.

Eq

Eq – класс типов, в которых значения можно проверять на равенство и неравенство.

Представители:Bool, Char, Double, Float, Int, Integer; кортежи и списки элементов, чей тип принадлежит Eq.

Методы: (==) :: a -> a -> Bool и (/=) :: a -> a -> Bool.

Как и прежде, (==) и (/=) могут использоваться в качестве инфиксных операторов == и /=.

ghci> True /= True
False
ghci> (1,2,3) == (1,1+1,1+1+1)
True

(Не путайте /= с оператором != в других языках.)

Ord

Ord – класс типов, в которых значения линейно упорядочены (для любых x и y имеем x ≤ y или y ≤ x).

Представители: Bool, Char, Double, Float, Int, Integer; кортежи и списки элементов, чей тип принадлежит Ord (они сравниваются лексикографически).

Методы:

  • Функции сравнения с типом a -> a -> Bool: (<), (>=), (>), (<=)
  • >min :: a -> a -> a и max :: a -> a -> a.
ghci> "Bob" < "Dobbs"
True
ghci> min "Bob" "Dobbs"
"Bob"

Enum

Enum – класс последовательностей.

Представители: (), Bool, Char, Double, Float, Int, Integer.

Методы:

  • Все элементы последовательностей занумерованы, начиная с 0. По элементу можно получить порядковый номер, а по порядковому номеру – элемент:
    toEnum :: Int -> a, fromEnum :: a -> Int
  • Если элемент не 0-й, то для него имеется предшествующий; если элемент не последний, то для него имеется последующий:
    pred :: a -> a, succ :: a -> a
ghci> fromEnum 'c'
99
ghci> toEnum 99 :: Char
'c'
ghci> pred 'b'
'a'
ghci> succ 'b'
'c'

Обратите внимание: toEnum – полиморфная функция с типом Int -> a, и из выражения toEnum 99 невозможно установить тип, поэтому мы явно указываем toEnum 99 :: Char.

Num

Num – класс чисел.

Представители:Double, Float, Int, Integral.

Методы:

  • Противоположное число, абсолютное значение, знак (тип a -> a -> a):
    negate, abs, signum
  • Сложение, умножение, вычитание (тип a -> a -> a):
    (+), (*), (-)
  • Преобразование из целого числа: fromInteger :: Integer -> a
ghci> [signum (-23), signum 0, signum 23]
[-1,0,1]
ghci> abs (-23)
23
ghci> negate 23
-23
ghci> [23 + 23, 23 * 23, 23 - 23]
[46,529,0]

Integral

Integral – класс целых чисел.

Представители: Int, Integral.

Методы:

  • Целочисленное деление с округлением к 0: quot :: a -> a -> a
  • Остаток от деления quot: rem :: a -> a -> a
  • Целочисленное деление с округлением к −∞: div :: a -> a -> a
  • Остаток от деления div: mod :: a -> a -> a
  • Пара чисел (частное, остаток): quotRem :: a -> a -> (a, a), divMod :: a -> a -> (a, a)
  • Преобразование в целое число типа Integer: toInteger :: a -> Integer
ghci> quotRem (-23) 3
(-7,-2)
ghci> divMod (-23) 3
(-8,1)

Важная функция:

fromIntegral :: (Integral a, Num b) => a -> b
fromIntegral = fromInteger . toInteger

Пример использования:

ghci> let mean xs = sum xs / (fromIntegral.length) xs
ghci> mean [1,2,3,4,5]
3.0

Fractional

Fractional – класс дробных чисел.

Представители: Double, Float.

Методы: (/) :: a -> a -> a и recip :: a -> a

ghci> 3 / 2
1.5
ghci> recip 3
0.3333333333333333

Floating

Floating – класс чисел с плавающей точкой.

Представители: Double, Float.

Методы:

  • Квадратный корень sqrt :: a -> a
  • Возведение в степень (**) :: a -> a -> a
  • Число π = 3.1415926…: pi :: a
  • Экспонента exp :: a -> a и натуральный логарифм log :: a -> a
  • Логарифм по данному основанию logBase :: a -> a -> a
  • Тригонометрические функции типа a -> a: sin, tan, cos, asin, atan, acos, sinh, tanh, cosh, asinh, atanh, acosh.
ghci> exp 1
2.718281828459045
ghci> logBase 2 64
6.0
ghci> sqrt 2
1.4142135623730951
ghci> sin $ pi/2
1.0
ghci> 1.99 ** 3.99
15.574846491761065

Show

Основной интересующий нас метод класса Show – show :: a -> String – используется для вывода значений типа a:

ghci> show 23
"23"
ghci> show [1,2,3]
"[1,2,3]"

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

ghci> (+) 1

<interactive>:1:0:
    No instance for (Show (t -> t))
      arising from a use of `print' at <interactive>:1:0-4
    Possible fix: add an instance declaration for (Show (t -> t))
    In a stmt of a 'do' expression: print it

Read

Для класса Read нас будет интересовать функция read :: (Read a) => String -> a, по сути противоположная show.

ghci> read "23" :: Integer
23
ghci> read "[('a',23)]" :: [(Char,Integer)]
[('a',23)]

Заключение

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

Рассмотренные классы образуют иерархию (рисунок 3).

Рисунок 3. Иерархия классов
Рисунок 3. Иерархия классов

Интересные ресурсы для самостоятельного изучения:

  • Библиотека Prelude: http://haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html (EN) (Для начала изучите набор функций и их типы.)
  • Hoogle – Web-приложение для поиска функций в стандартных библиотеках, в том числе по сигнатуре: http://haskell.org/hoogle/.
  • Команда :info выводит информацию о данном имени. Попробуйте применить ее к функциям, типам, методам и классам.

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

Прилагаемые файлы:fph02.lhs

Ресурсы

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


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

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



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

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


  • Bluemix

    Узнайте больше информации о платформе IBM Bluemix, создавайте приложения, используя готовые решения!

  • developerWorks Premium

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

  • Библиотека документов

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=469798
ArticleTitle=Функциональное программирование на Haskell: Часть 2.Основные типы и классы
publish-date=02252010