Хаскель (мова програмування)

Матеріал з Вікіпедії — вільної енциклопедії.

**Haskell**
Зображення:Haskell Logo.jpg
Парадигма:	функціональна, не строга, модульна
Дата розробки:	1990
Система типізації:	сильна, статична
Основні реалізації:	GHC, Hugs, NHC, JHC, Yhc
Діалекти:	--
Під впливом від:	Miranda, ML, Gofer
Influenced:	Python

Хаскель (англ. Haskell programming language) — стандартизована, виключно функціональна мова програмування з нестрогою семантикою. Названа на честь американського математика Хаскеля Карі, роботи в галузі математичної логіки якого, є базовими для функціонального програмування. Хаскель основано на Лямбда численні. Найважливішими реалізаціями є Glasgow Haskell Compiler (GHC), та Hugs, інтерпретатор Хаскеля.

Зміст

1 Історія
2 Особливості
3 Приклади
4 Дивіться також
- 4.1 Література
- 4.2 Ресурси інтернет

[ред.] Історія

На кінець 1980-тих років, вже існували деякі функціональні мови програмування, з власними перевагами та недоліками. Для того, аби наука отримала єдину основу для досліджень, слід було розробити стандартизовану сучасну функціональну мову програмування. Тоді планувалось використати мову програмування Міранда в якості вихідного варіанту; однак, її розробники були в цьому не зацікавлені. Так, в 1990 році і з'явилась мова програмування Хаскель 1.0.

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

[ред.] Особливості

[ред.] Робота програм

Хаскель є чистою функціональною мовою програмування. Функції не мають жодних побочних ефектів. Це означає, що для одних і тих самих значень вхідних параметрів, завжди повертатимуться однакові результати обчислень.

Функціональні мови програмування відрізняються від імперативних мов програмування тим, що програміст не повинен визначати порядок обчислення функцій. Розробнику слід лише описати залежність між даними, а транслятор вже самотужки визначає порядок обчислень на імперативному обчислювальному пристрої.

Відсутні будь які імперативні конструкції мови програмування. Завдяки монадам можливо виконувати операції вводу- виводу-, інші обчислення, які вимагають збереження стану, в чисто функціональному вигляді.

Відсутні оператори зміни значення змінних. Через це, відсутня різниця між константами та змінними. Як наслідок, відпадає необхідність у декларації const або final, які є, наприклад, в мовах програмування Сі та Ява відповідно.

Відсутня різниця між ідентичністю та рівністю об'єктів.

Усунення проблем від наявності побочних ефектів, значною мірою полегушує спостереження за послідовністю роботи програми.

Хаскель є не строгою мовою програмування. Обчислюються лише вирази, значення яких необхідне для обчислення результатів.

 first x y = x
 square x = x * x

Функція first при виклику з двома параметрами повертає значення першого. При виклику first x (3+7) обчислення значення суми (3+7) не потрібне для обчислення результата, і, тому, може не виконуватись.

Функція square повертає значення квадрата переданого параметра. При обчисленні square (3+5), функція матиме обчислити (3+5)*(3+5), однак, подвійне обчислення (3+5) не є оптимальним, і має уникатись.

Реалізація лінивих обчислень полегшується відсутністю побочних ефектів та строгим дотриманням парадигми функціонального програмування.

[ред.] Система типів

Хаскель є сильно типизованою мовою програмування. Розрізняються цілі, числа з плаваючою комою, рядкові, та інши типи даних.

Підримуються змінні типів. Завдяки цьому, можна робити узагальнені формулювання функцій. У випадку, коли така загальна функція застосовується до змінних з конкретним типом, автоматично визначаються і типи результатів решти обчислень.

Функція map виконує надану функцію для кожного елемента із списка. Її тип має вигляд:

 map :: (a -> b) -> [a] -> [b]

У випадку, якщо map буде викликано із функцією toUpper, яка має тип Char -> Char, матима вона тип:

 map toUpper :: [Char] -> [Char]

Починаючи з побудови, Хаскель є мовою програмування з статичною типізацією, хоча, існують варіанти з динамічною типізацією. Це значить, що для більшості обчислень, типи аргументів відомі вже на етапі трансляції. Це допомагає уникнути очевидні помилки ще до початку обчислень.

Хаскель підтримує функції вищого порядку (функціонали). Тобто, функції, які можуть приймати в якості аргументів та повертати в якості результатів функції. Одним із прикладів, є функція map, яка яка обчислює надану функцію f для кожного елемента одного типу (тут списка).

 map :: (a -> b) -> [a] -> [b]
 map f [] = []
 map f x:xs = f x : 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 порівнює як пару цифр, так і пару рядків. Однак, робота цього метода залежить від типів аргументів.

[ред.] Синтаксис

Розрізняється реєстр літер. Ідентифікатори, що починаються з великих літер, означають типи та конструктори. Ідентифікатори, що починаються з малої літери, означають змінні, функції, та параметри.

Хаскель пропонує ряд синтаксичних особливостей. Вони мають допомагати висловлювати все відповідно до функціональної парадигми.

Замість

 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      ==  (+) a b
 a `div` b  ==  div a b

[ред.] Програмування

Хаскель підтримує пошук по шаблонах. Тобто, в якості формальних параметрів можна передавати шаблони. При цьому, описані шаблони стають аргументами функції.

 fac :: Integer -> Integer
 fac 0 = 1
 fac n = n * fac (n-1)

Функція fac обчислює факторіал числа. При виклику функції з параметром, що дорівнює 0, буде повернута 1. Для всіх інших випадків, обчислення факторіала відбувається шляхом рекурсивного виклику n*fac(n-1). В цьому прикладі, 0 та 1 є шаблонами, від збігу з якими залежить результат обчислень.

[ред.] Модулі

Хаскель, також, має систему модулів. Існує велика кількість модулів, в яких реалізовано багато корисних функцій. Один із найповніших переліків існуючих модулів міститься в 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.

[ред.] Приклади

[ред.] Факторіал

Елегантне визначення функції факторіалу, яке використовує нотацію Хаскеля для списків:

 fac :: Integer -> Integer
 fac n = product [1..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))

[ред.] Швидке сортування

Алгоритм швидкого сортування записується мовою Хаскель наступним чином:

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

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

Як і очікується від алгоритму швидкого сортування, середній асимптотичний час роботи цього алгоритму дорівнює $O(n \cdot \log n)$ а час роботи в найгіршому випдаку дорівнює $O (n 2)$ . На відміну від звичайних реалізацій в імперативних мовах програмування, описана функція працює не перетираючи вхідний масив.

[ред.] Дивіться також

ML
Pugs (імплементація Перл версії 6 на Хаскель)

[ред.] Література

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 0201342758
Paul Hudak: The Haskell School of Expression - Learning Functional Programming Through Multimedia., 2000, Cambridge University Press, ISBN 0521643384

[ред.] Ресурси інтернет

http://www.haskell.org/ – Центральний портал мови програмування Хаскель.
http://www.haskell.org/learning.html – Корисна інформація для вивчення Хаскель.
http://www.haskell.org/hugs/ – Hugs 98, безкоштовний інтерпретатор Хаскель.
http://haskell.readscheme.org/ – Наукова література про Хаскель.

Отримано від "http://uk.wikipedia.org../../../%D1%85/%D0%B0/%D1%81/%D0%A5%D0%B0%D1%81%D0%BA%D0%B5%D0%BB%D1%8C_%28%D0%BC%D0%BE%D0%B2%D0%B0_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F%29.html"

Категорії: Мови програмування | Функціональні мови програмування | Декларативні мови програмування