Надо Знать

добавить знаний



Haskell



План:


Введение

Haskell (рус. Хаскела или Хаскелл) - стандартизированная, исключительно функциональная язык с нестрогой семантикой. Названа в честь американского математика Хаскелл Карри, работы в области математической логики которого являются базовыми для функционального программирования. Хаскела базируется на лямбда многочисленные. Важнейшими реализациями является компилятор Glasgow Haskell Compiler (GHC) и интерпретатор Hugs.


1. История

На конец 1980-х годов, уже существовали некоторые функциональные языки программирования, с собственными достоинствами и недостатками. Для того, чтобы наука получила единую основу для исследований, следует разработать стандартизированную современную функциональную язык программирования. Тогда планировалось использовать язык программирования Миранда в качестве исходного варианта, однако, ее разработчики были в этом заинтересованы. Так, в 1990 году и появилась язык Хаскела 1.0.

Текущая версия языка программирования является переработанным вариантом стандарта Хаскела-98 1999 года. Сейчас Хаскела является функциональной языке программирования, которая, в основном, используется для проведения исследований. Кроме того, существует большое количество вариантов языки программирования: Parallel Haskell, Distributed Haskell (ранее Gofin), Eager Haskell, Eden, DNA-Haskell и, также, объектно-ориентированные варианты (Haskell + +, O'Haskell, Mondrian). Для других, Хаскела был примером при разработке языка программирования. Например, в случае языка программирования Пайтон, было заимствование концепцию Лямбда-нотации и синтаксис работы со списками.


2. Применение

Несмотря на сравнительно небольшую сообщество Хаскеля, он уже показал свои сильные стороны в нескольких проектах. Pugs - реализация долгожданной языка программирования Perl 6 с интерпретатором и компилятором, которые показали полезность Хаскеля лишь через несколько месяцев после написания; также, GHC часто используется как испытательный стенд для передовых возможностей функционального программирования и оптимизаций. Darcs - это система контроля версий, которая имеет несколько инновационных особенностей. Linspire GNU / Linux использует Хаскела для разработки системных утилит. [1] xmonad - это менеджер окон для X Window System, полностью написанного на Хаскеля.


3. Особенности

3.1. Работа программ

  • Хаскела чиста функциональной языке программирования. Функции не имеют никаких побочных эффектов. Это означает, что для одних и тех же значений входных параметров всегда возвращаться одинаковые результаты вычислений.
  • Функциональные языки программирования отличаются от императивных языков программирования тем, что программист не должен определять порядок исчисления функций. Разработчику нужно только описать зависимость между данными, а транслятор уже самостоятельно определяет порядок вычислений на императивном вычислительном устройстве.
  • Отсутствуют какие-либо императивные конструкции языка программирования. Благодаря монадам можно выполнять операции ввода-вывода, другие вычисления, которые требуют сохранения состояния, в чисто функциональном виде.
  • Отсутствуют операторы изменения значения переменных. Поэтому, отсутствует разница между константами и переменными. Как следствие, отпадает необходимость в декларации const или final, которые есть, например, в языках программирования Си и Ява соответственно.
  • Отсутствует разница между идентичностью и равенством объектов.
  • Устранение проблем от наличия побочных эффектов, в значительной мере полегушуе наблюдение за последовательностью работы программы.
  • Хаскела является не строгим языком программирования. Вычисляются только выражения, значение которых необходимо для вычисления результатов.
 first xy = x square x = x * x 
Функция first при вызове с двумя параметрами возвращает первого. При вызове first x (3 +7) вычисление значения суммы (3 +7) не требуется для вычисления результата, и, поэтому, может не выполняться.
Функция square возвращает значение квадрата переданного параметра. При исчислении square (3 +5), функция будет вычислить (3 +5) * (3 +5), однако, двойное вычисления (3 +5) не является оптимальным, и имеет избегаться.
Реализация ленивых вычислений облегчается отсутствием побочных эффектов и строгим соблюдением парадигмы функционального программирования.

3.2. Система типов

  • Хаскела является сильно типизированных языке программирования. Различаются цели, числа с плавающей запятой, строчные, и другие типы данных.
  • Пидримуються переменные типов. Благодаря этому, можно делать обобщенные формулировки функций. В случае, когда такая общая функция применяется к переменным с конкретным типом, автоматически определяются и типы результатов остальных вычислений.
Функция map выполняет предоставленную функцию для каждого элемента из списка. Ее тип имеет вид:
 map :: (a -> b) -> [a] -> [b] 
В случае, если map будет вызвано с функцией toUpper, которая имеет тип Char -> Char, она будет тип:
 map toUpper :: [Char] -> [Char] 
  • С самого начала Хаскела является языком программирования со статической типизацией, хотя, существуют варианты с динамической типизацией. Это значит, что для большинства вычислений, типы аргументов известны уже на этапе трансляции. Это помогает избежать очевидных ошибок еще до начала вычислений.
  • Хаскела поддерживает функции высшего порядка (функционалы). То есть, функции, которые могут принимать в качестве аргументов и возвращать в качестве результатов функции. Одним из примеров, есть функция map, которая вычисляет предоставленную функцию f для каждого элемента одного типа (здесь списка).
 map :: (a -> b) -> [a] -> [b] map f [] = [] map fx: xs = fx: map f xs 
 map square [1,2,3] = [square 1, square 2, square 3] = [1,4,9] 
  • Поддерживается определения типов данных пользователями. Эти типы данных определяются использованием конструкторов типов данных.
 data Tree Int = Leaf Int | Branch Int (Tree Int) (Tree Int) 
В примере приведена структура данных деревьев с наповенене целыми числами. Таким образом, дерево (Tree Int) состоит или из письма (Leaf Int), или ответвления (Branch Int t1 t2), где t1 и t2 содержат поддерева, имеющие структуру данных Tree Int. Для определения этой структуры данных, нужно, также, определить конструктор Leaf с одним параметром, и конструктор Branch с тремя параметрами.
  • Функции позволяют карринг. В то время, как в других языках программирования, в качестве аргументов функции передаются кортежи, т.е. типа функций имеют вид (a, b) -> c, в Хаскела принято использовать Карри-образную форму a -> b -> c. Благодаря этому, становится возможным частичное вычисления значения функций. Выражение map toUpper является примером частичного вычисления map, поскольку он определяет функцию, а именно, функцию, переводит все буквы в верхний регистр.
  • Хаскела поддерживает классы типов. Благодаря классификации типов, можно определить совместные операции для типов одного класса. В сигнатурах функций могут присутствовать как аргументы конкретного типа, например, Char и бестиповым переменными, определяться аргументы явно заданными ограничениями типов.
Все приложения метода с классами типов имеют одинаковое имя. Это, в некотором смысле, отвечает перегрузци функций. Имя определенной функции зависит от типов аргументов. Например, метод == класса Eq сравнивает как пару цифр, так и пару строк. Однако, работа этого метода зависит от типов аргументов.

3.3. Синтаксис

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

Вместо

 readFile "input.txt" >> = writeFile "output.txt" 

или

 readFile "input.txt" >> = (\ content -> writeFile "output.txt" content) 

можно написать

 do content <- readFile "input.txt" writeFile "output.txt" content 
  • Как символьные (такие как +, -, *, /,>, <), так и алфавитно-цифровые идентификаторы (буквы, цифры, апостроф) могут использоваться как в качестве названий функций так и в качестве инфиксних и постфиксних операторов. Например, можно писать:
 a + b == (+) aba `div` b == div ab 

3.4. Программирование

  • Хаскела поддерживает поиск по шаблонам. То есть, в качестве формальных параметров можно передавать шаблоны. При этом, описаны шаблоны становятся аргументами функции.
 fac :: Integer -> Integer fac 0 = 1 fac n = n * fac (n-1) 
Функция fac вычисляет факториал числа. При вызове функции с параметром, равная 0, будет возвращена 1. Для всех остальных случаев, вычисления факториала происходит путем рекурсивного вызова n * fac (n-1). В этом примере, 0 и 1 являются шаблонами, от совпадения с которыми зависит результат вычислений.

3.5. Модули

Хаскела, также, имеет систему модулей. Существует большое количество модулей, в которых реализовано много полезных функций. Один из самых полных перечней существующих модулей содержится в Haskell Reference (Англ.) .

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

 import List import Maybe 

Различные модули могут содержать функции и типы с одинаковыми именами. Эти идентификаторы можно различать путем:

  • импорт только одного идентификатора,
 import Data.List (delete) x = delete 'a' "abc" 
  • использованием полного (вместе с модулем) имени идентификатора:
 import qualified Data.List x = Data.List.delete 'a' "abc" 

или

 import qualified Data.List as List x = List.delete 'a' "abc" 

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


4. Примеры

4.1. Факториал

Элегантное определение функции факториала, которое использует нотацию Хаскеля для списков:

 fac :: Integer -> Integer fac n = product [1 .. n] 

4.2. Числа Фибоначчи

Наивная реализация функции вычисления n числа с Последовательности Фибоначчи :

 fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1) 

