Функции многих переменных и порядок определения функций

Лабораторная работа № 2

«Функциональное программирование. Язык Haskell»

1. Цель работы:

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

2. Порядок выполнения работы:

1. Изучить основные теоретические положения.

2. Написать программу на языке Haskell согласно варианту в журнале.

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

4. Защитить отчет у преподавателя.

 

3. Основные теоретические положения:

3.1. Что такое Haskell?

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

Hasckell является одним из самых распространённых нестрогих языков программирования. Имеет очень развитую систему типизации, однако система модулей разработана хуже. Последний стандарт языка, ставший стандартом функционального программирования — Haskell-98. Берёт своё начало из языка Miranda, который был разработан Дэвидом Тёрнером в качестве стандартного функционального языка. Назван по имени математика Хаскелла Карри.

Язык появился в 1990 году. Haskell популярен в академических кругах, но малоизвестен среди прикладных программистов. В последнее время расширяется набор прикладных библиотек, язык интегрируется в распространённые программные системы (.Net, COM/ActiveXHaskellScript, Javajaskell), что делает язык всё более и более привлекательным для профессиональных программистов.

Типы

Программы на языке Haskell представляют собой выражения, вычисление которых приводит к значениям. Каждое значение имеет тип. Интуитивно тип можно понимать просто как множество допустимых значений выражения. Для того, чтобы узнать тип некоторого выражения, можно использовать команду интерпретатора:type (или:t). Кроме того, можно выполнить команду:set +t, для того, чтобы интерпретатор автоматически печатал тип каждого вычисленного результата.
Основными типами языка Haskell являются:

• Типы Integer и Int используется для представления целых чисел, причем значения типа Integer не ограничены по длине.

• Типы Float и Double используется для представления вещественных чисел.

• Тип Bool содержит два значения: True и False, и предназначен для представления результата логических выражений.

• Тип Char используется для представления символов. Имена типов в языке Haskell всегда начинаются с заглавной буквы.

Язык Haskell является сильно типизированным языком программирования. Тем не менее в большинстве случаев программист не обязан объявлять, каким типам принадлежат вводимые им переменные. Интерпретатор сам способен вывести типы употребляемых пользователем переменных.

Однако, если все же для каких-либо целей необходимо объявить, что некоторое значение принадлежит некоторому типу, используется конструкция вида: переменная:: Тип. Если включена опция интерпретатора +t, он печатает значения в таком же формате.
Ниже приведен пример протокола сессии работы с интерпретатором. Предполагается, что текст, следующий за приглашением Prelude>, вводит пользователь, а следующий за этим текст представляет ответ системы.

 

Текст программы:

Prelude>:set +t

Prelude>1

Integer

Prelude>1.2

Double

Prelude>’a’

’a’:: Char

Prelude>True

True:: Bool

Из данного протокола можно сделать вывод, что значения типа Integer, Double и Char задаются по тем же правилам, что и в языке Си.
Развитая система типов и строгая типизация делают программы на языке Haskell безопасными по типам. Гарантируется, что в правильной программе на языке Haskell все типы используются правильно. С практической точки зрения это означает, что программа на языке Haskell при выполнении не может вызвать ошибок доступа к памяти (Accessviolation). Также гарантируется, что в программе не может произойти использование неинициализированных переменных. Таким образом, многие ошибки в программе отслеживаются на этапе ее компиляции, а не выполнения.

 

Арифметика

Интерпретатор Hugs можно использовать для вычисления арифметическихвыражений. При этом можно использовать операторы +, -,*, / (сложение, вычитание, умножение и деление) с обычными правилами приоритета. Кроме того, можно использоватьоператор ^ (возведение в степень). Таким образом, сеанс работы может выглядетьследующим образом:

 

Текст программы:

Prelude>2*2

Integer

Prelude>4*5 + 1

Integer

Prelude >2^3

Integer

Кроме того, можно использовать стандартные математические функции sqrt (квадратныйкорень), sin, cos, exp и т.д. В отличие от многих других языков программирования, вHaskell при вызове функции не обязательно помещать аргумент в скобки. Таким образом, можно просто писать sqrt 2, а не sqrt(2). Пример:

 

Текст программы:

Prelude>sqrt 2

Double

Prelude>1 + sqrt 2

Double

Prelude>sqrt 2 + 1

Double

Prelude>sqrt (2 + 1)

Double

 

