Математическое введение в декларативное программирование. Зюзысов В.М. - 72 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

невозможным, чтобы преобразовать все программы в функциональный стиль. В общем (и
традиционно) императивные языки имеют следующие ограничения:
• структурные величины, такие как массивы и записи, не могут быть результатами вы-
зовов функций;
• нет способа построить величину структурного типа прямо;
• функции не являются данными, так что нет функций высокого порядка.
Каждая величина в функциональном языке имеет связанный (ассоциированный)
тип. Интуитивно, мы можем рассматривать типы как множества допустимых значений,
которые может иметь величина. Вообще говоря, типы могут явно или неявно присутство-
вать в языке. Точно так же, как выражения обозначают величины, типовые выражения –
синтаксические термы, которые обозначают типовые величины (или просто типы). При-
меры выражений типа включают атомарные типы
Integer
(целые бесконечной точности),
Char (символы), Integer->Integer (функции с областью определения и областью значе-
ний Integer
), а также структурные типы
[Integer]
(однородные списки целых чисел) и
(Char,Integer) (пары символ, целое число).
Типы в некотором смысле описывают величины и ассоциация типов с величинами
называется типизированием. Используя примеры типов, приведенных ранее, мы можем
записать типизирование следующим образом:
5 :: Integer
'a' :: Char
inc :: Integer -> Integer
[1,2,3] :: [Integer]
('b',4) :: (Char,Integer)
Лексема «::
» может быть прочитана как «имеет тип».
Функции в Haskell нормально определяются последовательностью уравнений. На-
пример, функция inc
может определяться одним уравнением (первая строка задает опре-
деление типа функции – она может отсутствовать):
inc :: Integer -> Integer
inc n = n+1
Вышеприведенное определение функции gcd
содержит три уравнения. Суперпози-
ция функций, которая в математике записывается как f (g (x)), на языке Haskell представ-
ляется в виде выражения f g x. Вызов математической функции с несколькими аргумен-
тами, например f(x,y+x,5) в языке выглядит как f x (y+x) 5.
Как пример определенной пользователем функции, что действует на списках, рас-
смотрим задачу подсчета количества элементов в списке:
length :: [a] -> Integer
length [] = 0
length (x:xs) = 1 + length xs
Некоторые разъяснения: конструктор «:» позволяет создавать списки, добавляя
элемент в начало списка (в данном случае x – первый элемент списка, xs – остальные эле-
менты); [] обозначает пустой список. Определение типа функции
length говорит, что
функция является полиморфной: список содержит элементы любого типа a.
Мы можем прочитать уравнения словами: «длина пустого списка равна нулю, а
длина списка, чей первый элемент –
x
и хвост (остальные элементы) есть
xs
, равна 1 плюс
длина
xs
».
Функциональное применение (аппликация) имеет наивысший приоритет среди
операций, поэтому 1 + length xs понимается синтаксически как 1 + (length xs). В
72

Страницы