Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м Шаблон со списком лекций
Нет описания правки
Строка 1:
{{ОФП Содержание}}
 
= Лекция 4. «Основы языка Haskell» =
 
Настоящая лекция будет полностью посвящена синтаксису языка [[w:Haskell|Haskell]] (далее, для удобства, «Хаскель»). Будут рассмотрены все важнейшие понятия языка, их соотношение с уже изученными понятиями (на основе абстрактного функционального языка). Также по возможности будут приводиться примеры на Lisp’е[[w:Лисп|Лиспе]], чтобы не отрываться от основ и традиции.
 
== Структуры данных и их типы ==
 
Одна из базовыхосновных единиц любого языка программирования — это символ. Символом традиционно называется последовательность букв, цифр и специальных знаков ограниченной или неограниченной длины. В некоторых языках строчные и прописные буквы различаются, в(к некоторыхним нет.относится ТакХаскель), в Lisp’е различия между строчными и заглавными букваминекоторых нет, а в Haskell’е есть(Лисп).
 
Символы чаще всего выступают в качествеявляются идентификаторовидентификаторами — именименами констант, переменных, функций. Значениями же констант, переменных и функций являются типизированные последовательности знаков. ТакПример: значением числовой константы не может быть строка из букв и т.п. В функциональных языках существует базовоеесть понятие — '''атом'''. В реализациях атомами называются символы и числа, причем числа могут быть трех видов: целые, с фиксированной и с плавающей точкой.
 
Следующим[[w:Список понятием(структура функциональногоданных)|Список]] программирования-- являетсяещё списокодно понятие функционального программирования. В абстрактной математической нотациизаписи использовались символыквадратные скобки [], которые также используются в Haskell’еХаскеле. Но в Lisp’еЛиспе используются обычные, «круглые» скобки — (). Элементы списка в Lisp’еЛиспе разделяются [[w:пробел|пробелами]], что не очень наглядно, поэтому в Haskell’еХаскеле было решено ввестиввели запятую для разделения. Таким образом, списокСписок [a, b, c] будет правильно записан в синтаксисе Haskell’аХаскеля, а в нотацию Lisp’аЛиспа его необходимо перевести как (a b c). ОднакоСоздатели создатели Lisp’аЛиспа пошли еще дальше в своей изощрённости.: Допускаетсядопускается использовать точечную запись для организации пары, поэтому приведенный выше список можно записать как (a.(b.(c.NIL))).
 
Списочные структуры в Lisp’еЛиспе и Haskell’еХаскеле описываются в соответствии с нотацией: — заключениезаключением одного списка в другой. При этом в нотации Lisp’аЛиспа сделано послабление, т.к. перед скобкой внутреннего списка можно не ставить пробел.
 
Как говорилось во [[Основы функционального программирования/Вводная лекция|вводной лекции]], типы данных в функциональных языках определяются автоматически. Механизм автоматического определения типа встроен и в Haskell.Хаскель, Однаконо в некоторых случаях необходимонужно явно указывать тип, иначе [[w:интерпретация|интерпретатор]] может запутаться в неоднозначности (в большинстве случаев будет выведено сообщение об ошибке или предупреждение). В Haskell’еХаскеле используется специальный символ — <code>::</code> (два двоеточия), котрый читается как «имеет тип». Т.е. если написать:
 
<code>5 :: Integer</code>
 
Это будет читаться как «Числовая константа 5 имеет тип Integer (Целое число)».
 
ОднакоЕщё HaskellХаскель поддерживает такую незаурядную вещь, как [[w:полиморфизм|полиморфные]] типы, или шаблоны типов. Если, например, записать <code>[a]</code>, то это будет обозначать тип «список из атомов любого типа», причем тип атомов должен быть одинаковымодин наво протяжениивсём всего списка. Т.есписке. спискиСписки <code>[1, 2, 3]</code> и <code>[‘a’, ‘b’, ‘c’]</code> будут иметь тип <code>[a]</code>, а список <code>[1, ‘a’]</code> будет другого типа. В этом случае в записи <code>[a]</code> символ a имеет значение типовой переменной.
 
== Соглашения по именованию ==
 
В Haskell’е оченьХаскеле важны соглашения по именованию, ибо они явно входят в синтаксис языка (чего обычно нет в императивных языках). Самое важное соглашение — использование заглавнойпрописной буквы в начале идентификатора. Имена типов, в том числе и определяемых разработчиком, должны начинаться с заглавнойпрописной буквы. Имена функций, переменных и констант должны начинаться со строчной буквы. В качестве первого символаначале идентификатора такжемогут возможноещё использованиебыть некоторыхнекоторые специальныхспециальные знаковзнаки, некоторые из которых такжемогут влияютвлиять на семантику идентификатора.<!-- Вместо того, чтобы говорить тут общими словами, лучше все подробности указать сразу -->
 