Быстрее реализация вычисления последовательности:

 fibs :: [Integer] fibs = 0: 1: (zipWith (+) fibs (tail fibs)) 


4.3. Быстрая сортировка

Алгоритм быстрой сортировки записывается языке Хаскела так:

 qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x: xs) = qsort [y | y <- xs, y  = x] 

В первой строке определяется сигнатура функции qsort. Во второй строке определяется, что результат применения функции для пустого списка также пустой список. В третьей строке происходит рекурсивное сортировки непустых списков: первый элемент x берется в качестве среднего элемента результирующего списка. Перед ним сортируются все меньше, а после него - все крупные элементы списка. Для того, чтобы выбрать все меньше и крупные элементы чем x из хвоста списка xs, использовано описание списков.

Как и ожидается от алгоритма быстрой сортировки, средний асимптотический время работы этого алгоритма равна O (n \ cdot \ log n) а время работы в худшем випдаку равна O (n ^ 2) . В отличие от обычных реализаций в императивных языках программирования, описана функция работает не перетирая входной массив.


5. Сноски


Литература

  • Why Functional Programming Matters by John Hughes, The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. [1] Преимущества функционального программирования. Приводятся примеры модульности программ на основе функций высшего порядка и ленивых вычислений.
  • Simon Thompson: Haskell - The Craft of Functional Programming, 1999, Addison-Wesley, ISBN 0-201-34275-8
  • Paul Hudak: The Haskell School of Expression - Learning Functional Programming Through Multimedia., 2000, Cambridge University Press, ISBN 0-521-64338-4

код для вставки
Данный текст может содержать ошибки.

скачать

© Надо Знать
написать нам