Викиучебник

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

Интерактивная навигация по истории
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
Нет описания правки
Строка 1:
{{ОФП Содержание}}
 
Настоящая лекция будет полностью посвящена синтаксису языка [[w:Haskell|Haskell]] (далее, для удобства, «ХаскельХаскел»). Будут рассмотрены все важнейшие понятия языка, их соотношение с уже́ изученными понятиями (на основе абстрактного функционального языка). Также по возможности будут приводиться примеры на [[w:Лисп|Лиспе]], чтобы не отрываться от основ и традиции.▼
= Лекция 4. Основы языка Haskell =
 
▲Настоящая лекция будет полностью посвящена синтаксису языка [[w:Haskell|Haskell]] (далее, для удобства, «Хаскель»). Будут рассмотрены все важнейшие понятия языка, их соотношение с уже изученными понятиями (на основе абстрактного функционального языка). Также по возможности будут приводиться примеры на [[w:Лисп|Лиспе]], чтобы не отрываться от основ и традиции.
 
== Структуры данных и их типы ==
 
Одна из основных единиц любого языка программирования — это символ. Символом традиционно называется последовательность букв, цифр и специальных знаков ограниченной или неограниченной длины. В некоторых языках строчные и прописные буквы различаются (к ним относится ХаскельХаскел), в некоторых нет (Лисп).
 
Символы чаще всего являются идентификаторами — именами констант, переменных, функций. Значениями же констант, переменных и функций являются типизированные последовательности знаков. Пример: значением числовой константы не может быть строка из букв. В функциональных языках есть понятие '''атом'''. В реализациях атомами называются символы и числачи́сла, причемпричём числачи́сла могут быть трехтрёх видов: целые, с фиксированной и с плавающей точкой.
 
[[w:Список (структура данных)|Список]] --— ещё одно понятие функционального программирования. В абстрактной математической записи использовались квадратные скобки <code>[]</code>, которые также используются в Хаскеле. Но в Лиспе используются обычные, круглые скобки <code>()</code>. Элементы списка в Лиспе разделяются [[w:пробел|пробелами]], что не очень наглядно, поэтому в Хаскеле ввели запятую для разделения. Список <code>[a, b, c]</code> будет правильно записан в синтаксисе ХаскеляХаскела, а в нотацию Лиспа его необходимо перевести как <code>(a b c)</code>. Создатели Лиспа пошли ещеещё дальше в своей изощрённости: допускается использовать точечную запись для организации пары, поэтому приведенныйприведённый выше список можно записать как <code>(a.(b.(c.NIL)))</code>.
 
Списочные структуры в Лиспе и Хаскеле описываются в соответствии с нотацией: заключением одного списка в другой. При этом в нотации Лиспа сделано послабление, т.&nbsp;к. перед скобкой внутреннего списка можно не ставить пробел.
 
Как говорилось во '''[[Основы функционального программирования/Вводная лекция|вводной лекции]]''', типы данных в функциональных языках определяются автоматически. Механизм автоматического определения встроен и в ХаскельХаскел, но в некоторых случаях нужно явно указывать тип, иначе [[w:интерпретация|интерпретатор]] может запутаться в неоднозначности. В Хаскеле используется специальный символ <code>::</code> (два двоеточия), котрый читается как «имеет тип». Т.&nbsp;е. если написать:
 
<code>5 :: Integer</code>
 
Это будет читаться как «Числовая константа <code>5</code> имеет тип Целое число».
 
Ещё ХаскельХаскел поддерживает [[w:полиморфизм|полиморфные]] типы, или шаблоны типов. Если, например, записать <code>[a]</code>, то это будет обозначать тип «список из атомов любого типа», причем тип атомов должен быть один во всём списке. Списки <code>[1, 2, 3]</code> и <code>[‘a’, ‘b’, ‘c’]</code> будут иметь тип <code>[a]</code>, а список <code>[1, ‘a’]</code> будет другого типа. В этом случае в записи <code>[a]</code> символ <code>a</code> имеет значение типовой переменной.
 
== Соглашения по именованию ==
Строка 29 ⟶ 27 :
== Определители списков и математические последовательности ==
 
Пожалуй, ХаскельХаскел -— единственный язык программирования, позволяющий просто и быстро конструировать списки, основанные на какой-нибудь простой математической формуле. Этот подход уже&#769; был использован при построении функции быстрой сортировки списка методом Хоара (см. '''[[Основы_функционального_программирования/Вводная_лекция#Краткость и простота|пример 3]]''' в '''[[Основы_функционального_программирования/Вводная_лекция|лекции 1]]'''). Наиболее общий вид определителей списков выглядит так:
 
<code>[ x | x <- xs ]</code>
 
