Язык Haskell: О пользе и вреде лени: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Строки объединены в абзацы, убраны лишние пробелы, исправлена орфография, грамматика, добавлены ссылки, вставлены формулы, прочее.
Строка 2: Строка 2:


[[Изображение:2_1.jpg|right|]]
[[Изображение:2_1.jpg|right|]]

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


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


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


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


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


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


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


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


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


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


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


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


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


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


В этом языке программирования есть базовые типы: <code>Integer</code> (целое число), <code>Char</code> (символ), <code>Float</code> (число с плавающей точкой), <code>Rational</code> (дробное). Есть специальные конструкции «<code>()</code>», «<code>[]</code>» и «<code>-></code>», которые позволяют определять новые типы на основании существующих.
В этом языке программирования есть базовые типы: <code>Integer</code> (целое число), <code>Char</code> (символ), <code>Float</code> (число с плавающей точкой), <code>Rational</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</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>. Соответственно можно задавать типы троек, четвёрок и произвольных наборов (кортежей) из ''n'' элементов.
Конструкция <code>(a, b)</code> означает тип пары элементов типов <code>a</code> и <code>b</code>. Соответственно можно задавать типы троек, четвёрок и произвольных наборов (кортежей) из <math>n</math> элементов.


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


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


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


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


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


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

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

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


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


Есть возможность явно типизировать функцию, указав перед определением функции строчку
<code>inc :: Integer->Integer</code>

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


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


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


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


Строка 107: Строка 93:
<code>inc = add 1</code>
<code>inc = add 1</code>


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


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


=== Пример 3 ===
=== Пример 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>[1,2,3]</code>, <code>(1:2:3)</code>и <code>(1:(2:(3)))</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] -> Integer
<code>length :: [a] -&gt; Integer
length [] = 0
length [] = 0
length (x:xs) = 1 + length xs</code>
length (x:xs) = 1 + length xs</code>


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


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


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


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


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


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


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


Это соответствует математической записи
Это соответствует математической записи
: <math>map(f,xs) = \left\{ f(x) | x\in xs \right\}.</math>


: <math>map(f,xs) = \left\{ f(x) | x \in xs \right\}</math>.
Конструкция «<code>x<-xs</code>» называется «генератором», её

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


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


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


Например, следующая конструкция
Например, следующая конструкция
Строка 180: Строка 142:
<code>ones = 1 : ones</code>
<code>ones = 1 : ones</code>


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


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



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


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

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


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


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


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


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


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


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


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


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


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


<code>take 5 powers where powers = map (2 ^) [1..] ''<math>\Rightarrow</math>'' [2,4,8,16,32].</code>
<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 это запишется так:
функций, которая обозначается с помощью точки.
Если ''h(x)=f(g(x))'', то в Haskell это запишется так:


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


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


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


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


Используя операцию композиции, напишем функцию <code>toDigits</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>countUnits</code>, которая считает число единиц в двоичной записи натурального числа.
В частности для ''n = 11'' функция <code>countUnits</code> должна вернуть ''3'',
так как ''11 = 1 + 2 + 8 = 2^0 + 2^1 + 2^3'', а для ''255'' ответ должен быть равен 8,
так как ''255=1 + 2 + 4 + ... + 64 + 128'' есть сумма восьми различных степеней двойки.


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


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


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


{|
{|
|<code>toDigsI (1+8+16)</code>
|<code>toDigsI (1 + 8 + 16)</code>
|<math>\Rightarrow</math>
|<math>\Rightarrow</math>
|[1,0,0,1,1],
|[1, 0, 0, 1, 1],
|-
|-
|<code>reverse [1,0,0,1,1]</code>
|<code>reverse [1, 0, 0, 1, 1]</code>
|<math>\Rightarrow</math>
|<math>\Rightarrow</math>
|[1,1,0,0,1],
|[1, 1, 0, 0, 1],
|-
|-
|<code>toDigits (1+8+16)</code>
|<code>toDigits (1 + 8 + 16)</code>
|<math>\Rightarrow</math>
|<math>\Rightarrow</math>
|[1,1,0,0,1],
|[1, 1, 0, 0, 1],
|-
|-
|<code>countUnits (1+8+16)</code>
|<code>countUnits (1 + 8 + 16)</code>
|<math>\Rightarrow</math>
|<math>\Rightarrow</math>
|3,
|3,
Строка 291: Строка 226:
|}
|}


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