Из данного примера можно сделать вывод, что вызов функции имеет более высокий приоритет, чем арифметические операции, так что выражение sqrt 2 + 1 интерпретируется как (sqrt 2) + 1, а не sqrt (2 + 1). Для задания точного порядка вычисления следуетиспользовать скобки, как в последнем примере. (В действительности вызов функции имеет более высокий приоритет, чем любой бинарный оператор.) Также следует заметить, что в отличие от большинства других языков программирования, целочисленные выражения в языке Haskell вычисляются с неограниченным числом разрядов (Попробуйте вычислить выражение 2^5000.) В отличие от языка Си, гдемаксимально возможное значение типа int ограничено разрядностью машины (на современных персональных компьютерах оно равно 2 1 2147483647 31 − =), тип Integer в языке Haskell может хранить целые числа произвольной длины.

 

Кортежи

Помимо перечисленных выше простых типов, в языке Haskell можно определять значения составных типов. Например, для задания точки на плоскости необходимы двачисла, соответствующие ее координатам. В языке Haskell пару можно задать, перечисливкомпоненты через запятую и взяв их в скобки: (5,3). Компоненты пары не обязательнодолжны принадлежать одному типу: можно составить пару, первым элементом которойбудет строка, а вторым- число и т.д.

В общем случае, если a и b – некоторые произвольные типы языка Haskell, тип пары, в которой первый элемент принадлежит типу a, а второй - типу b, обозначается как(a,b). Например, пара (5,3) имеет тип (Integer, Integer); пара (1, 'a') принадлежит типу(Integer, Char). Можно привести и более сложный пример: пара ((1,'a'),1.2) принадлежит типу ((Integer,Char),Double). Проверьте это с помощью интерпретатора.

Следует обратить внимания, что хотя конструкции вида (1,2) и (Integer,Integer) выглядят похоже, в языке Haskell они обозначают совершенно разные сущности. Перваяявляется значением, в то время как последняя - типом.

Для работы с парами в языке Haskell существуют стандартные функции fst и snd, возвращающие, соответственно, первый и второй элементы пары (названия этих функцийпроисходят от английских слов firs(первый) и second (второй)). Таким образом, их можноиспользовать следующим образом:

 

Текст программы:

 

Prelude > fst (5, True)

Integer

Prelude > snd (5, True)

True:: Bool

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

 

Текст программы:

Prelude>(1,2,3)

(1,2,3):: (Integer,Integer,Integer)

Prelude>(1,2,3,4)

(1,2,3,4):: (Integer,Integer,Integer,Integer)

 

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

Элементом кортежа может быть значение любого типа, в том числе и другой кортеж. Для доступа к элементам кортежей, составленных из пар, может использоваться комбинация функций fst и snd. Следующий пример демонстрирует извлечение элемента 'a' из кортежа(1, ('a', 23.12)):

 

Текст программы:

Prelude >

fst (snd (1, ('a', 23.12)))

'a':: Char

 

Списки

В отличие от кортежей, список может хранить произвольное количество элементов. Чтобы задать список в Haskell, необходимо в квадратных скобках перечислить его элементы через запятую. Все эти элементы должны принадлежать одному и тому же типу. Тип списка с элементами, принадлежащими типу a, обозначается как [a].

 

Текст программы:

 

Prelude>[1,2]

[1,2]:: [Integer]

Prelude>['1','2','3']

['1','2','3']:: [Char]

 

Всписке может не быть ни одного элемента. Пустой список обозначается как [].

Оператор: (двоеточие) используется для добавления элемента в начало списка. Еголевым аргументом должен быть элемент, а правым- список:

 

Текст программы:

 

Prelude>1:[2,3]

[1,2,3]:: [Integer]

Prelude>'5':['1','2','3','4','5']

['5','1','2','3','4','5']:: [Char]

Prelude>False:[]

[False]:: [Bool]

 

Спомощью оператора (:) и пустого списка можно построить любой список:

 

Текст программы:

Prelude>1:(2:(3:[]))

[1,2,3]:: Integer

 

Оператор (:) ассоциативен вправо, поэтому в приведенном выше выражении можноопустить скобки:

 

Текст программы:

 

Prelude>1:2:3:[]

[1,2,3]:: Integer

 

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

 

Текст программы:

 

Prelude>[(1,'a'),(2,'b')]

[(1,'a'),(2,'b')]:: [(Integer,Char)]

Prelude>[[1,2],[3,4,5]]

[[1,2],[3,4,5]]:: [[Integer]]

 

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

Функция head возвращает первый элемент списка.

Функция last возвращает последний элемент списка.

Функция tail возвращает список без первого элемента

Функция init возвращает список без последнего элемента

Функция null проверяет список на пустоту. Если в качестве аргумента этой операции будет задан пустой список, то функция выдаст значение True, в противномслучае –False.