Это можно прочесть как «Список из всех таких <code>x</code>, взятых из <code>xs</code>». Структура «<code>x <- xs</code>» называется '''генератором'''. Генератор он должен быть один и стоять первым в записи определителя списка. После него может стоять несколько выражений охраны, разделённых запятыми. При этом выбираются все такие <code>x</code>, значения всех выражений охраны на которых истинно. Запись
 
<code>[ x | x <- xs, x > m, x < n ]</code>
 
можно прочесть «Список из всех таких <code>x</code>, взятых из <code>xs</code>, что <code>x</code> больше <code>m</code> '''И''' <code>x</code> меньше <code>n</code>».
 
В Хаскеле можно формировать '''бесконечные''' списки и структуры данных. Бесконечные списки можно формировать на основе определителей списков или c помощью специальной нотации. Вот, например, бесконечный список, состоящий из последовательности [[w:натуральное число|натуральных чисел]]: <code>[1, 2 ..]</code>. Бесконечная последовательность [[w:чётность|нечётных]] натуральных чисел: <code>[1, 3 ..]</code>.
 
При помощи двух точек можно также определять любую [[w:арифметическая прогрессия|арифметическую прогрессию]], конечную или [[w:бесконечность|бесконечную]]. Для конечной задаются первый и последний элементы. Разность арифметической прогрессии вычисляется на основе первого и второго заданного элементов — в приведенныхприведённых выше примерах разность в первой прогресси равна 1, а во второй — 2. Чтобы определить список всех нечётных натуральных чисел вплоть до <code>10</code>, надо записать: <code>[1, 3 .. 10]</code>. Результатом будет список <code>[1, 3, 5, 7, 9]</code>.
 
Бесконечные структуры данных можно определять на основе бесконечных списков, а можно использовать механизм [[w:рекурсия|рекурсии]]. Рекурсия в этом случае используется как обращение к рекурсивным функциям. Третий способ создания бесконечных структур данных состоит в использовании бесконечных типов.
 
'''Пример 11. Определение типа для представления двоичных деревьев.'''
 
<code>data Tree a = Leaf a
| Branch (Tree a) (Tree a)
 
Branch :: Tree a -> Tree a -> Tree a
Leaf :: a -> Tree a</code>
Строка 55 ⟶ 53 :
В этом примере показан способ определения бесконечного типа. Видно, что без рекурсии тут не обошлось. Если нет необходимости создавать новый тип данных, бесконечную структуру можно получить через функции:
 
<code>ones = 1 : ones
numbersFrom n = n : numberFrom (n + 1)
squares = map (^2) (numbersFrom 0)</code>
 
Первая функция определяет бесконечную последовательность, полностью состоящую из [[w:1 (число)|единиц]]. Вторая функция возвращает последовательность целых чисел, начиная с заданного. Третья возвращает бесконечную последовательность квадратов натуральных чисел вместе с нулемнулём.
 
== Вызовы функций ==
 
Математическая нотация вызова функции традиционно полагала заключение параметров вызова в скобки. Эту традицию впоследствии переняли практически все императивные языки. В функциональных языках принята иная нотация: имя функции отделяется от её параметров просто пробелом. В Лиспе вызов функции <code>length</code> с неким параметром <code>L</code> записывается в виде списка: <code>(length L)</code>. Такая нотация объясняется тем, что большинство функций в функциональных языках каррированны.
 
В Хаскеле нет нужды обрамлять вызов функции в виде списка. Например, если определена функция, складывающая два числа:
 
<code>add :: Integer -> Integer -> Integer
add x y = x + y</code>
 
То еееё вызов с конкретными параметрами (например, <code>5</code> и <code>7</code>) будет выглядеть как:
 
<code>add 5 7</code>
 
Здесь видно, что нотация ХаскеляХаскела наиболее сильно приближена к нотации абстрактного математического языка. Однако он пошел ещеещё дальше Лиспа в этом вопросе, и в немнём есть нотация для описания некаррированных функций, т.&nbsp;е. тип которых нельзя представить в виде A1<math>A_{1} \rightarrow (A2A_{2} \rightarrow ...\ldots (AnA_{n} \rightarrow B) ...\ldots )</math>. И эта нотация, как и в императивных языках программирования, использует круглые скобки:
 
<code>add (x, y) = x + y</code>
 
Можно видеть, что последняя запись — это функция с одним аргументом в строгой хаскельской нотации Хаскела. С другой стороны для каррированных функций вполне возможно делать частичное применение; что значит, при вызове функции двух аргументов передать ей только один. Как показано в предыдущей лекции результатом такого вызова будет также функция. Более чётко этот процесс можно показать на примере функции <code>inc</code>, которая прибавляет единицу к заданному аргументу:
 