Строка 298: Строка 232:
toPowers' = (zipWith (*) powers) . toDigsI</code>
toPowers' = (zipWith (*) powers) . toDigsI</code>


Вообще «<code>zipWith (*) [''<math>a_1, a_2, a_3, ...</math>''] [''<math>b_1,b_2,b_3,...</math> '']</code>» равно <code>[''<math>a_1*b_1, a_2*b_2, ... </math>'']</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>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' (16+8+1) <math>\Rightarrow</math> [1,0,0,8,16].</code>


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


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

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


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

и список, а возвращает список только из тех элементов, на которых значение
<code>toPowers (16 + 8 + 1) <math>\Rightarrow</math> [1, 8, 16]</code>.
этой функции равно «правде». В данном случае мы оставляем только ненулевые элементы:
<code>toPowers (16+8+1) <math>\Rightarrow</math> [1,8,16].</code>


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


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


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


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

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


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

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


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


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


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


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


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

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


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


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

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

</big>

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


[[Изображение:2_3.jpg|right|]]
[[Изображение:2_3.jpg|right|]]

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


Кроме того, активно развиваются алгоритмы трансляции функциональных языков, и по эффективности ассемблерного кода они постепенно начинают догонять императивные языки. А самое важное (но сложное для понимания) достоинство Haskell заключается в том, в <!--em-->трансляторы языка Haskell со временем можно будет добавить алгоритмы, которые по данным определениям функций<!--em--> смогут сами находить наиболее эффективные алгоритмы их вычисления, например, с использованием динамического программирования или жадных стратегий. Сегодня теория алгоритмов уже настолько развита, что можно выделить ряд шаблонов алгоритмических задач, и «научить» трансляторы функциональных языков программирования «видеть их» в определениях функций и применять известные эффективные алгоритмы вычисления.
Кроме того, активно развиваются алгоритмы трансляции
функциональных языков, и по эффективности ассемблерного кода они постепенно начинают догонять
императивные языки. А самое важное (но сложное для понимания) достоинство 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:Объектно-ориентированное программирование|объектно-ориентированным]] образом, а на объектно-ориентированных языках писать программы, следуя процедурному стилю программирования.
* Software AG, одна из главных программистских компаний Германии, разработала на функциональном языке экспертную систему Natural Expert. Пользователи с огромным удовольствием пишут для этой системы свои приложения.
Аналогично, практически на всех языках можно использовать функциональный стиль программирования. Это связано с тем, что создатели языков стараются сделать их достаточно универсальными, чтобы они успешно использовались при решении разных задач. Абсолютной универсальности достичь невозможно. Хотя есть некоторые удачные экземпляры, такие как язык Python, которые покрывают большой диапазон стилей программирования и в то же время имеют достаточно простой синтаксис. Универсальность языка не всегда является плюсом. Часто она влечёт за собой сложность синтаксиса и неоднозначность языковых конструкций. Конечно, сам язык (транслятор языка) все конструкции интерпретирует вполне однозначно, а вот программист, если язык слишком универсальный, может запутаться. Есть множество забавных примеров — коротких программ на Си и Си++, в которых не могут разобраться даже специалисты, пока не скомпилируют их, не запустят и не проведут часок-другой за их исследованием.
* Система работает на мейнфреймах IBM.
* Компания Ericsson разработала функциональный язык [http://www.erlang.org Erlang] для создания системы управления телефонными станциями.
* Исследователи в корпорации MITRE используют Haskell для [[:w:прототипирование|прототипирования]]{{ref|cons2}} приложений обработки цифровых сигналов.


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


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


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


==Ссылки==
== Ссылки ==


* [http://www.haskell.org/ Официальная страница языка Haskell]
* [http://www.haskell.org/ Официальная страница языка Haskell]
* [http://www.haskell.ru/ Полный перевод описания Haskell на русский язык]
* [http://www.haskell.ru/ Полный перевод описания Haskell на русский язык]
* [http://wtk.norilsk.net/pm/fp/haskell.html Введение в язык Haskell Михаила Потанина]
<!-- ссылка не работает: * [http://wtk.norilsk.net/pm/fp/haskell.html Введение в язык Haskell Михаила Потанина]-->


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


# {{note|cons1}} Когда в языке Си определяется переменная типа функции, необходимо указать типы аргументов функции и тип возвращаемого значения. Например, «<code> int (*)(int, int)</code>» — это тип функции, возвращающей число типа <code>int</code> и принимающей в качестве аргументов два числа типа <code>int</code>.
# {{note|cons1}} Когда в языке Си определяется переменная типа функции, необходимо указать типы аргументов функции и тип возвращаемого значения. Например, <code>int (*)(int, int)</code> — это тип функции, возвращающей число типа <code>int</code> и принимающей в качестве аргументов два числа типа <code>int</code>.
# {{note|cons2}} О сути и смысле прототипирования читайте соответствующую [[Словарик философствующего информатика#Прототипирование|статью]] «Словарика философствующего информатика».
# {{note|cons2}} О сути и смысле прототипирования читайте [[Словарик философствующего информатика#Прототипирование|соответствующую статью]] «[[Словарик философствующего информатика|Словарика философствующего информатика]]».


[[Категория:Журнал «Потенциал»]]
[[Категория:Журнал «Потенциал»]]

Версия от 12:00, 10 февраля 2008

Исходная версия статьи (Ворожцов А. В., «Язык Haskell: О пользе и вреде лени») была опубликована в журнале «Потенциал»
Файл:2 1.jpg

В большинстве российских школ на уроках программирования изучают языки программирования Паскаль, Си или Java. Все они суть императивные языки программирования, в которых алгоритмы описываются как последовательность действий.

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

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

Введение

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

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

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

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

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

1 + (x + y) * 2 where x = 1; y = 2;

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

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

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

x = x + 2

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

> x where x = x + 2
ERROR - stack overflow.

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

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

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

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

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

Примеры типов:

Integer -> Integer целочисленная функция целого аргумента;
[Integer] -> Float функция, которая получает список целых чисел, а возвращает действительное число типа Float;
Float -> Float -> Float функция, которая получает на входе два действительных числа и возвращает действительное число;
(Float, Integer) -> [(Float, Float)] функция, которая получает на входе пару чисел типа Float и Integer и возвращает список пар чисел типа Float.

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

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

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

Пример 1

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

inc n = n + 1   -- функция типа a -> a

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

inc (inc 3)  5.

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

inc :: Integer -> Integer

Пример 2

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

add :: Integer -> Integer -> Integer
add x y = x + y

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

inc = add 1

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

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

Пример 3

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

length :: [a] -> Integer
length [] = 0
length (x:xs) = 1 + length xs

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

Пример 4

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

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

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

map (add 10) [1, 2, 3] )  [11, 12, 13].

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

map (\ x -> x * x * x) [1, 2, 3])  [1, 8, 27].

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

map f xs = [ f x | x <- xs].

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

.

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

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

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

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

ones = 1 : ones

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

ones = 1 : 1 : ones,
ones = 1 : 1 : 1 : ones,
ones = 1 : 1 : 1 : 1 : ones,
…
Файл:2 2.jpg
Карикатура «Учись лениться!»

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

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

numsFrom n = n : numsFrom (n + 1)

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

squares = map (^2) (numsFrom 0)

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

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

take 5 squares  [0, 1, 4, 9, 16].

Функцию take можно было определить рекурсивно:

take :: Integer -> [a] -> [b]
take 1 (x:xs) = [x]
take n (x:xs) = x : take (n - 1) xs

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

take 5 powers where powers = map (2 ^) [1..]  [2, 4, 8, 16, 32].

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

Есть специальная операция композиции двух функций, которая обозначается с помощью точки. Если , то в Haskell это запишется так:

h = f . g

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

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

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

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

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

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

toDigsI :: Integer -> [Integer]
toDigsI n | n == 0    = []
          | otherwise = (n `mod` 2) : toDigsI (n `div` 2)
countUnits = sum . toDigsI
toDigits = reverse . toDigsI

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

toDigsI (1 + 8 + 16) [1, 0, 0, 1, 1],
reverse [1, 0, 0, 1, 1] [1, 1, 0, 0, 1],
toDigits (1 + 8 + 16) [1, 1, 0, 0, 1],
countUnits (1 + 8 + 16) 3,
countUnits 255 8.

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

powers = map (2 ^ ) [0..]
toPowers' = (zipWith (*) powers) . toDigsI

Вообще zipWith (*) [] [] равно [], где вместо звёздочки может стоять произвольная операция. В частности, zipWith (+) [1, 2, 3] [10, 100, 1000] даст в результате [11, 102, 1003]. В итоге имеем

toPowers' (16 + 8 + 1)  [1, 0, 0, 8, 16].

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

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

toPowers = (filter (/=0)) . (zipWith (*) powers) . toDigsI

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

toPowers (16 + 8 + 1)  [1, 8, 16].

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

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

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

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

toPowers = \n -> filter (/= 0) (zipWith (*) powers (toDigsI n))

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

toPowers n = filter (/= 0) (zipWith (*) powers (toDigsI n))

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

Если , , есть функции, то функцию , равную их композиции, () можно определить в Haskell тремя способами:

h = f1 . f2 . f3
h x = f1 (f2 (f3 x))
h = \x -> f1 (f2 (f3 x))

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

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

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

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

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

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);
}


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

Файл:2 3.jpg

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

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

Есть несколько интерпретаторов языка Haskell как под Windows, так и под Linux; все они бесплатны. Рекомендуем начать с маленького и удобного для обучения интерпретатора HUGS (http://haskell.org/hugs). Шаблон:ССЫЛКА

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

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

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

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

Создатели также утверждают, что программы на Haskell получаются более модульными и встраиваемыми и предоставляют больше возможностей для (повторного использования (англ. code reuse). В частности, представленная программа быстрой сортировки на Haskell (в отличие от программы на Си) может сортировать не только целые числа, но и числа типа Float и любые другие объекты, на которых определена операция сравнения.

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

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

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

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

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

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

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

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

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

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

Представленная искусная реализация функции быстрой сортировки на Си, придуманная Хоаром, безусловно, выигрывает по эффективности у реализации на Haskell (как по времени работы, так и по необходимой для вычислений памяти). Но код на Haskell существенно проще! Следует отметить, что обе реализации имеют сложность , то есть время работы на списке (массиве) длины растёт пропорционально , и в этом «асимптотическом смысле» обе реализации одинаково хороши.

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

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

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

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

  • Software AG, одна из главных программистских компаний Германии, разработала на функциональном языке экспертную систему Natural Expert. Пользователи с огромным удовольствием пишут для этой системы свои приложения.
  • Система работает на мейнфреймах IBM.
  • Компания Ericsson разработала функциональный язык Erlang для создания системы управления телефонными станциями.
  • Исследователи в корпорации MITRE используют Haskell для прототипирования[2] приложений обработки цифровых сигналов.

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

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

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

Ссылки

Примечания

  1. ^  Когда в языке Си определяется переменная типа функции, необходимо указать типы аргументов функции и тип возвращаемого значения. Например, int (*)(int, int) — это тип функции, возвращающей число типа int и принимающей в качестве аргументов два числа типа int.
  2. ^  О сути и смысле прототипирования читайте соответствующую статью «Словарика философствующего информатика».