Просмотр кода страницы Язык Haskell: О пользе и вреде лени

: <small>Исходная версия статьи (Ворожцов&nbsp;А.&nbsp;В., «Язык Haskell: О пользе и вреде лени») была опубликована в [[Журнал «Потенциал»|журнале «Потенциал»]]</small>

В большинстве российских школ на уроках программирования изучают языки программирования [[w:Паскаль (язык программирования)|Паскаль]], [[:w:Си (язык программирования)|Си]] или [[:w:Java|Java]]. Все они суть [[w:Процедурное_программирование|императивные языки программирования]], в которых алгоритмы описываются как последовательность действий.

Здесь мы познакомимся с иным методом разработки программ — [[w:Функциональное программирование|функциональным программированием]], а также узнаем, что такое [[w:Ленивые вычисления|«ленивые» вычисления]]. Лень, как известно, — двигатель прогресса. Не удивительно, что лень сыграла значительную роль в развитии языков программирования. Программисты ужасно ленивы! Они хотят для решения сложных задач писать простые короткие программы. В своей ленивости программисты уступают, пожалуй, только начальникам.

Программы на [[w:функциональный язык программирования|функциональном языке программирования]] выглядят как определения того, что нужно вычислить, а последовательность элементарных действий, на которые раскладывается программа, остаётся скрытой. Функциональное программирование позволяет реализовать давнюю мечту программистов: «Я описываю, ''что'' мне нужно получить, а уж компьютер сам должен догадаться, ''как'' это сделать».

== Введение ==

Язык программирования [[:w:Haskell|Haskell]] — это «ленивый» функциональный язык программирования с [[:w:полиморфизм в языках программирования|полиморфизмом типов]]. Он достаточно необычен: других таких ленивых и настолько [[w:Чистота языка программирования|чистых]] функциональных языков нет! Что означают слова «чистый», «функциональный» и «полиморфизм типов», в двух словах не объяснить.

Язык Haskell (Ха́скель) функциональный, поскольку в нём основное понятие — это [[w:Функция (программирование)|функции]]. Но функции есть в любом языке программирования! В языках Паскаль, [[w:BASIC|Бейсик]], Си, [[w:Python|Питон (Python)]]… — везде есть понятие функции, и везде мы можем определять свои функции. Но не торопитесь делать выводы. Речь идёт не только о формальных возможностях языка, но и о ''стиле составления программ''. В функциональных языках программирования с функциями можно работать так же, как с числами или строковыми переменными. Например, представьте себе функцию, которая в качестве аргумента принимает некоторую функцию, а в качестве результата возвращает другую функцию. Возможность создавать переменные типа функций в языках Си/[[w:C++|Си++]], Паскаль, [[w:Object Pascal|Object Pascal]] есть{{ref|cons1}}, но ею пользуются крайне редко. Перечисленные языки ''процедурные'', и они не приспособлены для того, чтобы писать программы в функциональном стиле.

Функциональный программист мыслит в терминах функций и зависимостях функций друг от друга. Императивный программист мыслит в терминах действий и объединения последовательностей действий в процедуры.

Написать программу на функциональном языке значит записать выражение, которое должно быть вычислено, а также описать функции, которые используются в этом выражении. Акцент при этом делается не на то, в какой последовательности и какие команды будут исполняться, а на то, что́ должно быть получено и как функции выражаются друг через друга. Очень типично, когда «функциональный программист» даже не воображает последовательность выполнения элементарных действий своей программы. Функциональным образом мы мыслим, когда работаем в [[w:Табличный процессор|табличном процессоре]]: просто описываем зависимости ячеек друг от друга, и в одной из ячеек получаем нужный нам результат.

Программа на языке Haskell представляет собой одно выражение. Причём можно явно выделить две части: до слова <code>where</code> (переводится как «где») и после него. Например, программа

 <code>1 + (x + y) * 2 where x = 1; y = 2;</code>

в качестве результата вернёт 7. Функции, которые используются в выражении, должны быть определены после <code>where</code>.

'''Переменных в Haskell просто нет'''.