<code>inc :: Integer -> Integer</code>
<code>inc = add 1</code>
 
Т.&nbsp;е. в этом случае вызов функции <code>inc</code> с одним параметром просто приведетприведёт к вызову функции <code>add</code> с двумя, первый из которых — <code>1</code>. Это интуитивное понимание понятия частичного применения. Для закрепления понимания можно рассмотреть классический пример: функция <code>map</code> (её определение на абстрактном функциональном языке приведено во '''[[Основы функционального программирования/Структуры данных и базисные операции|второй лекции]]'''). Вот определение <code>map</code> на Хаскеле:
 
<code>map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = (f x) : (map f xs)</code>
 
Как видно, здесь использована инфиксная запись операции <code>prefix</code> — двоеточие, только такая запись используется в нотации ХаскеляХаскела для обозначения или конструирования пары. После приведенногоприведённого выше определения можно произвести вызов
 
<code>map (add 1) [1, 2, 3, 4]</code>
 
Строка 96 ⟶ 95 :
== Использование λ-исчисления ==
 
Функциональная парадигма программирования основана на [[w:λ-исчисление|λ-исчислении]], поэтому вполне закономерно, что все функциональные языки поддерживают нотацию для описания λ-абстракций. HaskellХаскел не обошелобошёл стороной этот аспект, если есть необходимость в определении какой-либо функции через λ-абстракцию. Ещё через λ-абстракции можно определять анонимные функции (например, для единичного вызова). Ниже показан пример определения функций <code>add</code> и <code>inc</code> именно при помощи λ-исчисления.
 