Функция length возвращает длину списка.

Функция elem проверяет наличие элемента в списке.

Функция take возвращает список, состоящий из n первых элементов исходногосписка.

Функция zip возвращает список, состоящий из пар объединенных исходныхсписков.

Функция!! возвращает элемент, номер которого задан (начиная с 0).

Функции head и tail определены для непустых списков. При попытке применить их кпустому списку интерпретатор сообщает об ошибке. Примеры работы с указанными функциями:

 

Текст программы:

 

Prelude>head [1,2,3]

1:: IntegerPrelude>tail [1,2,3]

[2,3]:: [Integer]

Prelude>tail [1]

[]:: Integer

Prelude>length [1,2,3]

Int

Prelude>elem 2 [1,2,3]

True:: Bool

Prelude> take 2 [1,2,3]

[1,2]:: [Integer]

Prelude> zip ["20","30"] [1,2,3]

[("20",1),("30",2)]:: [([Char],Integer)]

Prelude> [1,2,3,4,5]!! 3

Integer

Заметьте, что результат функции length принадлежит типу Int, а не типу Integer.

Для соединения (конкатенации) списков в Haskell определен оператор ++.

 

Текст программы:

 

Prelude>[1,2]++[3,4]

[1,2,3,4]:: Integer

 

Строки

Строковые значения в языке Haskell, как и в Си, задаются в двойных кавычках. Онипринадлежат типу String.

 

Текст программы:

 

Prelude>"hello"

"hello":: String

 

В действительности строки являются списками символов; таким образом, выражения"hello", ['h','e','l','l','o'] и 'h':'e':'l':'l':'o':[] означают одно и то же, а тип String является синонимом для [Char]. Все функции для работы со списками можно использовать при работе со строками:

 

Текст программы:

 

Prelude>head "hello"

'h':: Char

Prelude>tail "hello"

"ello":: [Char]

Prelude>length "hello"

Int

Prelude >" hello " ++ ", world "

"hello, world":: [Char]

 

Для преобразования числовых значений в строки и наоборот существуют функции read и show:

 

Текст программы:

 

Prelude>show 1

"1":: [Char]

Prelude>"Formula " ++ show 1

"Formula 1":: [Char]

Prelude>1 + read "12"

Integer

 

Если функция show не сможет преобразовать строку в число, она сообщит обошибке.

 

Функции

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

Команда:load позволяет загрузить в интерпретатор программу на языке Haskell, содержащуюся в указанном файле.

Команда:edit запускает процесс редактирования последнего загруженного файла.

Команда:reload перечитывает последний загруженный файл.

Определения пользовательских функций должны находиться в файле, которыйнужно загрузить в интерпретатор Hugs с помощью команды:load. Для редактированиязагруженной программы можно использовать команду:edit. Она запускает внешний редактор (по умолчанию это Notepad) для редактирования файла. После завершения сеансаредактирования редактор необходимо закрыть; при этом интерпретатор Hugs перечитает содержимое изменившегося файла. Однако файл можно редактировать и непосредственно из оболочки Windows. В этом случае, для того чтобы интерпретатор смог перечитать файл, необходимо явно вызывать команду:reload.

Рассмотрим пример. Создайте в каком-либо каталоге файл lab1.hs.

Пусть полный путь к этому файлу с:\labs\lab1.hs (это только пример, ваши файлы могутназываться по-другому). В интерпретаторе Hugs выполните следующие команды:

Prelude>:load "c:\\labs\\lab1.hs"

Если загрузка проведена успешно, приглашение интерпретатора меняется на Main>. Дело в том, что если не указано имя модуля, считается, что оно равно Main.

Main>:edit

Здесь должно открыться окно редактора, в котором можно вводить текст программы. Введите:

x = [1,2,3]

Сохраните файл и закройте редактор. Интерпретатор Hugs загрузит файлс:\labs\lab1.hs и теперь значение переменной x будет определено:

Main>x

[1,2,3]:: [Integer]

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

 

Текст программы:

 

square:: Integer -> Integer

square x = x * x

 

Первая строка (square:: Integer ->Integer) объявляет, что мы определяем функцию square, принимающую параметр типа Integer и возвращающую результат типа Integer.

Вторая строка (square x = x * x) является непосредственно определением функции. Функция square принимает один аргумент и возвращает его квадрат.

Функции в языке Haskell являются значениями “первого класса”. Это означает, чтоони “равноправны” с такими значениями, как целые и вещественные числа, символы, строки, списки и т.д. Функции можно передавать в качестве аргументов в другие функции, возвращать их из функций и т.п. Как и все значения в языке Haskell, функции имеют тип. Тип функции, принимающей значения типа a и возвращающей значения типа b, обозначается как a->b.