Это одна из причин, почему язык Haskell называют «[[w:Чистота языка программирования|чистым]]». Переменных нет, но можно определять функции, которые не получают аргументов и возвращают числа. Именно так следует интерпретировать символы <code>x</code> и <code>y</code> в последнем примере — это функции, а не переменные. Знак равенства <code>=</code> имеет в Haskell принципиально другое значение, нежели операция присвоения <code>=</code> в языке Си (или аналогичная операция <code>:=</code> в Паскале). В языке Си эта операция интерпретируется следующим образом: вычислить то, что указано справа от знака «равно», и результат поместить в переменную (ячейку памяти), которая указана слева от знака «равно». Строка

 <code>x = x + 2</code>

в языке Си интерпретируется как команда «увеличить значение переменной <code>x</code> на 2». В языке Haskell смысл этой команды совсем другой — «определить функцию <code>x</code> следующим образом: результат функции равен сумме результата вычисления функции <code>x</code> и числа 2». То есть в языке Haskell эта строка является определением рекурсивной функции с именем <code>x</code>!!! Функция <code>x</code> определена через себя, и использование этой функции приведёт к бесконечной цепочке рекурсивных вызовов и к ошибке переполнения стека «stack overflow»:

 <code>> x where x = x + 2
 ERROR - stack overflow.</code>

В языке Haskell нет переменных и нет понятия состояния — множества значений всех текущих переменных. Как жить в таких необычных и жёстких условиях?! Рассмотрим ряд простых примеров.

В этом языке программирования есть базовые типы: <code>Integer</code> (целое число), <code>Char</code> (символ), <code>Double</code> (число с плавающей точкой, ранее обозначалось <code>Float</code>). Есть специальные конструкции <code>()</code>, <code>[]</code> и <code>-&gt;</code>, которые позволяют определять новые типы на основании существующих.

Пусть <code>a</code> и <code>b</code> являются некоторыми типами данных. Тогда конструкция <code>[a]</code> означает новый тип — список элементов типа <code>a</code>. В частности тип <code>String</code> есть синоним типа <code>[Char]</code>.

Конструкция <code>(a, b)</code> означает тип пары элементов типов <code>a</code> и <code>b</code>. Соответственно можно задавать типы троек, четвёрок и произвольных наборов (кортежей) из <math>n</math> элементов.

Конструкция <code>a -&gt; b</code> соответствует типу функций, которые получают на входе элемент типа <code>a</code> и возвращают элемент типа <code>b</code>.

Примеры типов:
{| style = "padding:0.8em; border:thin solid #888; margin-left:1em;"
 |<code>Integer -&gt; Integer</code>
 |целочисленная функция целого аргумента;
 |-
 |<code>[Integer] -&gt; Float</code>
 |функция, которая получает список целых чисел, а возвращает действительное число типа <code>Float</code>;
 |-
 |<code>Float -&gt; Float -&gt; Float</code>
 |функция, которая получает на входе два действительных числа и возвращает действительное число;
 |-
 |<code>(Float, Integer) -&gt; [(Float, Float)]</code>
 |функция, которая получает на входе пару чисел типа <code>Float</code> и <code>Integer</code> и возвращает список пар чисел типа <code>Float</code>.
 |}

Особый интерес представляет тип <code>Float -&gt; Float -&gt; Float</code>. Его можно
интерпретировать и по-другому: функция, которая получает одно число типа <code>Float</code> и возвращает функцию типа <code>Float -&gt; Float</code>. Действительно, если у функции с двумя аргументами зафиксировать один аргумент, то получится функция одного аргумента.

При конструировании типов можно использовать круглые скобки, чтобы обозначить неделимые элементы. Например, тип <code>(Float -&gt; Float) -&gt; Float</code> соответствует функции, которая получает на вход функцию типа <code>Float -&gt; Float</code> и возвращает действительное число.

Интересно заметить, что при конструировании новых типов с помощью операций <code>[a]</code>, <code>(a, b)</code> и <code>a -&gt; b</code> не обязательно вместо <code>a</code> и <code>b</code> подставлять конкретные существующие типы. Можно использовать маленькие латинские буквы, означающие произвольный тип. В частности, тип <code>a -&gt; b -&gt; [(a, b)]</code> означает функцию, которая получает на входе два элемента типов <code>a</code> и <code>b</code> и возвращает список пар элементов типа <code>a</code> и <code>b</code>.