'''Пример 12. Функции add и inc, определённые через λ-абстракции.'''▼
<!-- Неплохо бы для примеров сделать заголовки. Пока отложу -->
▲'''Пример 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 показывает вызов анонимной функции, возводящей в куб переданный параметр. Результатом выполнения этой инструкции будет бесконечный список кубов целых чисел, начиная с нуля. Необходимо отметить, что в Хаскеле используется упрощенныйупрощённый способ записи λ-выражений; в точной нотации функцию <code>add</code> правильней было бы написать как:
 
<code>add = \x -> \y -> x + y</code>
 
Остаётся отметить, что тип λ-абстракции определяется точно так же, как и тип функций. Тип λ-выражения вида <codemath>λx\lambda x.expr</codemath> будет выглядеть как T1<math>T_{1} \rightarrow T2T_{2}</math>, где T1<math>T_{1}</math> — это тип переменной <math>x</math>, а T2<math>T_{2}</math> — тип выражения <codemath>expr</codemath>.
 
== Инфиксный способ записи функций ==
Строка 117:
Для некоторых функций возможен инфиксный способ записи. Это обычно простые двоичные операции. Вот как, например, определены операции конкатенации списков и композиции функций:
 
'''Пример 14. Инфиксная операция конкатенации списков.'''
 
<code>(++) :: [a] -> [a] -> [a]
Строка 123:
(x:xs) ++ ys = x : (xs ++ ys)</code>
 
'''Пример 15. Инфиксная операция композиции функций.'''
 
<code>(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)</code>
 
Покуда инфиксные операции всё-таки являются функциями в смысле ХаскеляХаскела, то есть они каррированы, то имеет смысл обеспечить возможность частичного применения таких функций. Для того имеется специальная запись, которая в Хаскеле называется «секция»:
 
<code>(x ++) = \x -> (x ++ y)
Строка 136:
Это три секции, каждая из которых определяет инфиксную операцию конкатенации списков в соответствии с количеством переданных ей аргументов. Использование круглых скобок в записи секций обязательно.
 
Если функция принимает два параметра, то её также можно записывать в инфиксной форме. Однако если просто записать между параметрами имя функции, это будет ошибкой, ибо в строгой нотации ХаскеляХаскела это будет просто двойным применением, причемпричём в одном применении не будет хватать одного операнда. Чтобы записать функцию в инфиксной форме, её имя необходимо заключить в символы обратного апострофа — [[w:`|`]].
 
Для вновь определённых инфиксных операций возможно определение порядка вычисления. Для этого в Хаскеле есть зарезервированное слово <code>infixr</code>, которое назначает операции приоритет выполения в интервале от 0 до 9: 9 объявляется самой сильной степенью значимости. 10 также входит в этот интервал, и именно эту степень имеет операция применения). Вот так определяются степени для определенных в примерах 14 и 15 операций:
Строка 143:
infixr 9 .</code>
 
В Хаскеле все функции являются нестрогими, что значит: все они поддерживают отложенные вычисления. Если какая-то функция определена как <code>bot = bot</code>, то её вызов даст ошибку, и такие ошибки обычно сложно отслеживать. Но если есть некая константная функция, которая определена как <code>constant_1 x = 1</code>, то при вызове конструкции <code>(constant_1 bot)</code> никакой ошибки не произойдёт, т.&nbsp;к. значение функции <code>bot</code> в этом случае не вычислялось бы (вычисления отложенные, значение вычисляется только тогда, когда оно действительно требуется). Результатом вычисления, естественно, будет <code>1</code>.
 
== Упражнения ==
 
1. #Сконструировать следующие конечные списки (N — количество элементов в конструируемом списке). Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
#*Список натуральных чисел. N = 20.
#*Список нечётных натуральных чисел. N = 20.
#*Список чётных натуральных чисел. N = 20.
#*Список степеней двойки. N = 25.
#*Список степеней тройки. N = 25.
#*Список треугольных чисел [[w:Пьер Ферма|Ферма]]. N = 50.
#*Список пирамидальных чисел Ферма. N = 50.
2. #Сконструировать следующие бесконечные списки. Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.▼
#*Список факториалов.▼
#*Список квадратов натуральных чисел.▼
#*Список кубов натуральных чисел.▼
#*Список степеней пятёрки.▼
#*Список вторых суперстепеней натуральных чисел.▼
 
=== Ответы ===▼
▲2. Сконструировать следующие бесконечные списки. Для этого воспользоваться либо генераторами списков, либо конструирующими функциями.
▲*Список факториалов.
▲*Список квадратов натуральных чисел.
▲*Список кубов натуральных чисел.
▲*Список степеней пятёрки.
▲*Список вторых суперстепеней натуральных чисел.
 
1. #Конечные списки конструируются либо при помощи ограничений, вставляемых в генератор списка, либо при помощи дополнительных ограничивающих параметров.▼
 
#*<code>[1 .. 20]</code>▼
▲=== Ответы ===
#*<code>[1, 3 .. 40]</code> или <code>[1, 3 .. 39]</code>▼
 
#*<code>[2, 4 .. 40]</code>▼
▲1. Конечные списки конструируются либо при помощи ограничений, вставляемых в генератор списка, либо при помощи дополнительных ограничивающих параметров.
#*Список степеней двойки проще всего сконструировать при помощи функции (здесь <code>reverse</code> — функция обращения списка):▼
▲*<code>[1 .. 20]</code>
▲*<code>[1, 3 .. 40]</code> или <code>[1, 3 .. 39]</code>
▲*<code>[2, 4 .. 40]</code>
▲*Список степеней двойки проще всего сконструировать при помощи функции (здесь <code>reverse</code> — функция обращения списка):
<code>powerTwo 0 = []
powerTwo n = (2 ^ n) : powerTwo (n – 1)
reverse (powerTwo 25)</code>
#*:Список степеней тройки проще всего сконструировать при помощи функции (здесь <code>reverse</code> — функция обращения списка):
<code>powerThree 0 = []
powerThree n = (2 ^ n) : powerThree (n – 1)
reverse (powerThree 25)</code>
#*В отличие от предыдущих двух упражнений, здесь можно воспользоваться функцией <code>map</code>, применяющей заданную функцию ко всем элементам списка:
<code>t_Fermat 1 = 1
t_Fermat n = n + t_Fermat (n – 1)
map t_Fermat [1 .. 50]</code>
#*Конструирование списка из 50 пирамидальных чисел Ферма также основывается на использовании функции <code>map</code>:
<code>p_Fermat 1 = 1
p_Fermat n = t_Fermat n + p_Fermat (n – 1)
map p_Fermat [1 .. 50]</code>
2.#Бесконечные списки конструируются либо при помощи неограниченных генераторов, либо при помощи конструирующих функций без ограничивающих параметров.▼
 
#*Бесконечный список факториалов:▼
▲2.Бесконечные списки конструируются либо при помощи неограниченных генераторов, либо при помощи конструирующих функций без ограничивающих параметров.
▲*Бесконечный список факториалов:
<code>numbersFrom n = n : numbersFrom (n + 1)
 
factorial n = f_a n 1
 
f_a 1 m = m
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>
#*Бесконечный список степеней пятёрки:
<code>powerFive n = 5 ^ n
 
map powerFive (numbersFrom 1)</code>
#*Бесконечный список вторых суперстепеней натуральных чисел:
<code>superPower n 0 = n
superPower n p = (superPower n (p – 1)) ^ n
 
secondSuperPower n = superPower n 2
map secondSuperPower (numbersFrom 1)</code>
Источник — https://ru.wikibooks.org/wiki/Основы_функционального_программирования/Основы_языка_Haskell