Загрузите созданный файл в интерпретатор и выполните следующие команды:

 

Текст программы:

 

Main>:typesquare

square:: Integer ->Integer

Main > square 2

Integer

 

Заметим, что в принципе объявление типа функции square не являлось необходимым: интерпретатор сам мог вывести необходимую информацию о типе функции из ееопределения. Однако, во-первых, выведенный тип был бы более общим, чем Integer ->Integer, а во-вторых, явное указание типа функции является “хорошим тоном” при программировании на языке Haskell, поскольку объявление типа служит своего рода документацией к функции и помогает выявлять ошибки программирования.

Имена определяемых пользователем функций и переменных должны начинаться слатинской буквы в нижнем регистре. Остальные символы в имени могут быть прописными или строчными латинскими буквами, цифрами или символами _ и ' (подчеркивание иапостроф). Таким образом, ниже перечислены примеры правильных имен переменных:

 

Var

Var 1

VariableName

Variable _ name

var '

 

Условные выражения

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

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

 

Текст программы:

 

signum:: Integer -> Integer

signum x = if x > 0 then 1

else if x < 0 then -1

Else 0

 

Условное выражение записывается в виде: if условие then выражение else выражение. Выражения в then-части и в else-части условного оператора должныпринадлежать одному типу.

Условие в определении условного оператора представляет собой любое выражениетипа Bool. Примером таких выражений могут служить сравнения. При сравнении можноиспользовать следующие операторы: <, >, <=, >=.

·  == – оператор проверки на равенство.

·  /= – оператор проверки на неравенство.

Выражения типа Bool можно комбинировать с помощью общепринятых логическихоператоров && и || (И и ИЛИ), и функции отрицания not. Примеры допустимых условий:

 

Текст программы:

 

x >= 0 && x <= 10

x > 3 && x /= 10

(x > 10 || x < -10) &&not (x == y)

 

Разумеется, можно определять свои функции, возвращающие значения типа Bool, и использовать их в качестве условий. Например, можно определить функцию isPositive, возвращающую True, если ее аргумент неотрицателен и False в противном случае:

 

isPositive:: Integer ->Bool

isPositive x = if x > 0 then True else False

 

Теперь функцию signum можно определить следующим образом:

 

signum:: Integer -> Integer

signum x = if isPositive x then 1

else if x < 0 then -1 else 0

 

Отметим, что функцию isPositive можно определить и проще:

 

isPositive x = x > 0

Функции многих переменных и порядок определения функций

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

 

Текст программы:

 

add:: Integer ->Integer ->Integer

add x y = x + y

 

Тип функции add может выглядеть несколько загадочно. Вязыке Haskell считается, что операция -> ассоциативна вправо. Таким образом, тип функции add может быть прочитан как Integer -> (Integer ->Integer), т.е. в соответствие с правилом каррирования, результатом применения функции add к одному аргументу будет функция, принимающая один параметр типа Integer. Вообще, тип функции, принимающей n аргументов, принадлежащих типам t1, t2,…, tn, и возвращающей результат типа a, записывается в виде t1->t2->...->tn->a.

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

 

Задания к лабораторной работе:

Напишите функции, решающие следующие задачи:

1.

2. По введенному номеру недели вывести наименование этого дня. Предусмотреть корректный ввод данных.

3. Дано 2 числа. Найти их НОД, проверить заданные числа на четность/нечетность.

4. Дано 2 числа. Упорядочьте их по возрастанию.

5. Дано 2 числа. Упорядочьте их по убыванию.

6. Дан список целых чисел. Добавьте элемент в начало списка.

7. Дан список целых чисел. Добавьте элемент в конец списка.

8. Реализуйте факториал числа.

9. Реализуйте число Фибоначчи.

10. Дан список чисел. Найдите в нем все числа, которые больше 10.

 

Контрольные вопросы:

1. Вчем отличие команд интерпретатора от выражений языка Haskell?

2. Основные типы языка Haskell.

3. Функции для работы с кортежами.

4. Функции для работы со списками.

5. Условные выражения в языке Haskell.

6. Определение функций в языке Haskell.

 

 

Пример оформления отчета:

Лабораторная работа №1

«Функциональное программирование. Язык Haskell»

Пример задачи: определение делителей числа.

Файл division.hs

division:: Int -> [Int]

 division x=filter (divisible x) [1.. x]

divisible x y= x `mod` y ==0 --определение делится ли число х на у без остатка

 

Рисунок 1 – Результат работы программы