vbrus.narod.ru
Чтиво - функциональное программирование на Haskell | ||
1. Что это такое? - Haskell
Hasckell является одним из самых распространённых нестрогих языков программирования. Имеет очень развитую систему типизации, однако система модулей разработана хуже. Последний стандарт языка, ставший стандартом функционального программирования — Haskell-98. Берёт своё начало из языка Miranda, который был разработан Дэвидом Тёрнером в качестве стандартного функционального языка. Назван по имени математика Хаскелла Карри. Язык появился в 1990 году. Haskell популярен в академических кругах, но малоизвестен среди прикладных программистов. В последнее время расширяется набор прикладных библиотек, язык интегрируется в распространённые программные системы (.Net [1], COM/ActiveX HaskellScript, Java jaskell), что делает язык всё более и более привлекательным для профессиональных программистов. Наверх | ||
2. Типы, Арифметика, Кортежи, Списки, Строки, Функции, Условные выражения - Haskell
Программы на языке Haskell представляют собой выражения, вычисление которых приводит к значениям. Каждое значение имеет тип. Интуитивно тип можно понимать просто как множество допустимых значений выражения. Для того, чтобы узнать тип некоторого выражения, можно использовать команду интерпретатора :type (или :t). Кроме того, можно выполнить команду :set +t, для того, чтобы интерпретатор автоматически печатал тип каждого вычисленного результата. Основными типами языка Haskell являются: • Типы Integer и Int используется для представления целых чисел, причем значения типа Integer не ограничены по длине. • Типы Float и Double используется для представления вещественных чисел. • Тип Bool содержит два значения: True и False, и предназначен для представления результата логических выражений. • Тип Char используется для представления символов. Имена типов в языке Haskell всегда начинаются с заглавной буквы. Язык Haskell является сильно типизированным языком программирования. Тем не менее в большинстве случаев программист не обязан объявлять, каким типам принадлежат вводимые им переменные. Интерпретатор сам способен вывести типы употребляемых пользователем переменных. Однако, если все же для каких-либо целей необходимо объявить, что некоторое значение принадлежит некоторому типу, используется конструкция вида: переменная :: Тип. Если включена опция интерпретатора +t, он печатает значения в таком же формате. Ниже приведен пример протокола сессии работы с интерпретатором. Предполагается, что текст, следующий за приглашением Prelude>, вводит пользователь, а следующий за этим текст представляет ответ системы. Prelude>:set +t Prelude>1 1 :: Integer Prelude>1.2 1.2 :: Double Prelude>’a’ ’a’ :: Char Prelude>True True :: Bool Из данного протокола можно сделать вывод, что значения типа Integer, Double и Char задаются по тем же правилам, что и в языке Си. Развитая система типов и строгая типизация делают программы на языке Haskell безопасными по типам. Гарантируется, что в правильной программе на языке Haskell все типы используются правильно. С практической точки зрения это означает, что программа на языке Haskell при выполнении не может вызвать ошибок доступа к памяти (Access violation). Также гарантируется, что в программе не может произойти использование неинициализированных переменных. Таким образом, многие ошибки в программе отслеживаются на этапе ее компиляции, а не выполнения. Арифметика Интерпретатор Hugs можно использовать для вычисления арифметических выражений. При этом можно использовать операторы +, -, *, / (сложение, вычитание, умножение и деление) с обычными правилами приоритета. Кроме того, можно использовать оператор ^ (возведение в степень). Таким образом, сеанс работы может выглядеть следующим образом: Prelude>2*2 4 :: Integer Prelude>4*5 + 1 21 :: Integer Prelude>2^3 8 :: Integer Кроме того, можно использовать стандартные математические функции sqrt (квадратный корень), sin, cos, exp и т.д. В отличие от многих других языков программирования, в Haskell при вызове функции не обязательно помещать аргумент в скобки. Таким образом, можно просто писать sqrt 2, а не sqrt(2). Пример: Prelude>sqrt 2 1.4142135623731 :: Double Prelude>1 + sqrt 2 2.4142135623731 :: Double Prelude>sqrt 2 + 1 2.4142135623731 :: Double Prelude>sqrt (2 + 1) 1.73205080756888 :: Double Из данного примера можно сделать вывод, что вызов функции имеет более высокий приоритет, чем арифметические операции, так что выражение sqrt 2 + 1 интерпретируется как (sqrt 2) + 1, а не sqrt (2 + 1). Для задания точного порядка вычисления следует использовать скобки, как в последнем примере. (В действительности вызов функции имеет более высокий приоритет, чем любой бинарный оператор.) Также следует заметить, что в отличие от большинства других языков программирования, целочисленные выражения в языке Haskell вычисляются с неограниченным числом разрядов (Попробуйте вычислить выражение 2^5000.) В отличие от языка Си, где максимально возможное значение типа int ограничено разрядностью машины (на современных персональных компьютерах оно равно 231-1 = 2147483647), тип 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, возвращающие, соответственно, первый и второй элементы пары (названия этих функций происходят от английских слов «first» (первый) и «second» (второй)). Таким образом, их можно использовать следующим образом Prelude>fst (5, True) 5 :: 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’ :: Integer Списки В отличие от кортежей, список может хранить произвольное количество элементов. Чтобы задать список в 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 возвращает первый элемент списка. • Функция tail возвращает список без первого элемента. • Функция length возвращает длину списка. Функции head и tail определены для непустых списков. При попытке применить их к пустому списку интерпретатор сообщает об ошибке. Примеры работы с указанными функциями: Prelude>head [1,2,3] 1 :: Integer Prelude>tail [1,2,3] [2,3] :: [Integer] Prelude>tail [1] [] :: Integer Prelude>length [1,2,3] 3 :: Int Заметьте, что результат функции 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" "Hello" :: [Char] Prelude>length "hello" 5 :: 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" 13 :: 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>:type square square :: Integer -> Integer Main>square 2 4 :: Integer Заметим, что в принципе объявление типа функции square не являлось необходимым: интерпретатор сам мог вывести необходимую информацию о типе функции из ее определения. Однако, во-первых, выведенный тип был бы более общим, чем Integer -> Integer, а во-вторых, явное указание типа функции является «хорошим тоном» при программировании на языке Haskell, поскольку объявление типа служит своего рода документацией к функции и помогает выявлять ошибки программирования. Имена определяемых пользователем функций и переменных должны начинаться с латинской буквы в нижнем регистре. Остальные символы в имени могут быть прописными или строчными латинскими буквами, цифрами или символами _ и ’ (подчеркивание и апостроф). Таким образом, ниже перечислены примеры правильных имен переменных: var var1 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 выражение. Обратите внимание, что хотя по виду это выражение напоминает соответствующий оператор в языке Си или Паскаль, в условном выражении языка Haskell должны присутствовать и 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 Информация бралась с: http://sguprog.narod.ru/ Наверх | ||
3. Рекурсия, Операция выбора(Case) - HaskellРекурсия В императивных языках программирования основной конструкцией является цикл. В Haskell вместо циклов используется рекурсия. Функция называется рекурсивной, если она вызывает сама себя (или, точнее, определена в терминах самой себя). Рекурсивные функции существуют в императивных языках, но используются не столь широко. Одной из простейших рекурсивных функций является факториал: factorial :: Integer -> Integer factorial n = if n == 0 then 1 else n * factorial (n - 1) (Заметьте, что мы пишем factorial (n - 1), а не factorial n - 1 — вспомните о приоритетах операций.) Использование рекурсии может вызвать трудности. Концепция рекурсии напоминает о применяющемся в математике приеме доказательства по индукции. В нашем определении факториала мы выделяем «базу индукции» (случай n == 0) и «шаг индукции» (переход от factorial n к factorial (n - 1). Выделение таких компонент — важный шаг в определении рекурсивной функции. Операция выбора(Case) Ранее был рассмотрен условный оператор. Его естественным продолжением является оператор выбора case, аналогичный конструкции switch языка Си. Предположим, нам надо определить некоторую (довольно странную) функцию, которая возвращает 1, если ей передан аргумент 0; 5, если аргумент был равен 1; 2, если аргумент равен 2 и -1 во всех остальных случаях. В принципе, эту функцию можно записать с помощью операторов if, однако результат будет длинным и малопонятным. В таких случаях помогает использование case: f x = case x of 0 -> 1 1 -> 5 2 -> 2 _ -> -1 Синтаксис оператора case очевиден из приведенного примера; следует только сделать замечание, что символ _ аналогичен конструкции default в языке Си. Однако у внимательного читателя может возникнуть закономерный вопрос: каким образом интерпретатор языка Haskell распознает, где закончилось определение одного случая и началось определение другого? Ответ заключается в том, что в языке Haskell используется двумерная система структурирования текста (аналогичная система используется в более широко известном языке Python). Эта система позволяет обойтись без специальных символов группировки и разделения операторов, подобным символам {, } и ; языка Си. В действительности в языке Haskell также можно использовать эти символы в том же смысле. Так, вышеприведенную функцию можно записать и таким образом (демонстрирующем, как не надо оформлять тексты программ): f x = case x of { 0 -> 1; 1 -> 5; 2 -> 2; _ -> -1 } Такой способ явно задает группировку и разделение конструкций языка. Однако можно обойтись и без него. Общее правило таково. После ключевых слов where, let, do и of интерпретатор вставляет открывающую скобку ({) и запоминает колонку, в которой записана следующая команда. В дальнейшем перед каждой новой строкой, выровненной на запомненную величину, вставляется разделяющий символ ‘;’. Если следующая строка выровнена меньше (т.е. ее первый символ находится левее запомненной позиции), вставляется закрывающая скобка. Это может выглядеть несколько сложновато, но в действительности все довольно просто. Применяя описанное правило к определению функции f, получим, что оно воспринимается интерпретатором следующим образом: f x = case x of{ ;0 -> 1 ;1 -> 5 ;2 -> 2 ;_ -> -1 } В любом случае можно не использовать этот механизм и всегда явно указывать символы {, } и ;. Наверх | ||
4. Задачи - Haskell
==================================================================== Откройте блокнот в нем напишите следующие строчки: sum :: Int sum = 5+5 Далее сохраните файл с расширением .HS и запустите его через интерпретатор (я использую WinHugs) после того как запустите на экране вы должны увидиь вот это: main> напиши рядом (при этом соблюдай регистр букв) с Main> слово: sum Теперь до тебя должно дойти что такое Haskell, ыы шутка:) Hello World - Haskell ==================================================================== module Hello where hello::String hello = "Hello World!" Сложение двух чисел, числа вводятся с клавиатуры - Haskell ==================================================================== sum :: IO Integer sum = let readNum :: IO Integer readNum = readLn in do putStr "Введите целое число: " x1 <- readNum putStr "Введите другое целое число: " x2 <- readNum putStr ("Их сумма равна " ++ show (x1+x2)) return (x1 + x2) -- sum Программа просит ввести имя файла и распечатывает его на экране - Haskell ==================================================================== import IO -- программа просит ввести имя файла и распечатывает его на экране printFile = do putStr "Укажите файл: " name <- getLine fromHandle <- openFile name ReadMode contents <- hGetContents fromHandle hPutStr stdout contents Программа просит ввести имя файла и целое число n, затем n первых строк файла выводится на экран - Haskell ==================================================================== import IO -- программа просит ввести имя файла и целое число n, затем n первых строк файла выводится на экран printStrInFile = let readNum :: IO Integer readNum = readLn nStr _ [] = [] nStr 0 ss = [] nStr n (s:ss) = s:nStr (n - 1) ss in do putStr "Укажите файл: " name <- getLine putStr "Введите число строк: " n <- readNum fromHandle <- openFile name ReadMode contents <- hGetContents fromHandle hPutStr stdout (unlines (nStr n (lines contents))) --printStrInFile Факториал на Haskell - Haskell ==================================================================== fac :: Integer -> Integer fac 0 = 1 fac n | n > 0 = n * fac (n - 1) Пример быстрой сортировки - Haskell ==================================================================== qsort [] = [] qsort (x:xs) = qsort [ u | u<-xs, u ] Простейший калькулятор - Haskell ==================================================================== Простейший калькулятор для вычисления выражений в обратной польской записи может быть определён на языке Haskell при помощи одной функции: calc :: String -> [Float] calc = foldl f [] . words where f (x:y:zs) "+" = (y + x):zs f (x:y:zs) "-" = (y - x):zs f (x:y:zs) "*" = (y * x):zs f (x:y:zs) "/" = (y / x):zs f xs y = read y : xs Наверх | ||
