Haskell

Материал из Википедии — свободной энциклопедии

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

[править] Характеристики языка

В качестве основных характеристик языка Haskell можно выделить следующие:

• возможность использования лямбда-абстракции;
• функции высшего порядка;
• недопустимость побочных эффектов (чистота языка);
• ленивые вычисления (lazy evaluation);
• сопоставление по образцу, функциональные образцы (pattern matching);
• параметрический полиморфизм и полиморфизм классов типов;
• статическая типизация;
• автоматическое выведение типов (основано на модели типизации Хиндли-Милнера);
• алгебраические типы данных;
• типы данных с параметрами;
• рекурсивные типы данных;
• абстрактные типы данных (инкапсуляция);
• списочные включения (list comprehensions);
• использование охраны (guards);
• возможность писать программы с побочными эффектами без нарушения парадигмы функционального программирования с помощью монад;
• возможность интеграции с программами, реализованными на императивных языках программирования посредством открытых интерфейсов (стандартное расширение языка Foreign Function Interface).

Возможности языка не ограничиваются стандартом. Некоторые реализации предлагают собственные расширения языка.

[править] Использование

Имеет интерпретаторы (один из самых известных — HUGS) и компиляторы (один из самых известных — Glasgow Haskell Compiler (GHC)).

Популярен в академических кругах, но малоизвестен среди прикладных программистов. В последнее время расширяется набор прикладных библиотек, язык интегрируется в распространённые программные системы (.Net [1], COM/ActiveX HaskellScript), что делает язык всё более и более привлекательным для профессиональных программистов.

Расширения языка:

• генерация исходного кода во время компиляции (Template Haskell);
• объектно-ориентированное программирование (O’Haskell, Haskell++ и Mondrian).

Расширения реализаций языка (относится к GHC):

• развитие системы типизации;
• многопоточность;
• параллельные вычисления;
• распределённые вычисления.

[править] Примеры

[править] Простейшие примеры

Следующий пример показывает синтаксис языка Haskell при реализации функции для вычисления факториала:

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

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

Первая строка в приведённом определении явлется необязательной, т. к. определяет (вернее, ограничивает) тип функции, который может быть выведен системой типизации самостоятельно. Эта строка может быть прочитана как: функция fac имеет тип (::) из целого в целое (Integer -> Integer). Это значит, что она получает на вход один целочисленный аргумент и возвращает результат также целого типа. Как сказано выше, типы всех функций может быть выведен автоматически, если программист явно не указал их.

Вторая строка основана на механизме сопоставления с образцами, который является важной особенностью языка Haskell. Этот механизм заставляет интерпретатор языка пробегаться сверху вниз по строкам определения и находить первый образец (т. е. набор формальных параметров, который подходит под значений фактически переданных параметров в функцию) и выполнять определение, записанное с этим образцом. В данном случае вторая строка определения будет выбрана тогда, когда фактический параметр при вызове функции fac будет равен нулю.

В третьей строке помимо механизма сопоставления с образцами использовано охраняющее выражение — n > 0. Оно гарантирует, что функция не будет работать для отрицательных чисел, для которых факториал неопределён. Если отрицательное число будет передано в качестве фактического параметра в функцию fac, то программа остановится с сообщением об ошибке.

[править] Более сложные примеры

Простейший калькулятор для вычисления выражений в обратной польской записи может быть определён на языке 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

В данном определении функция свёртки (foldl) вызывается с фактическими параметрами [] (пустой список — начальное значение для свёртки), f (функция для интерпретации одного слова во входном выражении) и списка, полученного разбивкой исходной строки с выражением на слова, т. е. строки, отделённые друг от друга пробельными символами. В результате работы получается список, который содержаит промежуточные и окончательное значения, получаемые при вычислении входного выражения.

Другой пример показывает способ вычисления бесконечного списка чисел Фибоначчи за линейное время:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Бесконечный список создаётся при помощи механизма корекурсии — последующие значения списка вычисляются на основе имеющихся с начальными 0 и 1 в качестве первых двух элементов списка. Это определение является примером применения механизма ленивых вычислений, который является важнейшей частью языка Haskell. Для понимания того, как это определение работает, можно рассмотреть вычисление первых шести чисел Фибоначчи при помощи этой функции:

fibs         = 0 : 1 : 1 : 2 : 3 : 5 : ...
               +   +   +   +   +   +
tail fibs    = 1 : 1 : 2 : 3 : 5 : ...
               =   =   =   =   =   =
zipWith ...  = 1 : 2 : 3 : 5 : 8 : ...
fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 : ...

Та же самая функция может быть записана короче и более понятно при использовании расширения языка Haskell, которое реализовано в компиляторе GHC (параллелизация определителей списков):

fibs = 0 : 1 : [a + b | a <- fibs
                      | b <- tail fibs]

[править] Ссылки

В Викиучебнике есть обучающий текст
«Язык Haskell: О пользе и вреде лени»

• http://www.haskell.org/ — Очень насыщенный сайт, посвящённый функциональному программированию в общем и языку Haskell в частности. Содержит различные справочные материалы, список интерпретаторов и компиляторов Haskell’а (в настоящий момент все интерпретаторы и компиляторы бесплатны). Кроме того, имеется обширный список интересных ссылок на ресурсы по теории функционального программирования и другим языкам (Standard ML, Clean).
• http://www.haskell.ru/ — Полный перевод описания языка Haskell на русский язык.
• http://www.roman-dushkin.narod.ru/fp.html — Курс лекций по функциональному программированию, читаемый в МИФИ с 2001 года.
• http://kchri.narod.ru — Курс лекций и лабораторные работы на Haskell

[править] Литература

• Душкин Р. В. Функциональное программирование на языке Haskell. — М.: ДМК Пресс, 2006. С. 608. ISBN 5-94074-335-8