=== Пример 1 ===

Функция <code>inc</code> увеличивает число на единицу. Она определяется следующим образом:

 <code>inc n = n + 1   -- функция типа (Num a) => a -&gt; a</code>

Здесь следует отметить, что комментарии в Haskell начинаются с двух дефисов. Выражение <code>inc (inc 3)</code> будет редуцировано (упрощено, вычислено) до 5. Этот факт мы будем записывать так:

 <code>inc (inc 3) <math>\Rightarrow</math> 5.</code>

Есть возможность явно типизировать функцию, указав перед определением функции строчку

 <code>inc :: Integer -&gt; Integer</code>

=== Пример 2 ===

Функция <code>add</code> находит сумму данных ей чисел. Аргументами этой функции являются два числа:

 <code>add :: Integer -&gt; Integer -&gt; Integer
 add 3 5 where add x y = x + y</code>

Функцию <code>inc</code> можно было бы определить через функцию <code>add</code>:

 <code>inc = add 1</code>

Зафиксировав один аргумент у функции <code>add</code>, мы получили функцию с одним аргументом.

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

=== Пример 3 ===

Есть два способа обозначения списков — квадратные скобки, в которых перечислены элементы через запятую, или круглые скобки, в которых элементы разделены двоеточием. В частности записи <code>[1, 2, 3]</code>, <code>(1:2:3:[])</code> и <code>(1:(2:(3:([]))))</code> эквивалентны. Символ двоеточие '<code>:</code>' означает операцию присоединения элемента к списку слева. Пусть <code>x</code> есть элемент, а <code>xs</code> — некоторый список элементов того же типа, что и <code>x</code>. Тогда выражение <code>x:xs</code> есть список, полученный из списка <code>xs</code> с помощью добавления элемента <code>x</code> в начало. Но интересно заметить, что конструкцию <code>(x:xs)</code> можно использовать и слева от знака «равно», где она соответствует операции отщепления первого элемента от списка. Это позволяет рекурсивно определить функцию <code>length</code>, которая измеряет длину списка элементов неопределённого типа:

 <code>length :: [a] -&gt; Integer
 length [] = 0
 length (x:xs) = 1 + length xs</code>

Строка <code>length [] = 0</code> означает, что длина пустого списка равна 0. Строка <code>length (x:xs) = 1 + length xs</code> означает, что длина списка, от которого отщепили один элемент, равна 1 плюс длина оставшегося списка. Это пример достаточно медленный, но показательный.

=== Пример 4 ===

Рассмотрим функцию <code>map</code>, которая получает на вход функцию и список элементов, а в качестве результата возвращает список значений функции, применённой к каждому элементу входного списка:

 <code>map :: (a -&gt; b) -&gt; [a] -&gt; [b]
 map f [] = []
 map f (x:xs) = f x : map f xs</code>

Слева от знака «равно» символ <code>:</code> означает «отщепить», а справа от знака «равно» — «присоединить». В частности выражение

 <code>map (add 10) [1, 2, 3]  <math>\Rightarrow</math> [11, 12, 13].</code>

означает «прибавить к каждому элементу списка <code>[1, 2, 3]</code> число 10». Интересно, что функции можно конструировать «на лету» прямо в выражениях. Для фиксирования аргумента функции используется символ <code>\</code>. В частности <code>\ x -&gt; x * x * x</code> означает функцию <math>f(x) = x^3</math>, а выражение <code>(\ x -&gt; x * x * x) 3</code> равно 27.

 <code>map (\ x -&gt; x * x * x) [1, 2, 3] <math>\Rightarrow</math> [1, 8, 27].</code>

Есть другой способ определения функции <code>map</code>:

 <code>map f xs = [ f x | x &lt;- xs].</code>

Это соответствует математической записи

: <math>map(f,xs) = \left\{ f(x) | x \in xs \right\}</math>.

Конструкция <code>x &lt;- xs</code> называется «генератором», её следует интерпретировать как «элемент <code>x</code> берётся из списка <code>xs</code>».

== Работа с бесконечными последовательностями ==