== Определители списков и математические последовательности ==
 
Пожалуй, HaskellХаскель — это- единственный язык программирования, который позволяетпозволяющий просто и быстро конструировать списки, основанные на какой-нибудь простой математической формуле. Этот подход уже был использован при построении функции быстрой сортировки списка методом Хоара (см. [[Основы_функционального_программирования/Вводная_лекция#Краткость и простота|пример 3 в лекции 1]]). Наиболее общий вид определителей списков выглядит так:
 
<code>[ x | x <- xs ]</code>
 
ЭтаЭто записьможно может быть прочитанапрочесть как «Список из всех таких x, взятых из xs». Структура «x  xs» называется '''генератором'''. После такого генератораГенератор (он должен быть один и стоять первым в записи определителя списка). После него может стоять некоторое числонесколько выражений охраны, разделённых запятыми. ВПри этом случае выбираются все такие x, значения всех выражений охраны на которых истинно. Т.е. запись:Запись
 
<code>[ x | x <- xs, x > m, x < n ]</code>
 
Можноможно прочитать какпрочесть «Список из всех таких x, взятых из xs, что (x больше m) И (x меньше n)».
 
ДругойВ важнойХаскеле особенностьюможно Haskell’аформировать является'''бесконечные''' простая возможность формирования бесконечных списковсписки и структурструктуры данных. Бесконечные списки можно формировать как на основе определителей списков, так иили сc помощью специальной нотации. НапримерВот, ниже показаннапример, бесконечный список, состоящий из последовательности [[w:натуральное число|натуральных чисел.]]: Второй<code>[1, список2 представляет..]</code>. бесконечнуюБесконечная последовательность [[w:чётность|нечётных]] натуральных чисел: <code>[1, 3 ..]</code>.
 
При помощи двух точек можно также определять любую [[w:арифметическая прогрессия|арифметическую прогрессию]], конечную или [[w:бесконечность|бесконечную]]. Для конечной задаются первый и последний элементы. Разность арифметической прогрессии вычисляется на основе первого и второго заданного элементов — в приведенных выше примерах разность в первой прогресси равна 1, а во второй — 2. Чтобы определить список всех нечётных натуральных чисел вплоть до 10, надо записать: <code>[1, 3 .. 10]</code>. Результатом будет список <code>[1, 3, 5, 7, 9]</code>.
[1, 2 ..]
[1, 3 ..]
 
Бесконечные структуры данных можно определять на основе бесконечных списков, а можно использовать механизм [[w:рекурсия|рекурсии]]. Рекурсия в этом случае используется как обращение к рекурсивным функциям. Третий способ создания бесконечных структур данных состоит в использовании бесконечных типов.
При помощи двух точек можно также определять любую арифметическую прогрессию, как конечную, так и бесконечную. Если последовательность конечна, то в ней задаются первый и последний элементы. Разность арифметической прогрессии вычисляется на основе первого и второго заданного элементов — в приведенных выше примерах разность в первой прогресси равна 1, а во второй — 2. Т.е. чтобы определить список всех нечётных натуральных чисел вплоть до 10, необходимо записать: [1, 3 .. 10]. Результатом будет список [1, 3, 5, 7, 9].
 
Бесконечные структуры данных можно определять на основе бесконечных списков, а можно использовать механизм рекурсии. Рекурсия в данном случае используется как обращение к рекурсивным функциям. Третий способ создания бесконечных структур данных состоит в использовании бесконечных типов.
 
'''Пример 11. Определение типа для представления двоичных деревьев.'''
 
<code>data Tree a = Leaf a
| Branch (Tree a) (Tree a)
 
Branch :: Tree a -> Tree a -> Tree a
Leaf :: a -> Tree a</code>
 
В этом примере показан способ определения бесконечного типа. Видно, что без рекурсии тут не обошлось. Однако еслиЕсли нет необходимости создавать новый тип данных, бесконечную структуру можно получить при помощичерез функцийфункции:
 
ones = 1 : ones
Строка 62 ⟶ 59 :
squares = map (^2) (numbersFrom 0)
 
Первая функция определяет бесконечную последовательность, полностью состоящую из [[w:1 (число)|единиц]]. Вторая функция возвращает последовательность целых чисел, начиная с заданного. Третья возвращает бесконечную последовательность квадратов натуральных чисел вместе с нулем.
 
== Вызовы функций ==
 
Математическая нотация вызова функции традиционно полагала заключение параметров вызова в скобки. Эту традицию впоследствии переняли практически все императивные языки. Однако вВ функциональных языках принята иная нотация —: имя функции отделяется от её параметров просто пробелом. В Lisp’еЛиспе вызов функции <code>length</code> с неким параметром L записывается в виде списка: <code>(length L)</code>. Такая нотация объясняется тем, что большинство функций в функциональных языках каррированны.
 
В Haskell’еХаскеле нет нужды обрамлять вызов функции в виде списка. Например, если определена функция, складывающая два числа:
 
add :: Integer -> Integer -> Integer
Строка 75 ⟶ 72 :
То ее вызов с конкретными параметрами (например, 5 и 7) будет выглядеть как:
 
<code>add 5 7</code>
 
Здесь видно, что нотация Haskell’аХаскеля наиболее сильно приближена к нотации абстрактного математического языка. Однако Haskellон пошел еще дальше Lisp’аЛиспа в этом вопросе, и в нем есть нотация для описания некаррированных функций, т.е. тип которых нельзя представить в виде A1  (A2  ... (An  B) ... ). И эта нотация, как и в императивных языках программирования, использует круглые скобки:
 
<code>add (x, y) = x + y</code>
 
Можно видеть, что последняя запись — это функция с одним аргументом в строгой нотациихаскельской Haskell’анотации. С другой стороны для каррированных функций вполне возможно делать частичное применение.; Т.е.что значит, при вызове функции двух аргументов передать ей только один. Как показано в предыдущей лекции результатом такого вызова будет также функция. Более чётко этот процесс можно поиллюстрироватьпоказать на примере функции <code>inc</code>, которая прибавляет единицу к заданному аргументу:
 
<code>inc :: Integer -> Integer</code>
<code>inc = add 1</code>
 
Т.е. в этом случае вызов функции <code>inc</code> с одним параметром просто приведет к вызову функции <code>add</code> с двумя, первый из которых — 1. Это интуитивное понимание понятия частичного применения. Для закрепления понимания можно рассмотреть классический пример —: функция <code>map</code> (её определение на абстрактном функциональном языке приведено во второй лекции). Вот определение функции <code>map</code> на Haskell’еХаскеле:
 
<code>map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = (f x) : (map f xs)</code>
 
Как видно, здесь использована инфиксная запись операции <code>prefix</code> — двоеточие, только такая запись используется в нотации Haskell’аХаскеля для обозначения или конструирования пары. После приведенного выше определения можно произвести следующий вызов:
<code>map (add 1) [1, 2, 3, 4]</code>
 
который даст список <code>[2, 3, 4, 5]</code>.
map (add 1) [1, 2, 3, 4]
 
Результатом которого будет список [2, 3, 4, 5].
 
== Использование λ-исчисления ==
 
Т.к. функциональнаяФункциональная парадигма программирования основана на [[w:λ-исчисление|λ-исчислении]], топоэтому вполне закономерно, что все функциональные языки поддерживают нотацию для описания λ-абстракций. Haskell не обошел стороной и этот аспект, если есть необходимость в определении какой-либо функции через λ-абстракцию. Кроме того,Ещё через λ-абстракции можно определять анонимные функции (например, для единичного вызова). Ниже показан пример, гдеопределения определены функциифункций <code>add</code> и <code>inc</code> именно при помощи λ-исчисления.
 
'''Пример 12. Функции add и inc, определённые через λ-абстракции.'''
<!-- Неплохо бы для примеров сделать заголовки. Пока отложу -->
 
<code>add = \x y -> x + y
inc = \x -> x + 1</code>
 
'''Пример 13. Вызов аномимной функции.'''
 
<code>cubes = map (\x -> x * x * x) [0 ..]</code>
 
Пример 13 показывает вызов анонимной функции, возводящей в куб переданный параметр. Результатом выполнения этой инструкции будет бесконечный список кубов целых чисел, начиная с нуля. Необходимо отметить, что в Haskell’еХаскеле используется упрощенный способ записи λ-выражений, т.к.; в точной нотации функцию add правильней было бы написать как:
 
<code>add = \x -> \y -> x + y</code>
 
Остаётся отметить, что тип λ-абстракции определяется абсолютноточно так же, как и тип функций. Тип λ-выражения вида <code>λx.expr</code> будет выглядеть как T1  T2, где T1 — это тип переменной x, а T2 — тип выражения <code>expr</code>.
 
== Инфиксный способ записи функций ==
 
Для некоторых функций возможен инфиксный способ записи,. такие функцииЭто обычно представляют собой простые бинарныедвоичные операции. Вот как, например, определены операции конкатенации списков и композиции функций:
 
'''Пример 14. Инфиксная операция конкатенации списков.'''
 
<code>(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)</code>
 
'''Пример 15. Инфиксная операция композиции функций.'''
 
<code>(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)</code>
 
Т.к.Покуда инфиксные операции всё-таки являются функциями в смысле Haskell’аХаскеля, т.е.то есть они каррированы, то имеет смысл обеспечить возможность частичного применения таких функций. Для этих целейтого имеется специальная запись, которая в Haskell’е носитХаскеле названиеназывается «секция»:
 
<code>(x ++) = \x -> (x ++ y)
(++ y) = \y -> (x ++ y)
(++) = \x y -> (x ++ y)</code>
 
Выше показаныЭто три секции, каждая из которых определяет инфиксную операцию конкатенации списков в соответствии с количеством переданных ей аргументов. Использование круглых скобок в записи секций является обязательнымобязательно.
 
Если какая-либо функция принимает два параметра, то её также можно записывать в инфиксной форме. Однако если просто записать между параметрами имя функции —, это будет ошибкой, т.к.ибо в строгой нотации Haskell’а,Хаскеля это будет просто двойным применением, причем в одном применении не будет хватать одного операнда. Для того чтобыЧтобы записать функцию в инфиксной форме, её имя необходимо заключить в символы обратного апострофа — [[w:`|`]].
 
Для вновь определённых инфиксных операций возможно определение порядка вычисления. Для этого в Haskell’еХаскеле есть зарезервированное слово <code>infixr</code>, которое назначает заданной операции степень её значимости (порядокприоритет выполнения)выполения в интервале от 0 до 9, при этом: 9 объявляется самой сильной степенью значимости (число. 10 также входит в этот интервал, и именно эту степень имеет операция применения). Вот так определяются степени для определенных в примерах 14 и 15 операций:
 
<code>infixr 5 ++
infixr 9 .</code>
 
В Хаскеле все функции являются нестрогими, что значит: все они поддерживают отложенные вычисления. Если какая-то функция определена как <code>bot = bot</code>, то её вызов даст ошибку, и такие ошибки обычно сложно отслеживать. Но если есть некая константная функция, которая определена как <code>constant_1 x = 1</code>, то при вызове конструкции <code>(constant_1 bot)</code> никакой ошибки не произойдёт, т.к. значение функции <code>bot</code> в этом случае не вычислялось бы (вычисления отложенные, значение вычисляется только тогда, когда оно действительно требуется). Результатом вычисления, естественно, будет <code>1</code>.
Остается отметить, что в Haskell’е все функции являются нестрогими, т.е. все они поддерживают отложенные вычисления. Например, если какая-то функция определена как:
 
== Упражнения ==
bot = bot
 
1. Сконструировать следующие конечные списки (N — количество элементов в конструируемом списке). Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
При вызове такой функции произойдет ошибка, и обычно такие ошибки сложно отслеживать. Но если есть некая константная функция, которая определена как:
*Список натуральных чисел. N = 20.
*Список нечётных натуральных чисел. N = 20.
*Список чётных натуральных чисел. N = 20.
*Список степеней двойки. N = 25.
*Список степеней тройки. N = 25.
*Список треугольных чисел [[w:Пьер Ферма|Ферма]]. N = 50.
*Список пирамидальных чисел Ферма. N = 50.
 
2. Сконструировать следующие бесконечные списки. Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
constant_1 x = 1
*Список факториалов.
*Список квадратов натуральных чисел.
*Список кубов натуральных чисел.
*Список степеней пятёрки.
*Список вторых суперстепеней натуральных чисел.
 
То при вызове конструкции (constant_1 bot) никакой ошибки не произойдёт, т.к. значение функции bot в этом случае не вычислялось бы (вычисления отложенные, значение вычисляется только тогда, когда оно действительно требуется). Результатом вычисления естественно будет число 1.
 
=== УпражненияОтветы ===
 
1. Конечные списки конструируются либо при помощи ограничений, вставляемых в генератор списка, либо при помощи дополнительных ограничивающих параметров.
#Сконструировать следующие конечные списки (N — количество элементов в конструируемом списке). Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
*<code>[1 .. 20]</code>
#*Список натуральных чисел. N = 20.
*<code>[1, 3 .. 40]</code> или <code>[1, 3 .. 39]</code>
#*Список нечётных натуральных чисел. N = 20.
*<code>[2, 4 .. 40]</code>
#*Список чётных натуральных чисел. N = 20.
#*Список степеней двойки. Nпроще =всего 25.сконструировать при помощи функции (здесь <code>reverse</code> — функция обращения списка):
<code>powerTwo 0 = []
#*Список степеней тройки. N = 25.
#*Список треугольных чисел Ферма. N = 50.
#*Список пирамидальных чисел Ферма. N = 50.
#Сконструировать следующие бесконечные списки. Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
#*Список факториалов.
#*Список квадратов натуральных чисел.
#*Список кубов натуральных чисел.
#*Список степеней пятёрки.
#*Список вторых суперстепеней натуральных чисел.
 
== Ответы для самопроверки ==
 
#Конечные списки конструируются либо при помощи ограничений, вставляемых в генератор списка, либо при помощи дополнительных ограничивающих параметров.
#*[1 .. 20]
#*[1, 3 .. 40] или [1, 3 .. 39]
#*[2, 4 .. 40]
#*Список степеней двойки проще всего сконструировать при помощи функции (здесь reverse — функция обращения списка):
 
powerTwo 0 = []
powerTwo n = (2 ^ n) : powerTwo (n – 1)
reverse (powerTwo 25)</code>
 
*:Список степеней тройки проще всего сконструировать при помощи функции (здесь reverse — функция обращения списка):
reverse (powerTwo 25)
<code>powerThree 0 = []
 
#*Список степеней тройки проще всего сконструировать при помощи функции (здесь reverse — функция обращения списка):
 
powerThree 0 = []
powerThree n = (2 ^ n) : powerThree (n – 1)
reverse (powerThree 25)</code>
 
*В отличие от предыдущих двух упражнений, здесь можно воспользоваться функцией map, применяющей заданную функцию ко всем элементам списка:
reverse (powerThree 25)
<code>t_Fermat 1 = 1
 
#*В отличие от предыдущих двух упражнений, здесь можно воспользоваться функцией map, применяющей заданную функцию ко всем элементам списка:
 
t_Fermat 1 = 1
t_Fermat n = n + t_Fermat (n – 1)
map t_Fermat [1 .. 50]</code>
 
*Конструирование списка из 50 пирамидальных чисел Ферма также основывается на использовании функции <code>map</code>:
map t_Fermat [1 .. 50]
<code>p_Fermat 1 = 1
 
#*Конструирование списка из 50 пирамидальных чисел Ферма также основывается на использовании функции map:
 
p_Fermat 1 = 1
p_Fermat n = t_Fermat n + p_Fermat (n – 1)
map p_Fermat [1 .. 50]</code>
 
2.Бесконечные списки конструируются либо при помощи неограниченных генераторов, либо при помощи конструирующих функций без ограничивающих параметров.
map p_Fermat [1 .. 50]
*Бесконечный список факториалов:
 
<code>numbersFrom n = n : numbersFrom (n + 1)
#Бесконечные списки конструируются либо при помощи неограниченных генераторов, либо при помощи конструирующих функций без ограничивающих параметров.
#*Бесконечный список факториалов:
 
numbersFrom n = n : numbersFrom (n + 1)
 
factorial n = f_a n 1
Строка 218 ⟶ 196 :
f_a n m = f_a (n – 1) (n * m)
 
map factorial (numbersFrom 1)</code>
*Бесконечный список квадратов натуральных чисел:
<code>square n = n * n
 
map square (numbersFrom 1)</code>
#*Бесконечный список квадратов натуральных чисел:
*Бесконечный список кубов натуральных чисел:
<code>cube n = n ^ 3
 
map cube (numbersFrom 1)</code>
square n = n * n
*Бесконечный список степеней пятёрки:
<code>powerFive n = 5 ^ n
 
map squarepowerFive (numbersFrom 1)</code>
*Бесконечный список вторых суперстепеней натуральных чисел:
 
<code>superPower n 0 = n
#*Бесконечный список кубов натуральных чисел:
 
cube n = n ^ 3
 
map cube (numbersFrom 1)
 
#*Бесконечный список степеней пятёрки:
 
powerFive n = 5 ^ n
 
map powerFive (numbersFrom 1)
 
#*Бесконечный список вторых суперстепеней натуральных чисел:
 
superPower n 0 = n
superPower n p = (superPower n (p – 1)) ^ n
 
secondSuperPower n = superPower n 2
map secondSuperPower (numbersFrom 1)</code>
 
map secondSuperPower (numbersFrom 1)
Источник — https://ru.wikibooks.org/wiki/Основы_функционального_программирования/Основы_языка_Haskell