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

Содержимое удалено Содержимое добавлено
м Обернул код тэгом code
Строка 6:
В большинстве российских школ на уроках программирования изучают языки программирования [[w:Паскаль (язык программирования)|Паскаль]], [[:w:Си (язык программирования)|Си]] или [[:w:Java|Java]]. Все они суть [[w:Процедурное_программирование|императивные языки программирования]], в которых алгоритмы описываются как последовательность действий.
 
Здесь мы познакомимся с иным методом разработки программ — функциональным программированием, а также узнаем, что такое «ленивые» вычисления. Лень, как известно, — двигатель прогресса. Не удивительно, что лень сыграла значительную роль в развитии языков
программирования. Программисты ужасно ленивы! Они хотят для решения сложных задач писать простые короткие программы. В своей ленивости программисты уступают, пожалуй, только начальникам.
 
Программы на [[w:функциональный язык программирования|функциональном языке программирования]] выглядят как определения того, что нужно вычислить, а последовательность элементарных действий, на которые раскладывается программа, остаётся скрытой. Функциональное программирование позволяет реализовать давнюю мечту программистов: «Я описываю, ''что'' мне нужно получить, а уж компьютер сам должен догадаться, ''как'' это сделать».
Строка 30 ⟶ 31 :
Это одна из причин, почему язык Haskell называют «чистым». Переменных нет, но можно определять функции, которые не получают аргументов и возвращают числа. Именно так следует интерпретировать символы <code>x</code> и <code>y</code> в последнем примере — это функции, а не переменные. Знак равенства <code>=</code> имеет в Haskell принципиально другое значение, нежели операция присвоения <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 нет переменных и нет понятия состояния — множество значений всех текущих переменных. Как жить в таких необычных и жёстких условиях?! Рассмотрим ряд простых примеров.
Строка 41 ⟶ 44 :
В языке Haskell есть базовые типы: <code>Integer</code> (целое число), <code>Char</code> (символ), <code>Float</code> (число с плавающей точкой), <code>Rational</code> (дробное). Есть специальные конструкции «<code>()</code>», «<code>[]</code>» и «<code>-></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>.
 
Примеры типов:
Строка 84 ⟶ 87 :
определяется следующим образом:
 
<code>inc n = n+1</code> -- функция типа a->a </code>
 
Комментарии в Haskell начинаются с двух тире.
Строка 99 ⟶ 102 :
Аргументами этой функции являются два числа:
 
<code>
add :: Integer->Integer->Integer
add x y = x + y
</code>
 
Функцию <code>inc</code> можно было бы определить через функцию <code>add</code>:
 
<code>
inc = add 1
</code>
 
Зафиксировав один аргумент у функции <code>add</code>, мы получили
Строка 123 ⟶ 130 :
определить функцию <code>length</code>, которая измеряет длину списка элементов неопределённого типа:
 
<code>
length :: [a] -> Integer
length [] = 0
length (x:xs) = 1 + length xs
</code>
 
Строка «<code>length [] = 0</code>» означает, что длина пустого списка
Строка 137 ⟶ 146 :
а в качестве результата возвращает список элементов, к которым применена данная функция:
 
<code>
map :: (a->b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
</code>
 
Слева от знака «равно» символ «:» означает «отщепить»,
Строка 145 ⟶ 156 :
В частности выражение
 
<code>
map (add 10) [1,2,3] ) <math>\Rightarrow</math> [11,12,13].
</code>
 
означает «прибавить к каждому элементу списка [1,2,3] число 10».
Строка 153 ⟶ 166 :
а выражение «<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</code>:
 
<code>map f xs = [ f x | x <- xs].</code>
 
Это соответствует математической записи
Строка 177 ⟶ 190 :
Например, следующая конструкция
 
<code>ones = 1 : ones</code>
 
определяет функцию <code>ones</code>, которая возвращает бесконечную
Строка 184 ⟶ 197 :
выражения:
 
<code>
ones = 1 : 1 : ones,
ones = 1 : 1 : 1 : ones,
ones = 1 : 1 : 1 : 1 : ones,
....
</code>
 
 
Строка 207 ⟶ 222 :
целых чисел, которые больше либо равны ''n'':
 
<code>numsFrom n = n : numsFrom (n+1)</code>
 
Используя эту функцию, можно получить бесконечную
последовательность квадратов целых чисел:
 
<code>squares = map (^2) (numsfrom 0)</code>
 
Выражение «<code>(^2)</code>» означает функцию, которая возводит данное
Строка 224 ⟶ 239 :
Функцию <code>take</code> можно было определить рекурсивно:
 
<code>
take :: Integer -> [a] ->[b]
take 1 (x:xs) = [x]
take n (x:xs) = x : take (n-1) xs
</code>
 
А вот простой способ найти первые 5 степеней двоек:
Строка 238 ⟶ 255 :
Если ''h(x)=f(g(x))'', то в Haskell это запишется так:
 
<code>h = f . g</code>
 
Интересно заметить, что операция композиции может быть определена в Haskell
как обычная функция:
 
<code>
(.) :: (b->c) -> (a->b) -> (a->c)
f . g = \x -> f (g x)
</code>
 
Она получает на вход две функции и возвращает одну.
Строка 257 ⟶ 276 :
Введём следующие определения.
 
<code>
toDigsI :: Integer->[Integer]
toDigsI n | n == 0 = []
Строка 262 ⟶ 282 :
countUnits = sum . toDigsI
toDigits = reverse . toDigsI
</code>
 
Функция <code>toDigsI</code> для данного числа ''n''
Строка 294 ⟶ 315 :
а именно, списка разрядов двоичного разложения и списка степеней двойки:
 
<code>
powers = (2 ^ ) [0..]
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 (+) [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) . toDigsI</code>
 
Функция <code>filter</code> получает на вход булеву функцию (функцию, возвращающую «правду» или «ложь»)
Строка 330 ⟶ 353 :
 
— второй способ:
<code>toPowers =\n -> filter (/=) (zipWith (*) powers (toDigsI n))</code>
 
— третий способ:
<code>toPowers n = filter (/=) (zipWith (*) powers (toDigsI n))</code>
 
В этих способах мы явно вводим аргумент <code>n</code> и используем его в выражении и скобки располагаем уже совсем другим образом.
Строка 341 ⟶ 364 :
можно определить в Haskell тремя способами:
 
<code>
h = f1 . f2 . f3
h x = f1 (f2 (f3 x ) )
h = \x -> f1 (f2 (f3 x ) )
</code>
 
== Быстрая сортировка ==
Строка 353 ⟶ 378 :
 
--Быстрая сортировка на языке Haskell
 
<code>
qsort [] = []
qsort (x:xs) =
Строка 358 ⟶ 385 :
++ [x] ++
qsort [y | y <- xs, y>=x]
</code>
 
Поясним смысл этих строчек. Запись «<code>qsort [] = []</code>» означает, что если на вход дан пустой
Строка 369 ⟶ 397 :
 
Тот же самый алгоритм на языке Си занимает далеко не 4 строчки:
 
<code>/* Быстрая сортировка на языке Си */
void qsort( a, lo, hi )
int a[], hi, lo; {
Строка 397 ⟶ 425 :
qsort( a, l+1, hi );
}
}</code>
 
Таким образом, на языке Haskell многие алгоритмы можно запрограммировать существенно быстрее, нежели на Си или Паскале.