А сейчас мы перейдём к вещам, пугающим и шокирующим «императивных» программистов. Хотите верьте, хотите — нет, но в Haskell есть возможность оперировать бесконечными объектами. Можно завести функцию, которая возвращает бесконечную последовательность [[w:Натуральное число|натуральных чисел]] или бесконечную последовательность [[w:Числа Фибоначчи|чисел Фибоначчи]], или какую-нибудь другую бесконечную последовательность.

Например, следующая конструкция

 <code>ones = 1 : ones</code>

определяет функцию <code>ones</code>, которая возвращает бесконечную последовательность единичек. Действительно, если мы начнём раскрывать это рекурсивное определение, то получим такие выражения:

 <code>ones = 1 : 1 : ones,
 ones = 1 : 1 : 1 : ones,
 ones = 1 : 1 : 1 : 1 : ones,
 …</code>

Это последовательность, которая остаётся равна сама себе после добавления единицы в начало. Неленивые языки, которым не терпитcя сделать сразу то, что от них просят, очень скоро получат ошибку исполнения (например, ошибку переполнение памяти). Ленивый язык Haskell не спешит раскрывать определение, данное ему справа от знака «равно», а раскрывает его по мере необходимости. Такое «равно» называют «ленивым равно», оно по сути означает определение функции, а не операцию присваивания. Есть функциональные языки, в которых есть два типа «равно» — ленивое (определение функции) и неленивое (вычисление выражения справа и присваивание результата переменной, что слева от знака «равно»). Например, в языке [[w:Mathematica|Mathematica]] (http://wolfram.com) для определения функций используется <code>:=</code>, а для присваивания — просто <code>=</code>.

Рассмотрим функцию <code>numsFrom</code>, которая получает один аргумент — целое число <code>n</code> — и возвращает список всех целых чисел, которые больше либо равны <code>n</code>:

 <code>numsFrom n = n : numsFrom (n + 1)</code>

Используя эту функцию, можно получить бесконечную последовательность квадратов целых чисел:

 <code>squares = map (^2) (numsFrom 0)</code>

Выражение <code>(^2)</code> означает функцию, которая возводит данное число в квадрат.

Получить первые элементы последовательности можно с помощью функции <code>take</code>:

 <code>take 5 squares <math>\Rightarrow</math> [0, 1, 4, 9, 16].</code>

Функцию <code>take</code> можно определить рекурсивно:

 <code>take :: Integer -&gt; [a] -&gt; [b]
 take 1 (x:xs) = [x]
 take n (x:xs) = x : take (n - 1) xs</code>

А вот простой способ найти первые 5 степеней двойки:

 <code>take 5 powers where powers = map (2 ^) [1..] <math>\Rightarrow</math> [2, 4, 8, 16, 32].</code>

== Задача разложения числа на степени двойки ==

Есть специальная операция композиции двух функций, которая обозначается с помощью точки. Если <math>h(x)=f(g(x))</math>, то в Haskell это запишется так:

 <code>h = f . g</code>

Интересно заметить, что операция композиции может быть определена в Haskell как обычная функция:

 <code>(.) :: (b -&gt; c) -&gt; (a -&gt; b) -&gt; (a -&gt; c)
 f . g = \x -&gt; f (g x)</code>

Она получает на вход две функции и возвращает одну.

Используя операцию композиции, напишем функцию <code>toDigits</code>, которая для данного целого числа находит список разрядов двоичного представления, и функцию <code>countUnits</code>, которая считает число единиц в двоичной записи натурального числа.

В частности для <math>n = 11</math> функция <code>countUnits</code> должна вернуть <math>3</math>, так как <math>11 = 1 + 2 + 8 = 2^0 + 2^1 + 2^3</math>, а для <math>255</math> ответ должен быть равен 8, так как <math>255=1 + 2 + 4 + \dots + 64 + 128</math> есть сумма восьми различных степеней двойки.

Введём следующие определения.

 <code>toDigits :: Integer -&gt; [Integer]
 toDigits n | n == 0    = []
           | otherwise = (n `mod` 2) : toDigits (n `div` 2)
 countUnits = sum . toDigits
 toDigits = reverse . toDigits</code>

Функция <code>toDigits</code> для данного числа <math>n</math> находит список его разрядов в двоичном представлении в направлении справа налево. Стандартная функция <code>reverse</code> обращает список: получает на вход список и возвращает тот же список, в котором элементы идут в обратном порядке, начиная с последнего до первого:

{|
 |<code>toDigits (1 + 8 + 16)</code>
 |<math>\Rightarrow</math>
 |[1, 0, 0, 1, 1],
 |-
 |<code>reverse [1, 0, 0, 1, 1]</code>
 |<math>\Rightarrow</math>
 |[1, 1, 0, 0, 1],
 |-
 |<code>toDigits (1 + 8 + 16)</code>
 |<math>\Rightarrow</math>
 |[1, 1, 0, 0, 1],
 |-
 |<code>countUnits (1 + 8 + 16)</code>
 |<math>\Rightarrow</math>
 |3,
 |-
 |<code>countUnits 255</code>
 |<math>\Rightarrow</math>
 |8.
 |}

Для того, чтобы найти сами степени двойки, в сумму которых разлагается число, можно использовать операцию <code>zipWith (*)</code> поэлементного умножения двух списков,
а именно, списка разрядов двоичного разложения и списка степеней двойки:

 <code>powers = map (2 ^ ) [0..]
 toPowers' = zipWith (*) powers . toDigits</code>

Вообще <code>zipWith (*) [<math>a_1, a_2, a_3, \dots</math>] [<math>b_1,b_2,b_3,\dots</math>]</code> равно <code>[<math>a_1*b_1, a_2*b_2, \dots</math>]</code>, где вместо звёздочки может стоять произвольная операция. В частности, <code>zipWith (+) [1, 2, 3] [10, 100, 1000]</code> даст в результате <code>[11, 102, 1003]</code>. В итоге имеем

 <code>toPowers' (16 + 8 + 1) <math>\Rightarrow</math> [1, 0, 0, 8, 16].</code>

Осталось добавить шаг фильтрации нулевых элементов:

— первый способ:

 <code>toPowers = filter (/=0) . zipWith (*) powers . toDigits</code>

Функция <code>filter</code> получает на вход булеву функцию (функцию, возвращающую «правду» или «ложь») и список, а возвращает список только из тех элементов, на которых значение этой функции равно «правде». В данном случае мы оставляем только ненулевые элементы:

 <code>toPowers (16 + 8 + 1) <math>\Rightarrow</math> [1, 8, 16]</code>.

Функция <code>zipWith</code> получает три аргумента. Если указано только два аргумента, то она превращается в функцию от одного аргумента. Это позволяет использовать выражение <code>zipWith (*) powers</code> как функцию от одного аргумента и поместить в цепочку композиции с функцией <code>toDigits</code>. Аналогичная ситуация с функцией <code>filter</code>: мы задали для неё первый аргумент — <code>(/=0)</code> — это функция сравнения с нулём. Второй аргумент остался неопределённым. Он достанется ей по цепочке как значение
функции <code>zipWith (*) powers</code> на том, что вернёт ей функция <code>toDigits</code>, применённая к тому, что даст пользователь в качестве аргумента функции <code>toPowers</code>.

Точки в определении функции <code>toPowers</code> играют роль операции «|» (pipe) в стандартной оболочке Linux. С помощью этой операции происходит передача результатов вычисления одной функции на вход другой. В нашем случае была выстроена цепочка из трёх функций.

Функцию <code>toPowers</code> можно определить и по-другому:

— второй способ:

 <code>toPowers = \n -&gt; filter (/= 0) (zipWith (*) powers (toDigits n))</code>

— третий способ:

 <code>toPowers n = filter (/= 0) (zipWith (*) powers (toDigits n))</code>

В этих способах мы явно вводим аргумент <code>n</code> и используем его в выражении, и скобки располагаем уже совсем другим образом.

Если <math>f_1</math>, <math>f_2</math>, <math>f_3</math> есть функции, то функцию <math>h</math>, равную их композиции, (<math>h(x) = f_1(f_2(f_3(x)))</math>) можно определить в Haskell тремя способами:

 <code>h = f1 . f2 . f3
 h x = f1 (f2 (f3 x))
 h = \x -&gt; f1 (f2 (f3 x))</code>

== Быстрая сортировка ==

Выше мы рассматривали простые примеры, от которых пока далеко до реальных промышленных задач. А сейчас мы рассмотрим первый серьёзный алгоритм — [[w:Быстрая сортировка|быструю сортировку Хоара]]. Несмотря на свою «серьёзность», выглядит он подозрительно просто:

 <code>qsort [] = []
 qsort (x:xs) = qsort [y | y &lt;- xs, y < x ] ++ [x] ++ qsort [y | y &lt;- xs, y >= x]
 </code>

Запись <code>qsort [] = []</code> означает, что если на вход дан пустой список <code>[]</code>, то и в результате будет пустой список. В следующей строчке рассматривается случай,
когда список не пуст и от него можно отщепить первый элемент <code>x</code>. Оставшаяся часть списка обозначена как <code>xs</code>. Выражение <code>[y | y &lt;- xs, y < x ]</code> равно множеству элементов списка <code>xs</code>, которые строго меньше <code>x</code>. Выражение <code>[y | y &lt;- xs, y >= x ]</code> равно элементам списка <code>xs</code>, которые больше либо равны <code>x</code>. Далее мы сортируем эти два списка с помощью самой же функции <code>qsort</code> и склеиваем три списка: список <code>qsort [y | y &lt;- xs, y < x]</code>, одноэлементный список <code>[x]</code> и список <code>qsort [y | y &lt;- xs, y >= x]</code>.

Тот же алгоритм на языке Си (только для целых чисел) требует гораздо больше кодирования:

<syntaxhighlight lang="C">void qsort(int *ds, int *de, int *ss){
    int vl = *ds, *now = ds + 1, *inl = ss, *ing = ss + (de - ds);
    if(de <= ds + 1) return;
    for(; now != de; ++now){
        if(*now <= vl) *inl++ = *now;
        else *ing-- = *now;
    }
    *++inl = vl;
    qsort(ds, ds + (inl - ss), ss);
    qsort(ds + (inl - ss), de, inl + 1);
}</syntaxhighlight>


Подобным образом на Haskell многие алгоритмы можно записать гораздо короче, нежели на Си, Паскале да и вообще любом императивном языке.

Извините, если не весь изложенный материал вам понятен. В одной обзорной статье сложно дать полноценное введение в язык программирования. Большинство приведённых примеров интуитивно ясны, но их, безусловно, недостаточно, чтобы самому начать писать программы на Haskell. У автора остаётся надежда на то, что вы заинтересуетесь и опробуете все эти примеры, установив на своем локальном компьютере интерпретатор языка Haskell, и прочитаете обучающие материалы, представленные на сайтах http://haskell.org/, <!-- ссылка не работает: http://wtk.norilsk.net/pm/fp/haskell.html, -->http://www.haskell.ru/.

== Дистрибутивы Haskell ==

Есть несколько интерпретаторов языка Haskell как под [[w:Microsoft Windows|Windows]], так и под [[w:GNU/Linux|Linux]]; все они бесплатны. Рекомендуем начать с маленького и удобного для обучения интерпретатора [[w:HUGS|HUGS]] (http://haskell.org/hugs).{{Ссылка|HUGS 98}}

== Зачем нужно функциональное программирование? ==

Создатели языка Haskell очень гордятся тем, что в нём используется чистая функциональная парадигма. Они утверждают, что на Haskell
* проще писать сложные программы, и программы получаются существенно короче;
* программы имеют ясный, легко читаемый вид; их можно легко понять, даже не зная многих деталей языка Haskell;
* делается меньше ошибок, так как синтаксис языка Haskell защищает программиста от совершения многих типичных ошибок;
* короче и проще этап проектирования и разработки программ: программист должен просто понять, что ему нужно, и затем описать это на формальном математическом языке;
* создаются адаптивные, легко изменяемые и расширяемые программы.

Кроме того, отмечается, что благодаря строгой типизации языка, в программах на Haskell не случается системных ошибок и не бывает аварийных ситуаций (сore dump).

Создатели также утверждают, что программы на Haskell получаются более [[w:Модульность (программирование)|модульными]] и встраиваемыми и предоставляют больше возможностей для [[w:Повторное использование кода|повторного использования]] ({{lang-en|code reuse}}). В частности, представленная программа быстрой сортировки на Haskell (в отличие от программы на Си) может сортировать не только целые числа, но и числа типа <code>Float</code> и любые другие объекты, на которых определена операция сравнения.

Язык Haskel имеет высокий уровень абстракции. Грубо говоря, под этим имеется в виду возможность создавать функции, которые возвращают функции. Но более точно сказать, что язык Haskell включает в себя абстрактное [[w:Лямбда-исчисление|лямбда-исчисление]] (λ-исчисление). Мощь, которую предоставляет это исчисление, ещё не до конца осознана программистами, и не в полной мере используется на практике.

Обратите внимание на то, что в списке достоинств не указаны такие моменты, как эффективность кода, экономичное использование памяти, или скорость работы программ. Это не потому, что этих достоинств нет. Просто сегодня акценты индустрии языков программирования cместились в другую сторону. Уже мало кого интересует скорость работы программ или возможность писать супероптимальный код. Ясно, что на практике возникает необходимость ускорить работу некоторых функций, так как они часто вызываются и/или играют важную роль. Но таких мест в коде не много и им можно уделить отдельное внимание. Например, важные функции, от которых требуется высокая скорость работы, можно реализовать на языке Си, оформить в виде библиотеки и подключить к основному приложению, написанному на удобном для человека языке программирования (языке быстрой разработки), подобному Haskell или Python.

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

== Встроенное управление памятью ==

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

Во многих сложных программах возникает необходимость динамического выделения памяти. Динамическое выделение памяти отличается от статического тем, что размер необходимой памяти узнаётся во время выполнения программы, и выполняется запрос к операционной системе выделить нужное количество байт.

В языке Си для этого используется функция <code>malloc</code>. Программист ответственен за возвращение этой памяти обратно системе. Когда потребность в выделенной памяти отпадает, он должен послать запрос возвращения (освобождения) памяти. Несбалансированные запросы по выделению и освобождению памяти являются частыми причинами неработоспособности программ. Кроме того, запрос выделения памяти достаточно «дорогой», и программисты на Си часто увлекаются написанием своих собственных менеджеров памяти, которые сначала запрашивают у системы много памяти, а потом начинают распределять внутри себя эту память по необходимости.

Функциональные языки освобождают программиста от этой непростой обязанности. Память выделяется неявно, автоматически, а специальный [[w:Сборка мусора|сборщик мусора]] (garbage collector) возвращает системе неиспользуемые куски памяти. Оптимальные алгоритмы управления памятью сложны, но сегодня уже достаточно хорошо проработаны. Использование этих алгоритмов не сильно увеличивают время работы программы в целом (в сравнении с тем, когда программист сам, по-умному, занимается выделением и освобождением памяти).

== Когда Си лучше? ==

Конечно, не всё «цветочки да бабочки». У функциональных языков есть свои недостатки. Считается, что программы, написанные на функциональных языках программирования, работают существенно медленнее, нежели на императивных. Поэтому суть пользы и вреда лени в данном случае сформулируем так: «Программы пишутся быстрее, но работают они медленнее». Это прекрасный компромисс, поскольку человеко-часы часто существенно дороже часов работы компьютера!

Представленная искусная реализация функции быстрой сортировки на Си, придуманная [[w:Хоар, Чарльз Энтони Ричард|Хоаром]], безусловно, выигрывает по эффективности у реализации на Haskell (как по времени работы, так и по необходимой для вычислений памяти). Но код на Haskell существенно проще! Следует отметить, что обе реализации имеют сложность <math>O(n\log n)</math>, то есть время работы на списке (массиве) длины <math>n</math> растёт пропорционально <math>n\log n</math>, и в этом «асимптотическом смысле» обе реализации одинаково хороши.

Кроме того, активно развиваются алгоритмы трансляции функциональных языков, и по эффективности ассемблерного кода они постепенно начинают догонять императивные языки. А самое важное (но сложное для понимания) достоинство Haskell заключается в том,что в <!--em-->трансляторы языка Haskell со временем можно будет добавить алгоритмы, которые по данным определениям функций<!--em--> смогут сами находить наиболее эффективные алгоритмы их вычисления, например, с использованием динамического программирования или жадных стратегий. Сегодня теория алгоритмов уже настолько развита, что можно выделить ряд шаблонов алгоритмических задач, и «научить» трансляторы функциональных языков программирования «видеть их» в определениях функций и применять известные эффективные алгоритмы вычисления.

Конечно, язык Си предпочтительнее в целом ряде случаев: [[w:Системное программирование|системное программирование]], [[w:Драйвер|драйверы устройств]], приложения, от которых требуется высокая производительность, например, [[w:Компьютерная игра|компьютерные игры]] с качественной графикой и другие. Но всё это довольно специальные случаи. Большинство компьютерных приложений не требует высокой скорости работы. Часто оптимизация требуется лишь для небольшого числа функций, а остальная логика может быть запрограммирована на удобном для человека языке программирования, пусть не совсем эффективном с точки зрения скорости работы и использования памяти.

== Где используется функциональное программирование ==

Функциональные языки программирования используются во многих серьезных системах. Перечислим некоторые из них.

* [[w:Software AG|Software AG]], одна из главных программистских компаний Германии, разработала на функциональном языке экспертную систему Natural Expert. Пользователи с огромным удовольствием пишут для этой системы свои приложения.
* Система работает на [[w:Мейнфрейм|мейнфреймах]] [[w:IBM|IBM]].
* Компания [[w:Ericsson|Ericsson]] разработала функциональный язык [http://www.erlang.org/ Erlang] для создания системы управления телефонными станциями.
* Исследователи в корпорации MITRE используют Haskell для [[w:Прототипирование|прототипирования]]{{ref|cons2}} приложений обработки цифровых сигналов.

Для многих программистов не секрет, что на процедурных языках можно писать [[w:Объектно-ориентированное программирование|объектно-ориентированным]] образом, а на объектно-ориентированных языках писать программы, следуя процедурному стилю программирования.
Аналогично, практически на всех языках можно использовать функциональный стиль программирования. Это связано с тем, что создатели языков стараются сделать их достаточно универсальными, чтобы они успешно использовались при решении разных задач. Абсолютной универсальности достичь невозможно. Хотя есть некоторые удачные экземпляры, такие как язык Python, которые покрывают большой диапазон стилей программирования и в то же время имеют достаточно простой синтаксис. Универсальность языка не всегда является плюсом. Часто она влечёт за собой сложность синтаксиса и неоднозначность языковых конструкций. Конечно, сам язык (транслятор языка) все конструкции интерпретирует вполне однозначно, а вот программист, если язык слишком универсальный, может запутаться. Есть множество забавных примеров — коротких программ на Си и Си++, в которых недостаточно опытные специалисты даже не могут разобраться, пока не скомпилируют их, не запустят и не проведут часок-другой за их исследованием.

Ограничения, которые вы встретите в языке программирования Haskell, следует уважать. Они спасают вас от множества проблем, которые могли бы возникнуть, если бы вы писали на слишком универсальном языке программирования типа Си++.

== Дальнейшее чтение ==

* В Википедии: [[w:Haskell|Haskell]]
* В Викиучебнике:
** [[Теория чисел и язык Haskell]]
** [[Введение в язык Scheme для школьников]]
** [[Основы функционального программирования]]

== Ссылки ==

* [http://www.haskell.org/ Официальная страница языка Haskell]
* [http://www.haskell.ru/ Полный перевод описания Haskell на русский язык]

== Примечания ==

# {{note|cons1}} Когда в языке Си определяется переменная типа функции, необходимо указать типы аргументов функции и тип возвращаемого значения. Например, <code>int (*)(int, int)</code> — это тип функции, возвращающей число типа <code>int</code> и принимающей в качестве аргументов два числа типа <code>int</code>. В языке C++, однако, можно описывать шаблоны функций без указания конкретных типов, например: <code>template<class T1, class T2>T2 f(T1 x, T2 y);</code> - функция, принимающая два аргумента и возвращающая значение того же типа, что и второй аргумент.
# {{note|cons2}} О сути и смысле прототипирования читайте [[Словарик философствующего информатика#Прототипирование|соответствующую статью]] «[[Словарик философствующего информатика|Словарика философствующего информатика]]».

[[Категория:Haskell (язык программирования)]]
[[Категория:Функциональное программирование]]
[[Категория:Журнал «Потенциал»]]
{{Готовность|75%}}