====== Haskell: введение в функциональное программирование =====
Автор: к.ф.-м.н., доцент кафедры информатики //В.Н. Власов//
----
**[[http://wiki.nsunc.com/_export/html/haskell|удобный для просмотра вид]]**
===== Ссылки на важные ресурсы по Haskell =====
- Основной сайт разработчиков (англ.) [[http://haskell.org|Haskell.org]] (есть небольшой раздел на русском языке).
- Сайт с переводом основной документации по синтаксису языка (рус.) [[http://www.haskell.ru|Haskell-98]].
- Ряд статей на сайте [[http://rsdn.org|RSDN.org]] (рус.) о декларативном, функциональном программировании и о Haskell, в частности [[http://rsdn.org/summary/3857.xml|Декларативное программирование ]]. Особый интерес для начинающих представляют статьи [[http://rsdn.org/article/haskell/haskell_part1.xml|Мягкое введение в Haskell-1]] и [[http://rsdn.org/article/haskell/haskell_part2.xml|Мягкое введение в Haskell-2]], [[http://rsdn.org/article/haskell/typesH.xml|Функциональные типы и композиция функций в Хаскелле]].**[[http://rsdn.org/article/funcprog/monad.xml|МОНАДЫ!!!]]**
- [[https://www.haskell.org/tutorial/|A Gentle Introduction To Haskell, version 98. Revised June, 2000]], (оригинал);
- Цикл переводов "Еще Одно Руководство по Монадам" от Mike Vanier в 4-х частях: [[http://habrahabr.ru/blogs/Haskell/127556/|Основы]], [[http://habrahabr.ru/blogs/Haskell/128070/|Функции '>>=' и return]], [[http://habrahabr.ru/blogs/Haskell/128538/|Монадные законы]], [[http://habrahabr.ru/blogs/Haskell/129909/|Монада Maybe и монада списка]] (возможно, самое лучшее введение по монадам на русском языке). Оригиналы и ещё 4-е статьи смотреть тут [[http://m.livejournal.com/read/user/mvanier|Mike's World-O-Programming]];
- [[https://ru.wikibooks.org/wiki/Haskell/Monad_transformers|Трансформеры монад (перевод на рус.)]];
- "Жесткое введение" в Haskell [[http://habrahabr.ru/post/153383|Через тернии к Haskell (перевод). 2/2]];
- Цикл статей на сайте [[http://www.ibm.com/developerworks/ru/library/|Техническая библиотека IBM]]: [[http://www.ibm.com/developerworks/ru/library/l-haskell/|Функциональное программирование на Haskell : Часть 1. Введение]], [[http://www.ibm.com/developerworks/ru/library/l-haskell2/|Функциональное программирование на Haskell: Часть 2.Основные типы и классы]], [[http://www.ibm.com/developerworks/ru/library/l-haskell3/|Функциональное программирование на Haskell: Часть 3. Определение функций]]
- Официальная документация на модуль [[http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html|Prelude]]
- [[http://habrahabr.ru/post/196110/|Эдвард руки — С++ (почему не надо программировать на С++, но нужно на Haskell)]]
- [[http://citforum.ru/gazeta/165/|Савчук И. Почему объектно-ориентированное программирование провалилось?]]
- [[http://haskell.org/haskellwiki/OOP_vs_type_classes|OOP vs type classes]]
- [[http://habrahabr.ru/post/193722/|Haskell в продакте: Отчёт менеджера проекта]]
- [[http://ru-lambda.livejournal.com/3212.html|Haskell: что это такое]]
- [[https://events.dev.by/lenta/main/esli-by-yazyki-programmirovaniya-byli-mashinami|Если бы языки программирования были машинами]], [[https://events.dev.by/lenta/main/esli-by-yazyki-programmirovaniya-byli-religiyami|Если бы языки программирования были религиями]] (шуточное :-))
- [[http://anton-k.github.io/ru-haskell-book/book/home.html|Учебник по Haskell. Антон Холомьёв]] (пока лучший учебник на русском!!)
- [[https://www.ohaskell.guide/|Шевченко Д. О Haskell по-человечески]]
- [[http://habrahabr.ru/post/225393/|Haskell IDE от FP Complete (описание на русском онлайн IDE)]], сейчас доступна по адресу: [[http://web.archive.org/web/20140705061020/http://habrahabr.ru/post/225393/|Haskell IDE от FP Complete (копия статьи)]]
- [[http://tryhaskell.org/|онлайн песочница для попробовать в браузере]]
- [[https://play.haskell.org/|Haskell Playground]]
===== Урок 1. Знакомство с интерпретатором ghci =====
Запуск интерпретатора Haskell осуществляется командой ghci. Он имеет свою собственную оболочку, похожую на консольную оболочку Linux, однако предназначенную для вычислений выражений, функций, задания новых определений, загрузки модулей и собственных скриптов, и только отчасти в ней возможно выполнение некоторых функций обычной оболочки вроде смены директории.
**Полезные команды** в ghci:
'':q'' -- выйти из оболочки;
'':l <имя программы>'' -- загрузить программу с указанным именем. Программа может не содержать модуля Main, а только определения функций (что мы и будем делать первое время);
'':r'' -- перегрузить текущий модуль;
'':t <имя функции>'' -- напечатать сигнатуру функции;
'':i <имя функции>'' -- напечатать сигнатуру функции и указать, в каком файле была определена данная функция;
Кроме того, надо знать, что выражения в оболочке интерпретатора можно сразу вычислять.
Наберем 2 + 2 и нажмем Enter, или наберем ''abs (-2)'' и нажмем Enter, и т.д.
Новые функции (пользовательские) можно задавать, как уже писалось выше, в отдельных файлах и подгружать по мере необходимости, либо сразу определять в оболочке:
> let {f :: Int -> Int; f n = n * 2}
Отметим, что в версиях ''ghc/ghci'', начиная с 8.0.2, ключевое слово ''let'' писать необязательно.
Многострочные записи делают следующим образом:
> :{
| let f :: Int -> Int
| f n = n * 2
> :}
Другой вариант определения многострочников:
> :set +m:
| let f :: Int -> Int
| f n = n * 2
Для просмотра тех или иных значений функции ''f'' можно попробовать набрать ''f 4'', а для просмотра произвольного значения ''foo'' набрать ''show foo''.
Дополнительно отметим, что командами вида '':!cmd'' можно вызвать команду шелла ''cmd'' (например ''ls'' в Linux или ''dir'' в Windows).
===== Урок 2. Способы определения функций =====
Определим факториал. В качестве необязательного начала укажем его сигнатуру.
Она задает область определения и значения данной функции. В нашем случае --
это потенциально бесконечное множество целых чисел. Можно попробовать вычислить факториал
от 10000 или от даже большего аргумента. Для сравнения можно изменить лишь
сигнатуру в определении этой функции на Int -> Int
(или прямо в ghci введем новую функцию:
let {f :: Int -> Int; f 1 =1; f n = n * f(n-1)})
и мы уже вряд ли сможем посчитать факториал с аргументом более 31.
Остальной код задан в виде уравнений, которые через сопоставление с образцами (pattern matching) задают нужное значение функции. Образцы рассматриваются по порядку. Возможно использование рекурсии при описании функции. При вызове функций им передаются из аргументов выражения, вычисляемые по необходимости и это следует учитывать особенно при программировании рекурсивных функций, так возможен большой расход оперативной памяти (частично это как раз преодолевается грамотным использованием так называемой //ленивости вычислений//)
fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n-1)
В следующем определении мы установим <<охрану>> (guards), т.е. зададим ряд
условий, которые также будут просматриваться по порядку. Если условие True,
то считается выражение после равенства, если False, то просматривается
следующее условие. При этом условия могут пересекаться или даже не
покрывать все возможные ситуации. Если все условия будут просмотрены и ни
одно из них не даст True, то получим ошибку времени выполнения.
Для получения сведений о типе функции, в интерпретаторе можно задать
:t fact' или для более подробных сведений :i fact'.
Константа otherwise равна True и используется для удобства как синоним.
fact' x | x <= 1 = 1
| otherwise = x * fact' (x-1)
**__Упражнение__.** Используя сопоставление с образцами, а затем охрану, создать программу, вычисляющую функцию "знак числа":
1. заданную для x >= 0:
sign (x) = 0, если x=0
sign (x) = 1, иначе
2. заданную для любого x:
sign (x) = -1, при x<0
sign (x) = 1, при x>0
sign (x) = 0, иначе
==== 2.1 Ветвления====
В Haskell возможно описание вычисления функции в
зависимости от условий в более-менее традиционном ключе, для чего
присутствуют операторы ''if'' и ''case''. Однако, их применение отлично от
аналогичных операторов в императивных языках. (Правильнее их называть
выражениями с использованием ''case-'' и ''if-then-else''-конструкций)
Тем не менее, семантика данного оператора в Haskell похожа на семантику тернарного оператора
у = х > 9 ? 100 : 200;
в Си-подобных языках программирования.
Ключевое слово ''if'' предназначено для указание на ветвление вычислительного процесса в
зависимости от условия булевского типа. Части ''then'' и ''else'' обязательны, они
в отличие от императивного аналога задают не порядок действий, а функции,
которые возвращают результат для задаваемой функции. Данное выражение является
частным, более простым случаем применения выражений с ''case''.
Иными словами, условное выражение вида
nosign x = if x >= 0 then x else negate x
эквивалентно выражению
fcase x = case x >= 0 of
True -> x
False -> negate x
Рассмотрим более сложные примеры с ''case''-выражениями:
casing :: Integer -> Integer -> Integer
casing x y = case (x, y) of
(_, 0) -> x
(_, n) -> 1 + casing x (n-1)
casing' :: Integer -> Integer -> Integer
casing' x y = case (x, y) of
(_, 0) | ( x >= 0 && y >= 0 ) -> x
(_, y) | ( x >= 0 && y >= 0 ) -> 1 + casing' x (y-1)
(_,_) | ( x < 0 || y < 0 ) -> error "cannot work with negative x and y"
Последний пример является комбинацией использования ''case''-выражения с <<охраной>>
для предотвращения применения функции для отрицательных аргументов.
Стоит также упомянуть, что задание функций уравнениями также возможно
рассматривать как упрощенную запись с соответствующими ''case''-выражениями.
**__Упражнение__.** Задать функцию ''sign(x)'' из предыдущего упражнения, используя ветвления с ''if'' и ''с case''.
==== 2.2 Карринг и лямбда-абстракция ====
**Карринг.** Отметим, что в Haskell функции ''f'(x,y)=x+y'' и ''f%%''%% x y = x+y'' --- разные по сути функции. Если ''f'(x,y)'' --- это функция от одного переменного (кортежа или вектора ''(x,y)''), то ''f%%''%% x y = x+y'' --- это функция от двух переменных. Тип у них тоже будет разный, и это можно будет узнать командой '':t''.
Для чего нужен карринг и такие сложности? С теоретической точки зрения, например, карринг позволяет сводить рассмотрение функций от многих переменных к функциям одной переменной. На практике карринг позволяет задавать функции неполным применением, делать так называемые сечения.
Рассмотрим выше заданную функцию ''f%%''%% x y'', назовем ее более логично ''add x y''.
add x y = x + y
Тогда мы легко можем задать частный случай сложения, функцию-инкремент ''add1 t = 1+t'' просто частичным применением уже заданной функции ''add''
add1 = add 1
**Лямбда-абстракции.** Данный синтаксис прежде всего предназначен для
описания анонимных функций и случаев, аналогичных частичному применению
(функций). Однако полезен и для обычного описания функций.
mi2 = \x -> (x-2)
trio :: Integer -> Integer -> Integer -> Integer
trio = \x y z -> x*y + z
Примеры частичного применения функции ниже показывают, что если мы даем
частичное определение функции без последнего аргумента (каррированной
функции), то получается естественное частичное применение. Если мы хотим
оставить в <<свободном плавании>> первый или второй аргумент, то мы
вынуждены использовать лямбда-абстракцию.
duo' = trio 2 3
duo'' = \t -> trio 2 t 3
Если мы подставим в качестве аргумента 4, то увидим разницу значений
функций ''duo%%'%%'' и ''duo%%''%%''.
В следующем, более простом примере, функции ''padd1'' и ''padd3'' эквивалентны, хотя заданы
различными способами (можно запустить функции для проверки с аргументами 4 и 5):
-- add x y = x+y
padd = \x y -> x^2 + y
padd1 t = \x -> padd t x
padd2 t = \x -> padd x t
padd3 x = padd x
Необходимость в анонимных функциях возникает, например, при
использовании функций высокого порядка (т.е. таких, которые в качестве
аргумента сами получают функции). Например, рассмотрим функцию map, которая
применяет полученную в качестве аргумента функцию к списку, полученному в
качестве второго аргумента. Например, мы могли бы передать этой функции уже
готовую функцию, а могли бы задать ее <<на лету>>. Для просмотра результатов
в ''ghci'' наберите ''show l1'' и ''show l2''.
l1 = map abs [(-1), 2, (-4.2)]
l2 = map (\x -> if x >= 0 then x else negate x) [(-1), 2, (-4.2)]
Сигнатура при использования лямбда-абстракций (особенно, когда у вводимой функции нет имени) может быть определена в скобках по месту использования:
l3 =
map ((\x -> if x >= 0
then x
else negate x)::(Double -> Double))
[(-1), 2, (-4.2)]
==== 2.3 Замыкания (локальные определения)====
Аналогами локальных присваиваний в императивных языках, в функциональном языке
Haskell есть два способа порождать локальные определения.
**let-выражения.**
roots a b c =
let d = b^2 - 4*a*c
sd = sqrt d
x1 = (-b - sd) / (2*a)
x2 = (-b + sd) / (2*a)
in (x1,x2)
**where-конструкция.** Данная конструкция не является выражением, она
является частью синтаксиса объявления функций и case-выражений. Хотя в
применении они очень похожи!
roots' a b c = (x1,x2) where
d = b^2 - 4*a*c
sd = sqrt d
x1 = (-b - sd) / (2*a)
x2 = (-b + sd) / (2*a)
**Пример вычисления корней квадратного уравнения с ветвлением.**
При упрощённом подходе мы не отслеживаем случаи, когда старший коэффициент будет равен нулю или дискриминант будет отрицательный. Однако в некоторых случаях это будет приводить к аварийному останову программы в процессе вычисления. Мы можем эти случаи отследить заранее и реагировать, например, более осмысленными предупреждениями:
roots' a b c | ((a == 0) && (b == 0)) = error "No roots at all!"
| ((a == 0) && (b /= 0)) = (x,x) -- let x = -c/b in (x,x)
| (a /= 0) = (x1,x2)
where
d = b^2 - 4*a*c
sd = if (d<0) then error ("No real roots! d=" ++ show d)
else sqrt d
x1 = (-b - sd) / (2*a)
x2 = (-b + sd) / (2*a)
x = -c/b
==== 2.4 Операторы композиции функции и применения в Haskell====
Два странных (для программистов из "другого" мира) оператора «.» и "$". Сначала рекомендуется о них прочесть статьи:
[[http://rsdn.ru/article/haskell/typesH.xml|Функциональные типы и композиция функций в Хаскелле]]
[[http://habrahabr.ru/post/127556/|Еще Одно Руководство по Монадам (часть 1: основы)]]
Понимание их удобства приходит с опытом. Например, оператор композиции позволяет использовать так называемую //бесточечную нотацию (бесточечный стиль)//, т.е. при определении сложной функции обходится без указания аргументов.
:-)
Ирония в том, что в «бесточечном стиле» оператор «точка» (.) очень даже используется, — сильнее, чем в обычном коде. Тут правильнее было бы сказать «безаргументный стиль», а не «бесточечный», так как мы опускаем аргументы функций.
//Mike Vanier//
Вот как это можно использовать:
f x = cos (sin x)
g x = cos $ sin x
h = cos . sin
Здесь функции f, g и h задают одну и ту же композицию двух функций sin и cos.
Практичность оператора применения еще нагляднее -- он так же позволяет не писать лишних скобок, вот еще то же самое определение
f x = cos $ sin x
==== 2.5 Проблемы преобразования типов в выражениях ====
Попробуем
2 + 2.0
4.0
Теперь попробуем
let x = 2
x + 2.0
:1:4:
No instance for (Fractional Integer)
arising from the literal `2.0' at :1:4-6
Почему ошибки не было в первом случае, и откуда она взялась во втором? И как ее избежать? Ведь в других языках приведение констант делает автоматически...
В новых версиях ghci поведение в let изменено. Если раньше, по крайней мере до GHCi, version 7.4.1 было:
Prelude> :t x
x :: Integer
то теперь в GHCi, version 8.0.2
Prelude> :t x
x :: Num t => t
соответственно получается правильный ответ:
Prelude> x + 2.0
4.0
Как показали дальнейшие изыскания, изначальное поведение было обусловлено ещё одной проблемой Haskell, так называемом //ограничением мономорфизма//:
[[https://wiki.haskell.org/Monomorphism_restriction|Monomorphism_restriction]]. В современных версиях ghci это ограничение отключено, но при желании его можно вновь включить и потестировать указанные выше странности:
Prelude> :set -XMonomorphismRestriction
Prelude> let x = 2
Prelude> x + 2.0
:5:5: error:
* No instance for (Fractional Integer)
arising from the literal `2.0'
...
Вот версия более простого и понятного примера, без странностей ограничения мономорфизма:
Prelude>let x=2::Int; y=2::Double
Prelude> x+y
:2:3: error:
* Couldn't match expected type `Int' with actual type `Double'
* In the second argument of `(+)', namely `y'
In the expression: x + y
In an equation for `it': it = x + y
В языках типа Си это соответствовало бы объявлению и инициализации переменных типа int и double, а потом совместного их использования в одном арифметическом выражении.
==== 2.6 Использование монады состояния====
Пока без комментариев, вычисление факториала:
import Control.Monad.State
fact' :: Integer -> State Integer Integer
-- тип состояния - Integer, тип результата - тоже Integer
fact' 0 = do
acc <- get -- получаем накопленный результат
return acc -- возвращаем его
fact' n = do
acc <- get -- получаем аккумулятор
put (acc * n) -- домножаем его на n и сохраняем
fact' (n - 1) -- продолжаем вычисление факториала
-- fact :: Integer -> Integer
fact n = fst $ runState (fact' n) 1 -- начальное значение состояния = 1
**__Задания к уроку__**
1. Используя примеры из урока, написать код и исполнить его в ''ghci'', проверить тип полученных функций.
2. Сделать тоже самое в отдельном файл и загрузить его в ''ghci'' с помощью команды '':l''.
3. Написать код для функций ''min, max, |x|, [x]'', среднего арифметического двух чисел и списка чисел, многочленов, рациональных функций и др. числовых функций.
===== Урок 3. Списки как типы =====
Списки --- широко используемая в Haskell (и в др. функц. языках в целом) полиморфная структура данных. Например, ''[a]'' --- это семейство типов, состоящее из типов списка с элементами из ''a'', для любого типа ''a''. Список целых (напр., ''[1,2,3]''), список символов (''['a','b','c']''), даже список списков целых и т.д. -- все являются членами этого семейства (отметим, однако, что ''[2,'b']'' не является таким примером и списком).
Список ''[1,2,3]'' в Haskell на самом деле является сокращенной формой записи для списка ''1:(2:(3:[]))'', где ''[]'' --- это пустой список, '':'' --- инфиксный оператор, добавляющий свой первый аргумент в начало своего второго аргумента (некоторого списка). Поскольку '':'' правоассоциативен, мы можем написать ''1:2:3:[]''.
==== 3.1 Полезные базовые функции для работы со списками ====
Рассмотрим ряд полезных **базовых** функций.
(везде ниже ''xs'', ''ys'' и т.п. обозначают список)
* ''xs !! n'' --- получим n-й произвольный элемент списка ''xs'', начиная с нулевого;
* ''head xs'' --- вернет //первый// элемент списка ''xs'';
* ''last xs'' --- вернет //последний// элемент списка ''xs'';
* ''tail xs'' --- вернет список ''xs'' без //первого// элемента;
* ''init xs'' --- вернет список ''xs'' без //последнего// элемента;
* ''reverse xs'' --- вернет обратный список;
* ''length xs'' --- вернет длину списка ''xs'';
==== 3.2 Добавление к списку ===
Ряд функций для добавления как отдельных элементов, так и целых списков.
* ''x:xs'' --- добавит ''x'' в качестве нового головного (нулевого) элемента к списку ''xs'';
* ''xs ++ [x]'' --- добавит ''x'' в качестве последнеого элемента к списку ''xs'';
* ''list1 ++ list2'' --- конкатенация двух списков ''list1'' и ''list2'';
Если же нам необходимо вставить ''x'' на произвольную позицию ''n'', надо разбить список на два меньших куска, поместить новый элемент между ними и соединить все вместе обратно:
let (ys, zs) = splitAt n xs
in ys ++ [x] ++ zs
получим новый список, где ''x'' займет требуемую позицию ''n''.
==== 3.3 Удаление из списка ===
* ''drop n xs'' --- вернет список, где удалены первых ''n'' элементов из списка ''xs'';
* ''take n xs'' --- вернет список из первых ''n'' элементов из списка ''xs'';
* ''splitAt n xs'' --- вернет пару списков, полученных из списка ''xs'' разбиением c ''n''-й позиции (причем ''n''-й элемент войдет во второй список);
Если мы хотим удалить только ''n''-й элемент из списка, нам придется вновь разбить список на два меньших куска, удалить нулевой элемент из второго списка и соединить все вместе обратно:
let (ys, zs) = splitAt n xs
in ys ++ (tail zs)
**Задание к уроку.** Напишите функцию ''slice'', которая работает как срезы (слайсы, slices) в таких языках как Python и Perl. Другими словами, должно быть что-то типа такого
> slice 2 3 [2.3, 7.4, 5.66, 6.1, 7.0]
[5.66, 6.1]
==== 3.4 Условия на список ===
Различные функции, которые извлекают подсписок в соответствии с условиями, выполняют проверки и т.п.:
* ''null xs'' --- проверяет, пуст ли список ''xs'' (возвращает ''True'' или ''False'');
* ''x `elem` xs'' --- проверит, лежит ли элемент ''x'' в списке ''xs'' (возвращает ''True'' или ''False'');
* ''any test xs'' --- вернет ''True'', если какой-либо элемент списка удовлетворяет условию ''test'' (если тип списка ''[a]'', то тип функции ''test'' должен быть a -> Bool);
* ''all test xs'' --- вернет ''True'', если все элементы списка удовлетворяет условию ''test'' (с аналогичными выше требованиями);
* ''filter test xs'' --- вернет только те элементы списка, которые удовлетворяют условию ''test'' (с аналогичными выше требованиями);
Пример использования в ghci:
Prelude> let xs = [1,2,322,100]
Prelude> filter (\x -> if x>1 then True else False) xs
Prelude> [2,322,100]
==== 3.5 Изменение списка или его элементов ===
* ''map f xs'' --- применит функцию ''f'' ко всем элементам списка ''xs'' и вернет новый список;
* ''map (\x -> if p x then f x else x) xs'' --- применит функцию ''f'' только к тем элементам списка, для которых функция ''p'' вернет ''True'';
* ''concat [[x,y,z],[a,b,c,d,e],[o,p,r,s,t]]'' --- из списка списков вернет список элементов всех списков ''[x,y,z,a,b,c,d,e,o,p,r,s,t]'';
* ''zip xs ys'' --- вернет список пар вида ''(x,y)'', в каждой из которых первый элемент ''x'' является очередным элементом первого списка ''xs'', а второй элемент ''y'' --- второго списка ''ys'';
* ''zip xs [0..]'' --- нумерация (альтернативная, [[haskell#poleznye_bazovye_funkcii_dlja_raboty_so_spiskami|ср. с п.3.1]]) элементов списка (так, например, ''zip ['a','b','c'] [0..]'' даст ''[('a',0), ('b',1), ('c',2)]'');
==== 3.6 Замечания о скорости работы списочных функций ===
Следующие функции всегда быстры:
* '':'' --- добавление первого элемента к началу списка;
* ''head'' --- получение первого элемента списка;
* ''tail'' --- удаление первого элемента из списка, т.е. хвост списка.
Функции, которые имеют дело с n-м элементом или первыми n элементами, обычно имеют скорость порядка n:
* ''xs !! n'';
* ''take n xs'';
* ''drop n xs'';
* ''splitAt n xs''.
Все функции, которые для выполнения нуждаются в целом списке, становятся тем медленнее, чем длиннее становится список:
* ''length xs'';
* ''list1 ++ list2'' --- скорость зависит //только// от длины ''list1'';
* ''last xs'';
* ''map my_fn xs'';
* ''filter my_test xs'';
* ''zip list1 list2'' --- скорость зависит от //наименьшего// из этих двух списков, поскольку именно он задет размер результирующего списка;
* ''sum xs'';
* ''minimum xs'';
* ''maximum xs''.
**Задача 1.** Написать собственные реализации функций maximum, minimum, sum, filter, reverse, sort.
==== 3.7 Определитель списков и диапазоны ===
По аналогии с математической теории множеств, в которой множество можно задать из имеющего с помощью //аксиомы выделения//:
{ 2x | x ∈ N }
где мы задаем множество четных натуральных чисел, в Haskell мы можем задать список четных натуральных чисел:
[ 2*x | x <- [1..] ]
(отметим, заданный список будет бесконечный!)
После выражений вида x <- xs, называемых генератором, могут быть дополнительные условия (охрана), которые также должны быть выполнены:
[ 2*x | x <- [1..], 3 < x, x < 7 ]
Отметим, что хотя с математической точки зрения данный список будет формально заданным, его вычисление, быстро выдав три первых ответа: 8,10,12 --- зависнет, так как реально программа будет перебирать все натуральные значения x, начиная с 1. Поэтому запуск можно делать как
take 3 [ 2*x | x <- [1..], 3 < x, x < 7 ]
либо как указано выше, вводить ограничение сверху, т.е. использовать x <- [1..57].
В примере также показан способ построения списков, называемых //диапазон//:
* ''[1..]'' --- список всех натуральных чисел;
* ''[1,3..]'' --- список всех нечетных натуральных чисел;
* ''[1,3..99]'' --- список всех нечетных натуральных чисел от 1 до 99;
**Простые задачи.** Описать списки четных и нечетных чисел, список квадратов четных чисел, список кубов нечетных. Выбрать из них список чисел, делящихся на 7, от 2000 до 10000.
**Задача 1.** Написать код, генерирующий потенциально бесконечный
список чисел Фибоначчи. Рассмотреть возможности "лобового решения" с бинарной рекурсией и оптимизации. (см. [[haskell:fibb|варианты решения]])
**Задача 2.** Написать код, генерирующий потенциально бесконечный
список простых чисел. Оптимизация по скорости, памяти и краткости
кода не требуется. (см. [[haskell:primex|решение здесь]])
==== 3.8 Дополнительные функции из модуля Data.List ===
Для целей "разгрузки" базового модуля ''Prelude'' в плане работы со списками, создан модуль ''Data.List'', который содержит помимо основных дополнительные удобные функции. Модуль необходимо вызывать квалифицированно:
import qualified Data.List
либо явно указывать импортируемые функции из числа тех, что не определены в Prelude:
import Data.List(delete)
Перечислим ряд полезных функций, эмулирующих работу со списками как со множествами:
* ''nub xs'' -- возвращает список, в котором удалены повторяющиеся элементы;
* ''delete x xs'' -- удаляет первое вхождение заданного элемента ''x'' из списка ''xs'';
* ''sortBy p xs'' -- осуществляет сортировку списка ''xs'', используя специальным образом заданную программистом функцию ''p'';
* ''union xs ys'' -- возвращает объединение двух списков;
* ''intersect xs ys'' -- возвращает пересечение двух списков;
* ''(\\)'' -- возвращает разность (неассоциативную) двух списков, таким образом: ''(xs ++ ys) \\ xs == ys'' (если нет общих элементов);
* ''elem x xs'' -- предикат, возвращающий истину, если элемент ''x'' принадлежит списку ''xs'';
* ''tails xs'' -- функция возвращает список хвостов данного списка, напр.:tails "abc" == ["abc", "bc", "c", ""]
* ''isPrefixOf, isSuffixOf, isInfixOf'' -- предикаты, принимающие два аргумента-списка ''list1'' и ''list2'', и возвращающие ''True'', если ''list1'' является приставкой, окончанием или содержится где-то в списке ''list2''.
**Задание к уроку.** Сделать собственные реализации указанных функций для представления конечных множеств в виде конечных списков.
=== 3.8.2 Поиск и замена в списках ===
Модуль ''Data.List'' предоставляет ряд функций, полезных для реализации функций поиска и замены в списках. Помимо уже указанных ''(!!)'', ''elem'' есть следующие:
* ''find p xs'' -- возвращает первый элемент в списке ''xs'' (обернутый конструктором ''Just''), который удовлетворяет предикату ''p'' или ''Nothing'' в противном случае;
* ''findIndex p xs'' -- возвращает индекс первого элемента в списке ''xs'' (обернутый конструктором ''Just''), который удовлетворяет предикату ''p'' или ''Nothing'' в противном случае;
* ''filter p xs'' -- возвращает подсписок списка ''xs'', элементы которого удовлетворяют предикату ''p''.
**Задача 1.** В Haskell нет встроенных функций по типу ''index'', ''substr'', ''replace'' для работы с поиском и заменой. Написать собственные реализации.
==== 3.9 Различные примеры определения функций, работающих со списками ====
Хорошим собранием образцов таких определений функций является сам модуль Prelude. Для нужд обучения полезно писать собственные реализации таких функций и/или изучать готовый код.
last [x] = x
last (_:xs) = last xs
init [x] = []
init (x:xs) = x:(init xs)
head (x:_) = x
tail (_:xs) = xs
null [] = True
null (_:_) = False
length [] = 0
length(x:xs)= 1 + length xs
Функция ''length'', заданная выше, в некотором смысле является образцом неэффективности рекурсивного определения для часто используемой функции, реализация которой в императивных языках для массивов и динамических массивов легковесна и быстра. В самом деле, напр. при вычислении длины списка в 1000000 элементов, функция ''length'' 1000000 раз пересоздаст список, убавляя каждый раз его на 1 элемент, и все промежуточные вычисления вместе со ссылками на адреса предыдущих шагов должны присутствовать в оперативной памяти, пока не будет явно вычислен случай пустого списка,
и вычисление не вернется по шагам обратно.
Для преодоления такой ситуации в функциональном программировании везде где это необходимо используют хвостовую рекурсию и накапливающийся параметр:
length' [] n = n
length' (_:xs) n = length' xs (n+1)
length ys = length' ys 0
Здесь ''length''' определена как хвостовая рекурсия, т.е. рекурсия, в определении которой последний вызов является вызовом самой себя (хвостовой вызов) и таким образом, позволяет избежать накладных расходов. Кроме того, такие определения при трансляции компилятором преобразуется в цикл типа ''for''.
**Задание 1 для самостоятельной работы:** написать собственный код для всех функций работы со списками, приведенных в главе 3.
**Задание 2:** написать код функции транспозиции, т.е. для данного списка ''xs'' и данных номеров-параметров ''n,m'' поменять элементы ''xs!!n'' ''xs!!m'' местами. Иными словами, в императивном смысле нам необходимо сделать что-то подобное следующему:
tmpn := xs[n]; tmpm := xs[m];
xs[n]:= tmpm; xs[m]:= tmpn;
Однако, в случае Haskell, функции необходимо вернуть новую копию списка, в которой указанные элементы будут поменяны местами.
===== Урок 4. Модули =====
==== 4.1 Импорт модулей ====
Импортирование сторонних модулей производится при помощи ключевого слова ''import''. После этого ключевого слова должно располагаться наименование импортируемого модуля, после которого может находиться перечисление тех программных сущностей, которые импортируются в модуль. Если такого списка нет, то импортируется все экспортируемое данным модулем. Например:
import Data.List
import Data.Char (
toLower,
toUper
)
**SIC.** Экспорт воплощения экземпляров классов делается всегда, вне зависимости от списка --- попросту, нет механизма внесения в список.
А что делать, если возникает конфликт имен при импорте? Рассмотрим возможные решения ниже.
=== 4.1.1 Сокрытие имен при импорте модулей ===
Иногда бывает проще при импорте скрыть некоторые имена, чем перечислять то, что импортируется. Это можно сделать при помощи ключевого слова ''hidding'', которое должно располагаться после наименования модуля при импорте. После этого перечисляются имена, которые должны быть скрыты при импорте:
import MyModule hiding (
someFunction1, someFunction2
)
=== 4.1.2 Квалифицированный импорт модуля ===
Другой случай возникает, когда в программе необходимы обе сущности, и сокрытие помочь не может. В такой ситуации ''Haskell'' дает возможность использовать квалификацию имен при импорте, т.е. при использовании импортированных программных сущностей перед их именем должно стоять имя импортируемого модуля. Для этого мы используем ключевое слово ''qualified'', которое указывает, что модуль импортируется квалифицированно:
import qualified SomeModule
xs = map SomeModule.somefunction ys
Стоит отметить, что после квалифицированного импорта неквалифицированные имена уже использовать нельзя.
Если модуль имеет слишком длинное и неудобное имя, то при квалифицированном импорте можно переименовать модуль, дав ему коротко название. Для этого используется ключевое слово ''as'':
import qualified VerySuperPuperModule as M
Более детально об импорте модулей можно прочитать тут: [[https://wiki.haskell.org/Import|wiki.haskell: Import]].
==== 4.2 Экспорт модулей ====
Если мы пишем программный код для использования другими программистами или для многократного использования для себя, то нам удобно оформить код в виде модуля. Haskell предоставляет для оформления модулей удобные, но простые средства:
module Ourhmodul (VeryImortantOurType, ourfunc1, ourfung2) where
Далее пишем определения типа ''VeryImortantOurType'' и функций ''ourfunc1'' и ''ourfung2''. Однако, при этом, конструкторы типа не экспортируются. Если же нам нужно их экспортировать, то мы должны их либо явно перечислить, либо с помощью двоеточия указать, что мы экспортируем все конструкторы.
module Ourmodul (
VeryImortantOurType(Constr1,Constr2),
ourfunc1,
ourfung2) where
module Ourmodul (VeryImortantOurType(..), ourfunc1, ourfung2) where
Кроме того, отметим, что модули стоит писать в отдельных файлах, название которых совпадает с названием модуля (без расширения), и название пишем с большой буквы.
===== Урок 5. Типы данных, определяемые пользователем =====
Haskell помимо встроенных основных типов предоставляет пользователям возможность самим определять собственные типы (так называемые //алгебраические типы//).
Наиболее простой способ определения типов --- это перечисления.
Так, мы можем определить цветовой тип:
data Color = Red | Green | Blue | Black | White
Однако, без представления о классах (см. ниже), с данным типом можно работать лишь в сопоставлениях с образцом в определениях функций:
f :: Color -> Char
f Red = 'r'
f Green = 'g'
f Blue = 'b'
f _ = 'x'
Другой, более интересный способ, так называемые записи или структуры:
data Point a = Pt a a
Здесь ''Point'' называют //конструктором типов//, производящим тип, а ''Pt'' называют //конструктором данных (или конструктором значений)//, производящим значение.
Как указывают авторы "Мягкого введения в Haskell", важно различать применение конструкторов типа и данных. Второе происходит во время выполнения и представляет собой способ, которым осуществляются вычисления в Haskell. Первое происходит во время компиляции и является частью процесса по обеспечению типобезопастности.
Кроме того, конструкторы типа и данных находятся в разных пространствах имен. Таким образом, мы могли именем ''Point'' называть оба конструктора --- так часто программисты на Haskell и поступают.
При описанном выше способе определения данных также возможно использование в сопоставлениях с образцом:
fliP (Pt x y) = Pt y x
paiR (Pt x y) = (x,y)
getX (Pt x _) = x
(проверьте тип этих функций!!)
Возможно применение введенного конструктора типа с конкретными типами:
f :: Point Double -> Double
f (Pt x y) = sqrt (x^2 + y^2)
g :: Point Double -> Point Double
g (Pt x y) = Pt (x+2) (y+2)
Таким образом, введенный тип ''Point'' является //полиморфным//.
Также возможно создание типов без каких-либо параметров:
data PointOnMonitor = Point2D Int Int Color
mycolor :: PointOnMonitor -> Color
mycolor (Point2D x y c) = c
mycoord :: PointOnMonitor -> Point Int
mycoord (Point2D x y c) = Pt x y
Однако, более удобно использование так называемых именованных полей:
data Point = Point {pointx, pointy :: Double}
Тогда допустимо такое использование именованных полей:
absPoint p = sqrt ( (pointx p)^2 + (pointy p)^2 )
Таким образом, отпадает нужда во введении функций, подобных ''getX''.
При сопоставлении с образцом будем писать:
absPoint' (Point { pointx = x, pointy =y } ) = sqrt (x^2 + y^2)
или
absPoint'' (Point x y) = sqrt (x^2 + y^2)
В одном объявлении возможно совмещения перечисления и создания структуры:
data Color2 = Red | Blue | RGB Int Int Int deriving Show
и пример использования:
toInt Red = RGB 255 0 0
toInt Blue = RGB 0 0 255
toInt x = x
toName (RGB 255 0 0) = Red
toName (RGB 0 0 255) = Blue
toName _ = error "Not defined!"
Работу конструкторов данных можно рассматривать как "навешивание" нового //тэга// к известным типам, для указания возможности использования их в других смыслах.
**Задание к уроку. 1.** Написать тип данных "неделя", перечисляющий дни недели. Написать функции, которые по номеру дня дают его название (точнее, значение) и по названию (значению) дают номер. Задать предикат, который выделяет выходные дни.
**Задание к уроку. 2.** Задать тип данных "точка" (из двух действительных компонентов-чисел). Задать функцию --- расстояние между точками. Составить список всех пар расстояний между разными точками и найти максимальное.
==== 5.1 Пример на 2 цикла. Массивы ====
Рассмотрим обобщение последней задачи. Пусть у нас имеется произвольной длины список координат точек на плоскости. Требуется вновь найти максимальное расстояние между двумя точками.
Вот решение этой задачи на языке JavaScript (в котором мы максимум не вычисляем, а выводим только список всевозможных расстояний):
var da = [[23.43,-34.8], [13.34,15.574], [-25.45,45.32], [37.6,78.23], [345.23,45.23]];
function distance (p1,p2)
{
var dist = Math.sqrt( Math.pow((p1[0] - p2[0]),2) + Math.pow((p1[1] - p2[1]),2));
return (dist);
}
var res = [];
var n = da.length;
var d = 0;
for (i=0;i
Основная "соль" в том, что решение мы делаем через использование двух вложенных циклов. Как провести аналогичные вычисления на функциональном языке?
Прежде всего, воспользуемся типом данных точки Point и функцией, вычисляющей длину между двумя точками distance.
data Point = Pt {pointx,pointy:: Double} deriving (Eq,Show,Read)
distance :: Point -> Point -> Double
distance p1 p2 = sqrt ((pointx p2 - pointx p1)^2 + (pointx p2 - pointx p1)^2)
Зададим теперь произвольный список координат точек:
da = [(Pt 23.43 (-34.8)), (Pt 13.34 15.574), (Pt (-25.45) 45.32), (Pt 37.6 78.23), (Pt 345.23 45.23)]
Определим рекурсивно функцию, вычисляющую список расстояний от n-й точки до 0-й, 1-й, ..., (n-1)-й:
distset 0 = []
distset n = [(distance (da!!k) (da!!n)) | k<-[0..(n-1)]]
Добавим полученные результаты в "общую копилку" расстояний. Её мы тоже зададим рекурсивно::
resset 0 = []
resset n = (distset n) ++ resset (n-1)
Полный набор расстояний теперь будет задаваться так:
ressset ((length da) -1)
Соответственно,
maximum $ ressset ((length da) -1)
даст нам требуемый ответ.
Данное решение, помимо отсутствия ясности по сравнению с двойным вложенным циклом в императивном решении на JavaScript, "страдает" большими накладными расходами, которые проявятся, если исходный список будет значителен.
Отметим все проблемные места. Самым последним неэффективным местом будет конкатенация списков:
...
resset n = (distset n) ++ resset (n-1)
от который мы избавимся следующим изящным решением с двойным генератором требуемого списка расстояний:
rset = [(distance (da!!k) (da!!n)) | n<-[1..(length(da)-1)], k<-[0..(n-1)], k
Это решение очень наглядно, вполне математично. Однако и в нём есть неэффективные места, связанные с особенностью работы списков в Haskell. Это вычисление длины списка (length da) (которую, в общем-то нам не избежать, если мы только заранее не знаем размер наших данных) и крайне неэффективные вызовы элементов списка (da!!k). Списки не являются массивами, поэтому вызов (da!!k) приводит к рекурсивной пересборке всего списка, чтобы "добраться" до k-го элемента и это крайне затратно по памяти и времени. Эту особенность можно обойти, отказавшись от обращения к конкретным элементам списка по номеру и вычисления длины списка, используя более тщательно генераторы списков, либо радикально решить с помощью массивов.
Вот как выглядит такое решение с использованием генераторов списков
distlist = [(distance p1 p2) | n<-da, k<-da]
maximum distlist
Однако, в этом решении присутствует неэффективность вычисления расстояний между точками дважды, так как
distance p1 p2 == distance p2 p1
=== 5.1.1 Решение с массивом ===
Поэтому, если нам нужен эффективный доступ к элементам по индексу и за счет этого более высокий контроль того, что происходит в генераторах списков, то необходимо обратиться к массивам.
Выпишем полностью решение с использованием массива. Оно будет немного отличаться.
import Data.Array
data Point = Pt {pointx,pointy:: Double} deriving (Eq,Show,Read)
distance :: Point -> Point -> Double
distance p1 p2 = sqrt ((pointx p2 - pointx p1)^2 + (pointx p2 - pointx p1)^2)
da = [(Pt 23.43 (-34.8)), (Pt 13.34 15.574), (Pt (-25.45) 45.32), (Pt 37.6 78.23), (Pt 345.23 45.23)]
lst = (length da) -1
ad = listArray (0,lst) da
rset = [(distance (ad!k) (ad!n)) | n<-[1..lst], k<-[0..(n-1)], k
Прокомментируем его. Во-первых, если длину списка da мы знаем заранее из условий, делать затратное вычисление lst нет нужды. Далее, во-вторых, посмотрим как задаётся массив в Haskell. Приведём один из вариантов. Так, пусть нам уже известны нижняя граница (в нашем случае 0) и верхняя граница (в нашем случае lst) будущего массива. Задаём массив с помощью функции listArray с двумя аргументами: парой из нижней и верхней границы, и списком, который в порядке возрастания и задаст элементы массива. Получение k-го элемента с помощью вызова (ad!k) будет происходить гарантированно быстро и одинаковой скоростью для любого значения индекса.
Отметим, что в начале программы (до использования функций работы с массивами) необходимо сделать импорт соответствующего модуля:
import Data.Array
В указанном модуле помимо использованных функций, содержатся и другие, полезные для начальной инициализации массива, инкрементального обновления части массива и отдельного элемента.
**Задание к уроку. 1.** Для данного массива координат точек вычислить координаты "центра тяжести", принимая вес каждой точки за 1.
**Задание к уроку. 2.** Изменим базовый тип
data Point = Pt {mass,pointx,pointy:: Double} deriving (Eq,Show,Read)
Для полученного (надо завести конкретный массив) массива материальных точек вычислить центр тяжести.
**Задание к уроку. 3.** Для исходного массива координат точек вычислить длину пути ломанной соединяющей точки в порядке возрастания нумерации в массиве.
==== 5.2 Рекурсивные типы ====
Типы также могут быть рекурсивными. Рассмотрим пример двоичного дерева, листья которого содержат значения произвольного типа ''a'':
data Tree a = Leaf a | Branch (Tree a) (Tree a)
fringe (Leaf x) = [x]
fringe (Branch left right) = fringe left ++ fringe right
kolvo :: Tree a -> Int
kolvo (Leaf _ ) = 1
kolvo (Branch l r) = kolvo l + kolvo r + 1
a1 = Leaf 1
a2 = Leaf 2
a3 = Leaf 3
b1 = Branch a1 a2
b2 = Branch b1 a3
**Задание к уроку.** По аналогии создать тип данных двоичных деревьев, у которых в каждой вершине будет храниться некоторое значение типа ''Int''. Написать функции, которые извлекают значения из вершины, собирают список таких значений для всего дерева, суммируют их (и считают их среднее арифметическое), вычисляют высоту дерева, определяют соседа, потомков и предков.
==== 5.3 Синонимы типов type и объявление newtype ====
Для удобства программистов в Haskell есть возможность определять синонимы типов для часто используемых типов. Они создаются с помощью объявления type:
type String = [Char]
type Name = String
type Tochka = Point Float
И еще есть некоторый аналог объявления ''data'' для более-менее простых случаев
newtype Email = MkEmail String
Это объявление можно использовать только в случаях конструкторов данных с одним аргументом. У объявления есть некоторые преимущества при оптимизации в процессе компиляции.
==== 5.4 Примеры ====
Создадим несколько учебных примеров, для лучшего понимания использования алгебраических типов на практике.
Допустим, мы хотим рассмотреть системы вычетов по модулю 5. С точки зрения математики, мы хотели бы реализовать на Haskell кольцо вычетов, т.е. возможность складывать, умножать и т.п. классы вычетов.
[2] + [2] = [4];
[2] + [3] = [0];
[2] * [2] = [4];
[2] * [3] = [1];
(Иное представление -- операции по модулю 5)
Следующий пример дает представление о том, как можно реализовать это на Haskell:
data MyAlg = O | I | II | III | IV deriving (Eq, Ord, Read, Show)
o :: MyAlg
o = O
e :: MyAlg
e = I
next :: MyAlg -> MyAlg
next O = I
next I = II
next II = III
next III = IV
next IV = O
prev :: MyAlg -> MyAlg
prev O = IV
prev I = O
prev II = I
prev III = II
prev IV = III
(<>) :: MyAlg -> MyAlg -> MyAlg
O <> x = x
n <> x = next (prev n <> x)
(><) :: MyAlg -> MyAlg -> MyAlg
O >< _ = O
n >< x = (prev n >< x) <> x
chet :: MyAlg -> Bool
chet O = True
chet II = True
chet IV = True
chet _ = False
Разовьем идею последнего примера. Вместо непривычных операций <>, >< организуем перегрузку стандартных операций +, -, * из класса Num. Но сначала определим функцию из целых в вычеты и наоборот
(эпиморфизм из целых в вычеты и выбор канонического представителя, в нашем случае, это будет отображение вычетов в первые пять целых чисел):
-- эпиморфизм из целых в вычеты (классы экв.)
toMyAlg :: Integer -> MyAlg
toMyAlg 0 = O
toMyAlg 1 = I
toMyAlg 2 = II
toMyAlg 3 = III
toMyAlg 4 = IV
toMyAlg x = toMyAlg (x `mod` 5)
-- определяем канонического представителя
fromMyAlg :: MyAlg -> Integer
fromMyAlg O = 0
fromMyAlg I = 1
fromMyAlg II = 2
fromMyAlg III = 3
fromMyAlg IV = 4
Теперь, когда все вспомогательные операции готовы, мы можем организовать воплощение класса Num для нашего кольца вычетов:
-- добавим к предыдущему:
-- интерпретация сигнатурных символов
-- (в терминах Haskell: перегрузка операций класса Num)
instance Num MyAlg where
fromInteger = toMyAlg
x + y = x <> y
x * y = y >< y
-- вводим отрицание (рекурсивно) и др.
negate O = O
negate n = prev (negate (prev n))
signum O = O
signum _ = I
abs = id
Следующий пример используем для построения типа, который является ограничением уже существующего типа. Таким примером будет тип Natural, являющийся сужением типа Integer до неотрицательных целых чисел.
Кроме того, нам может потребоваться сделать тип, у которого скрыты некоторые детали организации: конструкторы, те или иные методы. Это может предотвратить нежелательное использование, кроме указанных интерфейсных методов. В Haskell это возможно путем вынесения типа и его методов в отдельный модуль.
module Naturalische (
Natural (MakeNatural),
toNatural,
fromNatural
) where
newtype Natural = MakeNatural Integer deriving (Eq,Ord)
toNatural :: Integer -> Natural
toNatural x | x < 0 = error "There is no negative natural numbers!"
| otherwise = MakeNatural x
fromNatural :: Natural -> Integer
fromNatural (MakeNatural i) = i
chet x = (x `mod` 2 == 0)
instance Num Natural where
fromInteger = toNatural
x + y = toNatural (fromNatural x + fromNatural y)
x - y = toNatural (fromNatural x - fromNatural y)
x * y = toNatural (fromNatural x * fromNatural y)
abs = toNatural . fromNatural
signum = toNatural . signum . fromNatural
instance Show Natural where
showsPrec n = showsPrec n . fromNatural
[[haskell:sekv|haskell:sekv]]
==== 5.5 Классы типов ====
В предыдущем пункте 5.4 были показаны примеры, когда мы для новых алгебраических типов данных: кольца вычетов и натуральных чисел решили использовать привычные операции сложения, вычитания, умножения и т.п. Для этого мы воспользовались механизмом воплощения стандартных классов для наших типов данных.
Однако, классы можно также создавать "с чистого листа". Идея классов в Haskell родственная идее сигнатурных символов операций, предикатов, констант и их интерпретации в теории моделей. В Haskell эта идея сводится к тому, что при организации класса мы выписываем сигнатуры нужных нам типов функций и их простейших связей (взаимных определений), а потом, при разработке новых типов данных, мы указываем воплощение данного класса для нашего типа.
При этом, мы вправе использовать механизм модулей, который позволяет нам сокрыть детали реализации для конечного пользователя. Например, в примере с натуральными числами выше
предикат chet сокрыт для внешнего мира. А конструктор данных MakeNatural разрешен к использованию в явном виде. Если бы мы этого не хотели, то нужно было бы указать:
module Naturalische (
Natural,
toNatural,
fromNatural
) where
Таким образом, мы приходим к понятию //абстрактных типов данных//, где пользователю с помощью классов представлен интерфейс доступа и манипуляций к значениям из некоторого типа данных, детали реализации которого намеренно скрыты.
**Задание.** Создать собственный класс Logic с операциями ''&&&,'' ''|||'', ''neg'' --- описывающие сигнатуры и взаимосвязи конъюнкции, дизъюнкции и отрицании. Затем создать тип данных ''OurBool'' и воплощения для него класса ''Logic''.
Формально класс описывается следующим образом:
class Logic a where
neg :: a -> a
(&&&) :: a -> a -> a
(|||) :: a -> a -> a
Можно указать простейшие связи между этими операциями:
x &&& y = neg ( (neg x) ||| (neg y) )
x ||| y = neg ( (neg x) &&& (neg y) )
Чтобы уменьшить число скобок, полезно указывать приоритет заданных операций и их ассоциативность:
infixl 7 &&&
infixl 5 |||
Вот примерный образец минимального решения:
class Logic a where
neg :: a -> a
(&&&) :: a -> a -> a
(|||) :: a -> a -> a
data MyBool = T | F deriving (Eq, Read, Show)
T `kon` T = T
_ `kon` _ = F
F `diz` F = F
_ `diz` _ = T
ot T = F
ot F = T
instance Logic MyBool where
neg = ot
(&&&) = kon
(|||) = diz
**Задание.** Создать собственный класс ''MyModulus'' с единственной функцией ''modl''. Затем для типов ''Int, [a], (a,b)'' создать воплощения класса ''MyModulus'' так, чтобы для ''Int'' это было абсолютной значение, для списков -- длина списка, для пары -- значение 2. Для типа данных
{-# LANGUAGE FlexibleInstances #-}
data IntPara = Point Int Int
сумма абсолютных значений.
==== 5.6 Классы типов и АТД ====
Как уже упоминалось выше, классы типов полезны при создании "АТД" (Абстрактные Типы Данных --- Abstract data type --- англ.) Это позволяет реализовать ситуацию, когда разные разработчики создают различные уровни абстракции: архитекторы -- АТД с абстрактными методами, программисты --- либо воплощения этих АТД для конкретных данных, либо использования методов АТД в следующих "слоях абстракции". А воображаемые пользователи могут использовать как прелести реализации, так и возможности создавать методы, независимые от реализации.
В "невоображаемой" реальности ситуация сильно осложняется и, по крайней мере, на Haskell мы порой вынуждены использовать ещё более громоздкие виды абстракции: GADT, Type Family, Type Functional Dependency и т.п.
В данном разделе рассмотрим идею АТД и простое использование этой идеи. Создадим модуль с задекларированной функцией-предикатом:
module Sosedy (Sosedy, (~~)) where
class Sosedy a where
(~~) :: a -> a -> Bool
Данный класс и его метод описывает ситуацию "быть соседом" вне зависимости от реализации. Далее, некто или мы можем на этой базе создать новые функции, не зависящие от реализации, напр., предикат, описывающий свойство "быть соседом симметрично":
module SimSosedy where
import Sosedy
(~~~) :: (Sosedy a) => a -> a -> Bool
a ~~~ b = (a ~~ b) && (b ~~ a)
Ну и, наконец, создадим различные реализации (воплощения) для данного класса и метода:
{-# LANGUAGE FlexibleInstances, UndecidableInstances, IncoherentInstances #-}
module SosedyInst((~~),(~~~)) where
import Sosedy
import SimSosedy
import Data.Char(ord)
instance Sosedy Int where
x ~~ y = (abs (x-y) == 1)
instance Sosedy Char where
x ~~ y = ((ord(x) - ord(y)) == 1)
instance (RealFloat a) => Sosedy a where
x ~~ y = (abs (x-y) < 1.0)
Этот код уже не слишком тривиален (что видно по обилию "грозных заголовков"), он был трудный в отладке. Указаны воплощения класса ''Sosedy'' и функции ''(~~)'' для типов ''Int'' и ``Char``. Кроме того, для класса типов ``RealFloat`` (куда входят типы ``Float`` и ``Double``) указано общее воплощение.
Заметим, что функция ``(~~~)`` будет реализована автоматически.
**Задание 1.** Написать воплощение класса ``Sosedy`` для других типов данных, напр. точек, слов и т.п.
**Задание 2.** Написать функции, использующие класса ``Sosedy`` независимо от типов данных, напр., для проверки свойства рефлексивности или транзитивности конкретных значений.
===== Урок 6. Начинаем писать «реальные программы» =====
Для того, чтобы наш код на Haskell был полноценным кодом, он должен быть организован надлежащим образом и мы должны уметь грамотно делать "ввод-вывод". И то, и другое подразумевает работу с монадами, конкретно, с монадой IO.
Однако, в качестве вводной урока, попробуем достичь заявленной цели, избегая определения монады.
==== 6.1 Структура «реальной программы» ====
Такая программа должны иметь точку входа, именованную "main", так же как и в других си-подобных языках. Предполагаем, что ее тип должен быть IO(). Вот классический пример:
main = print "Hello, world!"
Для многострочных программ нам необходимо использовать ключевое слово do, полный смысл которого будет ясен при изучении монад.
Вот как осуществляется получение аргументов командной строки в самом простом случае:
import System.Environment(getArgs)
main = do
s <- getArgs
print s
При запуске runghc fisrt.hs hello you! best 123 4 мы получим следующий вывод:
["hello","you!","best","123","4"]
Для более серьезных случаев разбора опций и значений командной строки используются специальные библиотеки: [[https://downloads.haskell.org/~ghc/latest/docs/html/libraries/base-4.9.0.0/System-Console-GetOpt.html|GetOpt]] ([[https://wiki.haskell.org/GetOpt/описание]] и [[https://wiki.haskell.org/High-level_option_handling_with_GetOpt|пример использования]]), [[http://hackage.haskell.org/package/ReadArgs|ReadArgs]] (простая и понятная библиотека, которая позволяет передавать простые значения), [[https://wiki.haskell.org/Command_line_option_parsers|список всех парсеров командной строки]].
Рассмотрим более сложный случай, когда нам необходимо получить данные из консоли:
main = do c <- getChar
print (c == 'y')
(здесь мы ожидаем, что пользователь введет "y" или что-либо другое -- соответственно программа выведет True или False).
Во втором примере мы видим, что некоторым аналогом присваивания выступает конструкция c<-getChar.
В качестве функции для вывода в простейшем случае используем print, которая сама использует функцию show для преобразования разных величин в строку. Но при использовании не латинских букв, выведутся номера символов:
main = print "Привет мир!"
получим:
"\1055\1088\1080\1074\1077\1090 \1084\1080\1088!"
Поэтому рекомендуется использовать функции putStr или putStrLn, но с ними придется делать самим преобразование величин в символы.
x = 7::Int
main = putStrLn $ "Привет мир:" ++ (show x)
==== Урок 6.2 Взаимодействие с STDIN-STDOUT ====
Список базовых функций ввода-вывода может быть найден тут: [[https://downloads.haskell.org/~ghc/latest/docs/html/libraries/base-4.12.0.0/Prelude.html#g:25|Basic Input and output]]
или на русском языке тут:
[[http://www.haskell.ru/io-13.html|Haskell-98. Основные операции ввода-вывода]].
Нам важны такие функции для работы со стандартными устройствами ввода-вывода из ''Prelude: putStr, print, getLine, readLn''.
Рассмотрим простой пример считывания строки и числа из устройства стандартного ввода. Как результат, просто вернем полученные данные на стандартный вывод.
import System.IO (hFlush, stdout)
main = do
putStr "Enter a string: "
hFlush stdout
str <- getLine
putStr "Enter an integer: "
hFlush stdout
num <- readLn :: IO Int
putStrLn $ str ++ " " ++ (show num)
(пример взят из [[http://rosettacode.org/wiki/User_input/Text#Haskell]])
Здесь важно отметить, что во-первых, мы должны "помочь" команде ''readLn'' правильно считать строку и вернуть ее как число (по умолчанию, она останется строкой). Для этого мы указываем тип '':: IO Int'' (просто ''Int'' --- не можем). Во-вторых, мы должны самостоятельно делать сброс буфера --- в документации указывается, что Haskell сам этого делать не будет.
Следующий, почти аналогичный пример взят из официального сборника
[[http://www.haskell.ru/io.html#sect21|Haskell Report]]
import System.IO
main = do
hSetBuffering stdout NoBuffering
putStr "Введите целое число: "
x1 <- readNum
putStr "Введите другое целое число: "
x2 <- readNum
putStr ("Их сумма равна " ++ show (x1+x2) ++ "\n")
where readNum :: IO Integer
readNum = readLn
Видим, что иначе решена проблема буферизации (отключена), и тоже решаем проблему ввода целых чисел (Указание сигнатуры типа позволяет избежать исправления типов ''x1,x2'' правилом по умолчанию).
Еще пример программы, которая меняет регистр вводимых букв:
import System.IO (hFlush, stdout)
import Char (toUpper)
main = do
putStr "Enter a string: "
hFlush stdout
str <- getLine
let str2 = map toUpper str
putStrLn str2
Отметим, что если функция не из монады ввода-вывода (т.е. не возращает подходящее значение), то мы используем конструкцию ''let y = f x'', вместо конструкции ''y <- f x''.
Но в любом случае, переменные, однажды определенные, будут далее неизменны. Для работы с изменяемыми переменными нам необходимо монаду ''IO'' обернуть монадой ''StateT'', что является нетривиальной задачей. Пример ниже.
==== Урок 6.3 Образец самостоятельного проекта ====
На уроке [[haskell#zamykanija_lokalnye_opredelenija|Замыкания...]]
мы разрабатывали функцию для решения квадратного уравнения. Оформим ее в виде самостоятельного модуля:
module Roots(roots) where
roots a b c =
let d = b^2 - 4*a*c
sd = sqrt d
x1 = (-b - sd) / (2*a)
x2 = (-b + sd) / (2*a)
in (x1,x2)
сохраним в файле ''Roots.hs''. Теперь используем его в небольшой интерактивной программе, которая спросит у нас значения коэффициентов, а потом вычислит корни и выведет их.
import Roots
import System.IO
main = do
hSetBuffering stdout NoBuffering
putStr "Enter an a: "
a <- readLn :: IO Double
putStr "Enter an b: "
b <- readLn :: IO Double
putStr "Enter an c: "
c <- readLn :: IO Double
putStrLn $ "Answer is: " ++ (show $ roots a b c)
let r = show $ roots a b c
print $ "Another method to do the same:" ++ r
Далее компилируем наши файлы как указано в разделе 6.4: ''ghc --make resolvroots.hs'' --- указываем только головной файл, файл модуля ''Roots.hs'' будет скомпилирован и слинкован автоматически.
**Задание к уроку.** Подготовить проект с вычислением собственной функции (суммы квадратов двух чисел, факториала числа и т.п.), при этом сделать два варианта ввода данных: интерактивно и с помощью списка аргумента командной строки.
Вот возможный вариант решения с инкрементом аргумента
import System.Environment(getArgs)
main = do
[s] <- getArgs
let n = (read s::Int) +1
print n
==== 6.4 Изменяемые переменные ====
Первый пример работы с состояниями в нашем курсе был указан выше, см. [[#ispolzovanie_monady_sostojanija|"2.6 Использование монады состояния"]]
В дальнейшем, чтобы научиться работать с изменяемыми переменными, нам необходимо изучить тему работы с монадами и монадными трансформерами. Это --- отдельная и трудная для беглого понимания тема. Вот небольшой пример, а тему оставим "на потом".
import Control.Monad.State
import System.IO
code :: StateT Int IO ()
code = do
x <- get
liftIO $ print x
liftIO $ putStr "Input number: "
y <- liftIO $ (readLn :: IO Int)
let z = x + y
put z
liftIO $ print z
return ()
main :: IO ()
main = do
hSetBuffering stdout NoBuffering
runStateT code 1
return ()
Сам пример ничего интересного не представляет, на Паскале он выглядел бы примерно так:
var
x,y,z,datastorage: integer;
begin
datastorage := 1;
x := datastorage;
writeln(x);
write('Input number: ');
readln(y);
z := x+y;
datastorage := z;
writeln(z);
end.
В Haskell у нас нет возможности изменять переменные, таких переменных попросту не существует. То, что в коде на Haskell выглядит как переменные ''x,y,z'', на самом деле --- неизменяемые константы (в этом случае монад --- еще сложнее). А для того, чтобы у нас была возможность использовать изменяемые переменные (в терминах Haskell --- изменяемые состояния), нам требуется специальная монада ''State'' c утилитами ''get'' и ''put''. Эту ситуацию можно мыслить как обращение к базе данных, когда ''x<-get'' позволяет получить некоторое значение и связать его с "переменной" ''x'', а ''put x'' отправляет значение ''x'' в эту базу.
Кроме того, мы не можем просто так в одном блоке %%main%% организовать работу и с вводом-выводом, и с сохранением состояний, как в обычных языках. Поэтому нам приходится организовывать два блока кода. Один из которых ''main'' отвечает традиционно за ввод-вывод, а другой, в нашем примере ''code'', отвечает за работу с состояниями. При этом, блок ''code'' теперь организован не как обычная монада состояния ''State'', а как монада-трансформер ''StateT'' над монадой ввода-вывода. Об этом мы будем позже говорить подробнее, а сейчас нам важно видеть, что в блоке ''code'' мы можем вызывать утилиты ввода-вывода с помощью ''liftIO''.
Несколько полезных примеров по работе с трансформером-монадой состояния ''StateT'' в связке с монадой ввода-вывода можно найти здесь [[https://wiki.haskell.org/Simple_StateT_use|Simple StateT use]]. Предложенный выше пример был, кстати, создан по мотивам этой статьи :)
==== 6.5 Работа с файлами ====
Работа с текстовыми файлами, в самом простом варианте, когда мы сразу, хотя и "ленивым образом", считываем весь текстовой файл в одну строку, разбиваем (или не разбиваем) ее в список строк по символу конца строк, затем обрабатываем.
Предположим, есть задача --- все буквенные символы текстового файла перевести в верхний регистр. Вот всё решение:
import Data.Char
main = do
file <- readFile "test.txt"
writeFile "testUp.txt" (map toUpper file)
Здесь операция ''readFile'' считывает весь файл и передает его в "переменную" ''file''. Затем, с помощью "чистой функции" ''toUpper'' мы преобразуем каждый Char-символ в строке file, используя функцию map для обработки списков --- в нашем случае, напомню, строки --- это списки символов. И, наконец, результат записывает в другой файл ''testUp.txt''.
Рассмотрим это же решение, но с разбивкой на строки --- возможно, когда-нибудь нам понадобится обработка отдельных строк.
import Data.Char
transform :: String -> String
transform str = map toUpper str
main = do
file <- readFile "test.txt"
let str_lst = lines file
let up_lst = map transform str_lst
writeFile "testUp.txt" (unlines up_lst)
Здесь "чистая функция" ''transform'' преобразует в строках символы к верхнему регистру. "Чистая функция" ''lines'' разбивает входящую строку на список строк по признаку конца строки, а функция ''unlines'', наоборот, получив список строк, склеивает их в одну.
Работа с "чистыми функциями" в монадическом коде (для нас пока это означает "внутри блока ''do''") должна осуществляться с помощью конструкции ''let''.
**Задание к уроку.** Написать программку, которая считывая текстовой файл, оставляет только буквы, а их в свою очередь приводит в нижний регистр. (//Указание:// использовать ''filter'', ''isAlpha'', ''isLetter'' или ''isLower'', ''toLower'', [[https://downloads.haskell.org/~ghc/latest/docs/html/libraries/base-4.10.1.0/Data-Char.html#v:LowercaseLetter|см. документацию по модулю Data.Char]])
==== 6.6 Запуск и компиляция ====
Запуск подготовленных указанным выше способом файлов возможен разными путями.
Во-первых, мы можем по-прежнему из ''ghci'' загружать нужный файл и указывать на выполнение функцию ''main''.
Во-вторых возможен запуск на прямое исполнение командой ''runghc myfile.hs'' (если будет запуск как скрипта, то всегда можно в первой строке указать
#!/usr/bin/runghc
В-третьих, компиляция в исполняемый двоичный код: ''ghc --make myfile.hs'', можно с указанием опций для оптимизации: ''ghc --make -O2 myfile.hs''. Полученный довольно объемный файл можно порой существенно ужать утилитой ''strip -s myfile'' (флаг ''--make'' для компиляции в нашей простой ситуации совершенно необязателен, по факту, обычно это происходит автоматически).
==== 6.7 Кратко о монаде IO ====
Для дальнейшего понимания работы "главной (части) программы", т.е. того, что начинается после ключевого слова ''main'' помимо понимания концепции и техники работы с монадами нужно понимание особой монады ввода-вывода ''IO''. Подробное изложение особенностей принципов ее работы выходит за рамки курса, однако, помимо уже указанных выше ссылок, можно порекомендовать отличный перевод [[https://habrahabr.ru/post/153383|Через тернии к Haskell (перевод). Часть-2]] и [[http://anton-k.github.io/ru-haskell-book/book/8.html|главу, посвященную монаде ''IO'' в учебнике А.Холомьева]].
===== Урок 7. Знакомство с монадами =====
Понятие монад пришло из чистой математики, из ее раздела под названием "теория категорий". И хотя полное понимание требует знакомства с математическим определением и свойствами, однако, возможно использование данного понятия в программировании, в частности, на языке Haskell, исходя из объяснения необходимости монад или чего-либо подобного для чистого языка функционального программирования и исходя из примеров применения различных монад.
Необходимость монад в чистом функциональном программировании возникает из ограничения, вытекающего из основных преимуществ данного стиля программирования. Вот такой парадокс. Так, Haskell не имеет возможность вводить глобальные переменные и как-то манипулировать ими внутри определений функций. Преимущество такого подхода дает надежность и уверенность для программиста (и для компилятора!!) в том, что в программе не будет побочных эффектов. Обратной стороной медали при этом будет то, что мы не можем с легкостью манипулировать, например, каким-то системными переменными, конфигурационными данными и т.п. У нас остается только возможность каждый раз при вызове функции вносить все требуемые данные в качестве параметров. Это загромождает описание функций и требует накладных расходов при реализации.
Другим примером такой необходимости является такое достоинство как декларативность, когда мы вместо императивного описания действий просто декларативно описываем уравнениями нужную нам функцию. Декларативный метод при этом очень удобен для автоматической оптимизации компилятором, когда есть возможность кэшировать вызовы функций с одними и теми же аргументами. Компилятор при этом может не вычислять вторично функцию от того же самого значения функции, менять порядок вычислений и т.п. Однако, в реальном программировании, нам часто необходимо описать именно порядок действий, например, ради "побочных эффектов", таких как вывод на печать, ввод данных с клавиатуры.
Монады предоставляют математический механизм, оставаясь в рамках чистого функционального программирования, эмулировать те или иные особенности стратегии последовательного выполнения упорядоченных действий.
Вот как об этом говорится в руководстве Джефа Ньюберна:
В языке Haskell монада определяется конструктором типов (назовем его ''m''), функцией, формирующей значение данного типа ''(a -> ma)'', и функцией, комбинирующей это монадическое значение с вычислениями, которые создают значения данного типа для формирования нового значения данного типа
''(ma ->(a -> mb)-> mb)''.
Говоря о монадах в целом, принято называть конструктор типов монады ''m''. Функцию, вычисляющую значения данного типа, обычно называют ''return'', а третья функция известна как ''bind'', но записывается как ''>>=''. Сигнатура функций такова:
data m a = ...
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
==== 7.1 Монада Maybe ====
Знакомство с монадами начнем с изучения монады ''Maybe''.
В Haskell определен следующий тип:
data Maybe a = Nothing | Just a deriving (Eq, Ord)
(Напомним, здесь ''Maybe'' --- это конструктор типов, в данном случае полиморфный, параметризованный произвольным типом ''a'', ''Nothing'' и ''Just'' --- конструкторы данных)
Можно задать значение данных, применив конструктор данных ''Jus''t к значению:
mynumber = Just 5
Полиморфные типы похожи на контейнеры, которые могут содержать значения многих различных типов. Так, ''Maybe Int'' можно считать контейнером типа ''Maybe'', который содержит ''Int'' с тэгом ''Just'', или ''Nothing''.
Теперь, предположим, что необходимо написать программу для обслуживания экспериментов по клонированию и скрещиванию овец. Нам потребуются функции ''mother'' и ''father''. Но если овцы клонированы, у них не всегда могут быть и отец, и мать!
Опишем возможность отсутствия матери или отца с помощью конструктора типов ''Maybe'':
type Sheep = ...
father :: Sheep -> Maybe Sheep
father = ...
mother :: Sheep -> Maybe Sheep
mother = ...
Вынесем конкретную реализацию этого типа и функций в отдельный модуль:{{:haskell:barans.hs|Barans.hs}}. Модуль задает овечью семью в виде бинарного смешанного дерева, предельно упрощен и далек от реальности.
Здесь каждый барашек задается по некоторому имени "i8" или "i12" и т.д. Все имена можно узнать в ''ghci'' функцией ''names''. В свою программу необходимо включить строку
import Barans
Итак, первое задание. Зададим функцию поиска дедушки --- отца матери:
import Barans
maternalGrandfather :: Sheep -> Maybe Sheep
maternalGrandfather s = case (mother s) of
Nothing -> Nothing
Just m -> father m
Задача будет еще сложнее, если мы захотим найти прадеда:
mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mothersPaternalGrandfather s = case (mother s) of
Nothing -> Nothing
Just m -> case (father m) of
Nothing -> Nothing
Just gf -> father gf
Такое описание уродливо и громоздко. Очевидно, что значение ''Nothing'' в любой точке вычисления приведет к ''Nothing'' в конечном результате, и гораздо удобнее выполнить данное преобразование один раз и удалить из программы подробные описания проверок ''case''.
import Barans
-- comb - комбинатор для упорядочивания операций, производимых Maybe
comb :: Maybe a -> (a -> Maybe b) -> Maybe b
comb Nothing _ = Nothing
comb (Just x) f = f x
-- теперь можно использовать `comb` для формирования сложных
-- последовательностей
mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mothersPaternalGrandfather s = (Just s) `comb` mother
`comb` father
`comb` father
Код не только стал более аккуратным, но с ним стало легче работать!
Более того, здравый смысл привел нас к созданию монады!
....
=== Урок 7.1.1 Формальное описание монад ===
Опишем теперь монаду ''Maybe'' формально:
data Maybe a = Nothing | Just a
instance Monad Maybe where
return = Just
Nothing >>= f = Nothing
(Just x) >>= f = f x
Смысл применения функции ''return'' заключается в простой упаковке исходного значения в <<монадическое значение>> (очень грубо, особенно для рассматриваемого случая монады Maybe, можно понимать монадическое значение как обертку или помещение в специальный контейнер). Смысл комбинатора ''>>='' заключается в передаче упакованного значения в //монадическую функцию//. А более широко, как мы увидим ниже --- в связывании двух монадических функций. Под монадическими функциями мы будем понимать функции особого вида, те, которые получают на вход обычное значение, а возвращают уже упаковнное, т.е. монадическое значение.
В нашем случае, функции ''mother'', ''father'' и все функции полученные из них (''mothersPaternalGrandfather'', ''maternalGrandfather''), являются монадическими --- на вход получают имя барашка-строку, а на выход отдают имя барашка внутри монады ''Maybe''. При их комбинировании все время приходится то распаковывать значения, то вновь их упаковывать: распаковкой заведует комбинатор ''>>='', а упаковку делают сами монадические функции. Выигрышем при этом является ясность и чистота программного кода, контроль при комбинировании. Иными словами, на Haskell, кроме случаев ввода-вывода и операций связанных с <<внешним миром>>, где мы вынуждены работать с монадой ''IO'', вполне можно обходиться и без монад. Но монады делаются код яснее, лаконичнее и увеличивают контроль над последовательностью при комбинировании функции, чего императивные языки не делают совсем (об этом подробнее будет в других главах).
**Задание к уроку.** Написать предикаты проверяющие, является ли данное значение значением ''Nothing'', значением, упакованным тегом ''Just''. Написать функцию распаковки из контейнера ''Just''.
=== Урок 7.1.2 Использование введенных комбинаторов для монадических функций ===
Вернемся к нашей задаче описания бараньего поголовья. Теперь наш код будет выглядеть почти также, но в более регулярном виде:
import Barans
mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mothersPaternalGrandfather s = return s >>= mother
>>= father
>>= father
Тоже самое с использованием ''do''-нотации:
import Barans
mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mothersPaternalGrandfather s = do
m <- mother s
gf <- father m
father gf
Ещё вариант возможен в форме композиции <<монадических функций>>, так как на самом деле, значение ''s'' нам в явном виде не нужно.
import Barans
import Control.Monad
-- mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mPGf :: Sheep -> Maybe Sheep
mPGf = return >=>
mother >=>
father >=>
father
или даже без return:
import Barans
import Control.Monad
-- mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mPGf :: Sheep -> Maybe Sheep
mPGf = mother >=>
father >=>
father
Здесь как раз видно, что обычные комбинаторы функции ''$'' и ''.'' имеют соответствующие аналоги для монадических функций: ''>>='' и ''>=>'', но в обратном порядке, как для PipeLine в Unix; если необходим привычный порядок комбинаторов, как в композициях функций, то можно использовать ''=<<'', ''<=<''. Правда, если комбинатор ''>>='' доступен сразу в модуле ''Prelude'', то комбинаторы ''>=>'', ''<=<'', ''=<<'' доступны либо при подключении модуля ''Control.Monad'', либо требуют простых определений самостоятельно, напр.:
f >=> g = \x -> (f x >>= g)
И, наконец, некоторые улучшения, используя модуль по поддержке монад:
import Barans
import Control.Monad
traceFamily :: Sheep -> [ (Sheep -> Maybe Sheep)] -> Maybe Sheep
traceFamily s l = foldM getParents s l
where getParents s f = f s
mothersPaternalGrandfather :: Sheep -> Maybe Sheep
mothersPaternalGrandfather s = traceFamily s [mother, father, father]
**Задания к уроку:** написать функции, возвращающие разных прабабушек или прадедушек.
Более сложное задание: написать функцию ''parents'', возвращающую список всех родителей и функцию ''grandparents'', возвращающую список бабушек и дедушек --- если таковые есть, и пустой список, если таковых нет.
**Решения.** :-)
import Barans
import Control.Monad -- only for grandparents2
import Data.Maybe
import Data.List
parents :: Sheep -> [Sheep]
parents s = (maybeToList $ mother s) ++ (maybeToList $ father s)
grandparents :: Sheep -> [Sheep]
grandparents s = (parents s) >>= parents
grandparents2 :: Sheep -> [Sheep]
grandparents2 = parents >=> parents
=== Урок 7.1.3 Некоторые хитрости ===
Для нас было бы мало пользы в концепции монад, если мы не смогли сделать код программ более изящным. Рассмотрим еще некоторые полезные функции и примеры для них.
В определении модуля {{:haskell:barans.hs|Barans.hs}} были введены экспортируемые функции ''father'' и ''mother'', для которых мы использовали инфиксную функцию ''`mplus`''.
Воспользуемся ей еще раз. Допустим, нам необходимо узнать, является ли данный барашек сироткой:
import Barans
import Control.Monad
import Data.Maybe
isOrphan x = isNothing (father x `mplus` mother x)
Разумеется, мы могли воспользоваться стандартной техникой с ''if''... ''then''... ''else'', но данный вариант компактнее!
Для компактификации мы можем использовать функцию ''guard''.
Например, у нас в стаде барашков есть некоторые селекционные барашки:
selected_barans = ["i3", "i5", "i6", "i9", "i12"]
Нужно написать функцию, которая возвращает (например ''Just "i6"'') имя селекционного папы, обернутого конструктором ''Just'', и ''Nothing'', если такового нет.
import Barans
import Control.Monad
import Data.Maybe
father_ifselected x =
do
p <- father x
guard (p `elem` selected_barans)
return(p)
Функция ''guard'' --- это вариации на тему <<охраны>> [[#urok_2_sposoby_opredelenija_funkcij|в определениях функции]], и более тематически близко --- в генераторах списков. Собственно о функции ''guard'' есть хорошее (но уже устаревшее) описание у Джефа Ньюберна в разделе [[https://wiki.haskell.org/All_About_Monads#Functions_for_use_with_MonadPlus|6.2.5 Functions for use with MonadPlus]]:
guard :: MonadPlus m => Bool -> m ()
guard p = if p then return () else mzero
"...Трюк к пониманию этой функции --- вспомнить закон для монад с нулем и плюсом (т.е. реализующих класс ''MonadPlus''), и то, что состояния
mzero >>= f == mzero
(где mzero в зависимости от монады может быть пустым списком [] или значением ''Nothing'' --- В.В.)
Таким образом, размещение функции ''guard'' в последовательности монадических операций если значение ''p'' будет ''False'' заставит последующие операции быть ''mzero''...."
Соответственно, если будет получено значение ''True'', то ''guard'' вернет значение ''()'' в монадической обёртке, однако, в типичном использовании мы просто перейдём к следующей строке с операцией. См. развёрнутые примеры использования в разделе [[#transformery_monad|7.4 Трансформеры монад]].
Конечно, мы не всегда можем воспользоваться функцией guard. Допустим, нам нужна функция
''nearst_selected_male_predecessor'', которая находит селекционного ближайшего предка по мужской линии (либо, если такового нет, возвращает ''Nothing''). Теперь нам потребуется обработка ситуации ''False'' (папа есть, но не селекционный, и надо смотреть дедушку и т.п.), нам придется воспользоваться традиционным ''if''... ''then''... ''else''
nearst_selected_male_predecessor x =
do
p <- father x
if (p `elem` selected_barans)
then return(p)
else nearst_selected_male_predecessor (p)
**Задания к уроку.** Написать функцию allparents, описывающую множество всех родителей в стаде; ''parentchild p c'', проверяющую, является ли ''p'' родителем для ''c''; функцию ''childs x'', составляющую список всех детишек барашка ''x''. И, наконец, функцию проверки, является ли барашек ''x1'' селекционным ребенком барашку ''x2''.
==== 7.2 Монада List ====
Монада ''List'' --- это новая точка зрения на применение списков. В данном случае, монада ''List'' вводит поддержку функций с неоднозначным результатом, а главное --- стратегию их связывания. Будем считать, что монадическая функция дает неоднозначный результат, если она возвращает список, а ее тип будет выглядеть примерно так:
f :: a -> [b]
Более формально, монада ''List'' вводится воплощением класса ''Monad'':
instance Monad [] where
return a = [a]
ma >>= f = concat $ map f ma
=== Урок 7.2.1 Примеры неоднозначных функций ===
Введем пару неоднозначных функций и оформим их в виде модуля:
module MultiValFunc where
ffive x = [x+1,x+2..x+n]
where n = (x `mod` 5) + 1
ftwo x = [x-1,x+1]
=== Урок 7.2.2 Примеры связывания неоднозначных функций ===
Зададим новую функцию ''h'', связав эти две новые функции:
h s = return s >>= ftwo >>= ffive
или проще так
h = ftwo >=> ffive -- здесь return можно написать, но необязательо!
или с ''do''-нотацией:
h s = do
p <- ftwo s
ffive p
Каждый способ имеет свои преимущества: первый --- лаконичный, второй --- более-менее классический, третий --- позволяет использовать промежуточные значения.
=== Урок 7.2.3 Какие задачи можно решать ===
Пусть задана функция
f = return >=>
ftwo >=>
ffive
Будем считать результат "несчастным", если среди возвращаемых итоговых значение есть число 13. Как нам проверить несчастность конкретного результата?
Примерно так:
13 `elem` f 10
Пусть теперь задана функция
g = ftwo >=>
ffive >=>
ffive >=>
ffive >=>
ftwo
Необходимо вывести список двузначных чисел с одинаковыми цифрами из результата. Введем необходимый предикат:
test77 m = ((m `mod` 11) == 0) && (10
Для фильтрования нужен фильтр:
test77list = filter test77
А использовать примерно так
test77list $ g 76
> [77,88,88,88]
Еще, вычисления монадного типа приводят нас к "открытию циклических" вычислений. Например, вот так:
loop 1 x = ffive =<< return x
loop n x = loop (n-1) =<< ffive x
Первый аргумент задает число повторов, второй --- исходное значение.
Вернёмся к ''do''-нотации. Рассмотрим функцию
g3 :: Integer -> [Integer]
g3 x = do
y1 <- ftwo x
y2 <- ffive y1
y3 <- ffive y2
return y3
Мы видим, что за счет ''do''-нотации она даже выглядит как традиционная функция. Значения ''y1,y2,y3'' позволяют получить доступ к промежуточным значениям вычисления. Но, к сожалению, это возможно только внутри монадного вычисления в блоке ''do''. Вне этого блока значения ''y1,y2,y3'' неопределены, и требуются специальные "ухищрения".
**Задание к уроку.** Назовем вычисление комбинированной неоднозначной функции счастливым, если на всех этапах ее вычисления в результатах есть двузначные числа с одинаковыми цифрами. Проверить, будет ли вычисление от конкретного аргумента счастливым.
//Замечание//. Можно попробовать "на счастье" ряд других предикатов: четность, делимость на 3, разность цифр и т.п.
=== Урок 7.2.4 Другой взгляд на списки ===
На уроке 3.7 мы разбирали понятие "определителя списков" и такой вот пример:
list = [ 2*x | x <- [1..57], 3 < x, x < 7 ]
Теперь, мы вправе сказать, что задана "неоднозначная" безаргументная функция, берущая ''x'' из списка чисел [1..57], проверяющая, чтобы оно входило в интервал между 3 и 7 и возвращающая в итоге список четных чисел вида ''2x''. Иными словами,
list = do
x <- [1..]
guard (3 < x && x < 7)
let y = 2*x
return y
Можно это рассмотреть и как комбинацию двух монадических неоднозначных функций.
Пусть ''getlist'' --- это любая неоднозначная функция с одним аргументом, например, в простейшем случае просто возвращающая список [1..57], без учета аргумента. Или любая функция из примеров выше. Монадическая функция ''check'' для аргумента ''x'' делает проверки, и при их выполнении, возвращает список с учетом всех возможных значений ''x''. Последняя функция ''getcheck'' является их монадической композицией.
getlist _ = [1..57]
check :: Integer -> [Integer]
check x = do
guard (3 < x && x < 7)
let y = 2*x
return y
getcheck = getlist >=> check
Подобно уроку 7.1.3 мы можем ввести ещё несколько полезных монадных функций. Например, функция ''liftM'':
liftM :: Monad m => (a -> b) -> m a -> m b
liftM f ma = do
a <- ma
return $ f a
Её смысл --- "поднятие" обычных функций для вычислений с монадическими значениями. Конечно, функция не станет монадической в смысле сигнатуры ''a -> m b'', но полученный результат тоже будет полезным. Например,
f :: Integer -> Integer
f n = 2*n
g = liftM f
> g [1,2,3]
[2,4,6]
> g Just 2
Just 4
> g Nothing
Nothing
И при этом функция ''g'' работает с разнообразными монадами!
=== Урок 7.2.5 Комбинированная задача ===
Сформулируем задачу: предположим, необходимо проводить цепочку вычислений функции ''g3'', заданной выше, только от тех аргументов функций, которые не делятся на 3.
В программном коде этой новой задачи мы как раз попробуем делать требуемые проверки, используя доступ к ''y1,y2,y3''.
Кроме того, при решении будем связывать вычисления с помощью монады ''Maybe''. И, кстати, таким образом, мы придём к одному из завершающих понятий в теме монад --- //монадным трансформерам//!!
В данной первичной версии, связывание как таковое пока не очевидно, оно представляет собой многочисленные проверки ''if'', упаковки и распаковки в списки и контейнер ''Maybe''. Суть их сводится к тому, что если аргумент будущего вычисления функции не делится на 3, то мы помечаем меткой ''Nothing'' текущий (и таким образом, все будущие итерации вычислений от этого аргумента). А если делится, то мы делаем упаковку с помощью ''Just'' и передачу в список всех результатов с помощью ''return'' (см. ниже, особенно на примере вычисления значений ''l2'' и ''l3'').
Сделаем заготовку:
test3 n = ((n `mod` 3) /= 0)
и оформим первую версию решения:
import MultiValFunc
import Control.Monad
import Data.Maybe
g3l x = if test3 x
then
do
y1 <- ftwo x
l1 <- if test3 y1 then return $ Just y1 else return Nothing
l2 <- if isJust l1
then
do
y2 <- ffive y1
return $ if test3 y2 then Just y2 else Nothing
else return Nothing
l3 <- if isJust l2
then
do
y3 <- ffive $ fromJust l2
return $ Just y3
else return Nothing
return l3
else return Nothing
И при вычислении получим примерно такое:
> g3l 73
[Nothing,Nothing,Just 77,Just 78,Just 78,Just 79,Just 80,Nothing,Just 80,Just 81,Just 82,Just 83,Just 84]
По шагам...
...
Видим, что количество точек ветвления (обработки ''if-then-else'') примерно равно таковому при программировании на привычных императивных языках. Но оказывается, в Haskell мы можем значительно сократить объем кода и само решение будет намного элегантнее.
==== 7.3 Монада State ====
Образцы применения данной монады уже рассматривались в нашем курсе ранее...
Однако насколько необходимо формальное и подробное объяснение принципов и деталей реализации этой монады в рамках нашего курса --- до сих вопрос. Дело в том, что если использование простых утилит ''get'' и ''put'' интуитивно понятно, и может быть сразу использовано в практическом программировании в рамках ''do''-блоков, то изучение того, как реализованы ''return'' и связывание ''bind'' уже достаточно сложно и не дает немедленной помощи при написании программ. То же самое касается и общей идеи того, как реализована эмуляция состояний "чистыми" функциями языка Haskell.
Итак, общая идея состоит в том, что если к данной нужной нам функции вида ''f:a->b'', а особенно к цепочке вложенных функций (т.е. композиции)
f1 >.> f2 >.> f3 >.> ... >.> fn
или в более традиционной записи на Haskell:
fn . ... . f3 . f2 . f1
где
f1 :: a0 -> a1
f2 :: a1 -> a2
...
fn :: a(n-1) -> an
мы хотели бы добавить возможность чтение/записи некоторого глобального состояния, т.е. глобальной переменной в терминах традиционного программирования. Глобальных переменных в Haskell нет, поэтому мы можем добавить к каждой функции ещё одну "лишнюю" переменную, которая будет переносить внутрь функции информацию о таком состоянии и это значение, возможно измененное функцией, должно быть добавлено к возвращаемому результату. Таким образом, тип наших функций будет изменён так:
f1 :: (a0,s) -> (a1,s)
f2 :: (a1,s) -> (a2,s)
...
fn :: (a(n-1),s) -> (an,s)
или даже так:
f1 :: a0 -> s -> (a1,s)
f2 :: a1 -> s -> (a2,s)
...
fn :: a(n-1) -> s -> (an,s)
но в таком случае, мы должны связывать цепочку функций не обычной композицией (прямой или обратной), а более сложной функцией, которая сама будет распаковывать пары результатов и передавать два аргумента в следующую функцию.
Вот по этому пути и пошли создатели монады ''State''. Фактически, монадические функции, которые работают в монаде ''State'', возвращают пару из типа ''(b,s)'', и принимают два значения, принадлежащие типам ''a'' и ''s''. Но делают это не напрямую, а скрытно, с помощью специального api так, что у программиста создается иллюзия, что его функция принимает на вход значение типа ''a'', возвращает значение типа ''b'', а обращение к состоянию напоминает обращение к базе данных внутри тела задаваемой функции (это было подробнее описано в [[#izmenjaemye_peremennye|"6.4 Изменяемые переменные"]])
Далее я начну описывать формальности и особенности реализации монады ''State'', а также некоторые простейшие примеры ее использования и описания монадических функций в различном стиле.
=== 7.3.1 Формальное описание State ===
newtype State s b = State (s -> (b, s))
или, если мы не гонимся за эффективностью:
data State s b = State (s -> (b, s))
Теперь введем формальное определение ''return''
return :: a -> State s a
return x = State (\st -> (x, st))
Это определение показывает, что применение ''return'' (в монаде ''State'') к аргументу ''x'' создает функцию преобразования состояния, которая на самом деле не изменяет состояние вообще, но которая «возвращает» значение ''x'', переданное в самом начале. И важное, функция с тэгом ''State'' в правой части уравнения выше и есть <<монадическое значение>> или <<трансформер состояния>>, как его иногда называют. Если для монад ''Maybe'' и ''List'', которые мы изучили раньше, монадическим значением было <<нечто>> (как правило числа, строки или иные обычные объекты) в контейнере, то теперь это <<нечто>> стало функцией.
Таким образом, если ранее монадическими функциями были, например, функции такого типа ''f :: a -> Maybe b'', то в случае монады ''State'' станут такими
f :: a -> State s a
f x = State (\st -> (какое-то конкретное описание тела функциии) -> (x', st'))
где ''x''' ''s''' --- результаты вычисления (значение и состояние) функцией ''f''.
Введем формальное определение связывания
mv >>= g = State (\st ->
let (State ff) = mv
(y, st') = ff st
(State gg) = g y
in gg st')
и разберем его по шагам:
- во второй строке мы фактически распаковываем монадическое значение ''mv'' и полученной функции присваиваем имя ''ff'';
- в третье строке запускаем эту функцию со значением состояния ''ff st'' и результат передаем в пару ''(y, st')'', где ''y'' --- новое значение, а ''st''' --- новое состояние;
- в четвёртой строке мы распаковываем частичное применение функции ''g y'' (выглядит как запуск функции ''g'' с аргументом ''y'') и полученной функции присваиваем имя ''gg'';
- в последней строке осуществляем запуск этой функции со значение состояния, которое мы получили на втором шаге ''gg st'''.
И зададим две важные для нас утилиты:
get :: m s
get = State (\s -> (s, s))
для получения состояния и
put :: s -> m()
put s = State (\_ -> ((), s))
для изменения состояния. При этом, функция ''get'' в качестве возвращаемого значения вернёт ''s''. А функция ''put'' вернёт значение (), но помимо этого, переданный ей параметр-состояние поместит в <<условное хранилище>>, иначе говоря, изменит это состояние на переданной в качестве параметра значение.
И ещё три функции для запуска вычислений внутри монады ''State'':
runState :: State s a -> s -> (a, s)
runState (State f) init_st = f init_st
evalState :: State s a -> s -> a
evalState mv init_st = fst (runState mv init_st)
execState :: State s a -> s -> s
execState mv init_st = snd (runState mv init_st)
Основной является функция ''runState'', а функции ''evalState'' и ''execState'' являются производными от нее, возвращая конечное значение-результат или только последнее значение состояния соответственно. Функция ''runState'' возвращает пару
''(a,s)'', т.е. и результат, и состояние. По своей сути эта функция ''runState'' (и две производные функции соответственно) распаковывает (т.е. снимает тэг ''State'') с монадического значения --- функции-трансформатора состояния ''f'', а потом запускает ее с начальным значение состояния ''init_st''. Кстати, если до этого мы создавали монадическую функцию, например, ''f''', то ''f = f'(a)''. Вспомним [[#ispolzovanie_monady_sostojanija|пример из раздела 2.6]], где с помощью монады ''State'' мы задавали факториал, --- здесь функция ''f''' как раз являлась монадической функцией, а ''(f' n)'' --- уже было применение монадической функции к значению ''n'' и было по сути монадическим значением.
Использовали определения из http://mvanier.livejournal.com/5406.html и из
http://mvanier.livejournal.com/5846.html
=== 7.3.2 Различные примеры использования State ===
Рассмотрим теперь очень простые монадические функции и различные способы их задания. В новом файле в самом начале необходимо импортировать модуль управления монадами:
import Control.Monad.State
Теперь зададим простейшую монадическую функцию ''addA''. Ее аргументом будет число ''a'', принадлежащее типу ''Int'', а состояние ''s'' будет принадлежать типу ''String'':
addA :: Int -> State String Int
addA a = State (\s -> (a, ((show a) ++ s)))
Функция преобразует числовой аргумент в строку и конкатенирует его к текущему состоянию.
К сожалению, такой способ задания (с помощью **конструктора данных** (значений)) ''State'' не работает в современных версиях ''ghc'' при импорте ''Control.Monad.State''. Это исторически связано с переходом на использование в пакете монадного трансформера ''StateT''. Для совместимости вместо конструктора данных ''State'' можно использовать функцию ''state'', и таким образом, пример будет выглядеть в современном виде так:
import Control.Monad.State
addA :: Int -> State String Int
addA a = state (\s -> (a, ((show a) ++ s)))
Подробнее об этом изменении API можно прочитать тут
[[http://stackoverflow.com/questions/24103108/where-is-the-data-constructor-for-state|Where is the data constructor for 'State'?]], [[http://stackoverflow.com/questions/14157090/has-the-control-monad-state-api-changed-recently|Has the Control.Monad.State API changed recently?]] и тут [[https://mail.haskell.org/pipermail/beginners/2011-October/008882.html|State Monad - Not in scope: data constructor State]]
Более привычно для нас (и более стабильно в плане независимости от версии пакета ''Control.Monad.State'') задать эту функцию с помощью утилит ''put'' и ''get'' следующим образом:
addA a = do
s <- get
let t = (show a) ++ s
put t
return a
В любом случае задания, запуск будет осуществятся примерно так:
execState (addA 5) "hello"
Следующая функция ''addbum0'' является монадным значением, или как мы говорим <<трансформером состояния>>, так как она не зависит от какого-либо аргумента (зависит только от значения состояния).
addbum0 :: State String Int
addbum0 = State (\s -> (0, s ++ "bum"))
Аналогично, она может быть описана так:
addbum0 :: State String Int
addbum0 = do
s <- get
let t = s ++ "bum"
put t
return 0
Далее небольшая коллекция различным образом заданных монадических функций, использующих состояние (возможно, есть ошибки!!)
addbum :: Int -> State String Int
addbum x = State (\s -> (x, s ++ "bum"))
getPar a = State (\s -> (a,s))
go1 n = return n >>= addA >> addbum0 >>= addbum
-- или еще проще:
go1 >=> addA >=> addbum0 >=> addbum
go2 n = do
p1 <- addA n
p2 <- addA p1
addA p2
go2_1 n = do
p1 <- addA n
p2 <- addA p1
return p2
go3 n = do
g <- get
let g' = g ++ (show n)
put g'
return n
go3_1 n = do
g <- get
(x,g') <- return (2, g ++ "hi")
put g'
return x
go4 n = do
s <- get
return (n+1)
go4_1 n = get >>= return
go5 n = return n
go5_2 n = do
return n
{-
go4_2 = do
s <- get
return
-}
-- depack :: State s a = (a,s)
-- depack State (\s -> (a,s)) = (a,s)
depack :: State s a -> s -> (a,s)
depack (State f) = f
**Задание к уроку.** На основании примеров [[#ispolzovanie_monady_sostojanija|"2.6 Использование монады состояния"]] и
[[#izmenjaemye_peremennye|"6.4 Изменяемые переменные"]]
придумать цепочку из 3--4 простых функций или рекурсивно заданных функций, которые в процессе работы передают не только результат, но и какое-то промежуточное состояние.
==== 7.4 Трансформеры монад ====
Подготовим вторую версию функции для задачи выше. Предыдущее решение было <<лобовым>>, и хотя в аналогичном решении при //императивном программировании// нет ничего необычного в большом количестве вложенных проверок ''if'', мы попробуем сделать наш код изящнее. Для этого нам понадобиться следующий уровень монадной абстракции: //трансформеры монад// или //монадные трансформеры// (думаю, первый термин более адекватный).
g3mt :: Integer -> MaybeT [] Integer
g3mt x = do
guard (test3 x)
m1 <- lift $ ftwo x
guard (test3 m1)
m2 <- lift $ ffive m1
guard (test3 m2)
m3 <- lift $ ffive m2
return m3
rg3mt :: Integer -> [Maybe Integer]
rg3mt = runMaybeT . g3mt
(необходимо кое-что <<допилить напильником>>, чтобы код работал в разных версиях GHC: в современных версиях достаточно строки ''import Control.Monad.Trans.Maybe'', в более древних версиях необходимо либо самим писать реализацию трансформера, см. [[https://wiki.haskell.org/New_monads/MaybeT|New monads - MaybeT]]) или подключать дополнительные пакеты, см. [[https://hackage.haskell.org/package/MaybeT-0.1.2/docs/Control-Monad-Maybe.html|Control.Monad.Maybe]] или [[https://hackage.haskell.org/package/transformers-0.5.4.0/docs/Control-Monad-Trans-Maybe.html|Control.Monad.Trans.Maybe]])
Запуск и тест:
> rg3mt 73
[Nothing,Nothing,Just 77,Just 78,Just 78,Just 79,Just 80,Nothing,Just 80,Just 81,Just 82,Just 83,Just 84]
Мы видим, что код и правда получился кратким и изящным. Цена вопроса --- это существенные мозговые усилия по вдумчивому освоению идей монад, трансформеров монад и API (различных функций-утилит), связанных с этим.
Прокомментируем этот пример подробнее, тут прежде всего стоит отметить, что пример всё-таки несколько <<надуманный>>, и поставленную задачу можно решить безо всяких трансформеров и Maybe-функционала:
g3mt x = do
guard (test3 x)
m1 <- ftwo x
guard (test3 m1)
m2 <- ffive m1
guard (test3 m2)
m3 <- ffive m2
return m3
тогда и запуск даёт более простой ответ:
> g3mt 73
[77,78,78,79,80,80,81,82,83,84]
Чтобы обосновать наличие Maybe-функционала, можно было бы, например, сказать, что нам необходимо сохранить какую-то информацию о неудачных ветвях вычислений, вычислить их количество.
Само преобразование с помощью трансформера ''MaybeT'' монады ''[]'' (''List'') выразилось <<в обволакивании>> с помощью тега Just каждого значения в списках-результатах монадических функций ''ftwo'' и ''ffive'' (конкретно мы этого добились с помощью функции ''lift''). И с помощью служебной функции-запускалки ''runMaybeT'' (которая всего лишь убирает тэг ''MaybeT'') в итоге получилась новая монадическая функция ''rg3mt'' со значениями вида ''[Maybe Integer]''.
Далее, рассмотрим ещё одно "вложение", ещё один трансформер, который увеличит функциональность примера путём работы с системой ввода-вывода.
==== 7.5 Пример простого парсера ====
Начнем проектирование парсера! :-)
Запуск парсера удобно делать в GHCI. Затем вызываем функцию parseArg с разбираемой строкой, напр.:
parseArg "ac", которая возвращает список всех возможных значение: чисел (16-ричных, 10-чных) или слов.
import Control.Monad
import Data.Char
data Parsed = Digit Integer | Hex Integer | Word String deriving Show
parseHexDigit :: Parsed -> Char -> [Parsed]
parseHexDigit (Hex n) c =
if isHexDigit c
then return (Hex ((n*16) + toInteger (digitToInt c)))
else mzero
parseHexDigit _ _ = mzero
parseDigit :: Parsed -> Char -> [Parsed]
parseDigit (Digit n) c =
if isDigit c
then return (Digit ((n*10) + toInteger (digitToInt c)))
else mzero
parseDigit _ _ = mzero
parseWord :: Parsed -> Char -> [Parsed]
parseWord (Word s) c =
if isAlpha c
then return (Word (s ++ [c]))
else mzero
parseWord _ _ = mzero
parse :: Parsed -> Char -> [Parsed]
parse p c = (parseHexDigit p c) `mplus`
(parseDigit p c) `mplus`
(parseWord p c)
parseArg :: String -> [Parsed]
parseArg s = do
init <- (return (Hex 0)) `mplus`
(return (Digit 0)) `mplus`
(return (Word ""))
foldM parse init s
===== Урок 8. Грамматики. Парсеры =====
Предыдущее упражнение показало частный пример разработки простого парсера. Однако, более общая проблема разработки парсеров для //Контекстно-Свободных Грамматик// (КС-грамматик, cfg (context-free grammar)) требует и более изощренных методов. Дадим определение КС-грамматик.
**Определение 1.**
Пусть даны //VT// --- алфавит (множество терминальных символов), //VN// --- множество нетерминальных (служебных) символов, причем //VT// ∩ //VN// = ∅ (т.е. пересечение данных множеств пусто), //P// --- конечное множество правил (продукций), каждое из которых имеет вид //A -> a//, где //A// ∈ //VN//, //a// ∈ (//VT// ∪ //VN//)*, //S//∈ //VN// --- стартовый символ.
Тогда мы говорим, что задана грамматика //G// = T, VN, P, S//>.
Более точно, мы даже задали //контекстно-свободную// грамматику, или КС-грамматику. КС-грамматики занимают особую роль в проектировании языков программирования и компиляторов. Как правило, современные языки описываются некоторой КС-грамматикой. Есть и другие виды грамматик: более общие //контекстно-зависимые// и более специализированные, //регулярные//. При этом, регулярные являются подмножеством контекстно-свободных грамматик, а контекстно-свободные являются подмножеством контекстно-зависимых грамматик.
**Определение 2.**
Пусть (//A// -> β) ∈ //P// --- правило, γ, δ --- любые цепочки символов (слова) из множества
(//VT// ∪ //VN//)*.
Тогда говорят, что "из γ//A//δ непосредственно выводится γβδ в грамматике //G// (при помощи данного правила)" и обозначают: γ//A//δ ⇒ γβδ(//G//).
**Определение 3.**
Пусть α1, α2, ..., α//m// --- цепочки из множества
(//VT// ∪ //VN//)* и
α1⇒α2, ..., α//m//-1⇒α//m//.
Тогда мы пишем: α1 ⇒* α//m// и говорим, что
"из α1 выводится α//m// в грамматике //G//".
**Определение 4.**
Язык, порождаемый грамматикой //G//, определим как
//L//(//G//) = { //w// | //w// ∈ //VT//*, //S// ⇒* //w// }.
Другими словами, язык есть множество терминальных цепочек (слов), выводимых
из начального нетерминала грамматики. И таким образом, первой задачей проектируемого парсера будет синтаксический анализ принадлежности слов данной грамматике, т.е. возможно ли вывести то или иное слово из стартового символа с помощью данных грамматических правил.
**Упражнение 1**. Составить грамматику для языка, где //VT = {a,b,c}// и
//L = {wcwT | w ∈ {a,b}* }//.
**Упражнение 2**. Составить грамматику для языка, где //VT = {a,b}// и
//L = {wwT | w ∈ VT* }//.
**Упражнение 3**. Составить грамматику для языка, где //VT = {a,b}// и
//L = {w | w = wT, w ∈ VT* }//.
**Упражнение 4**. Составить грамматику для языка сбалансированных скобок (терминалами будут только скобки). Например: <<()()>>, <<(())>>.
Решением первого упражнения будет следующая грамматика: //VN = {S}, S = S// и //P// определено следующим образом: //S -> c;// //S -> aSa;// //S -> bSb.// Часто для удобства пишут тоже самое более компактно: //S -> c | aSa | bSb//.
**Упражнение 5 (на лето)**. Написать транслятор для арифметических выражений из обычной в польскую (обратную) запись и наоборот. Для этого надо описать какой-то узкий вид арифметических выражений над целыми числами (''Integer''), с переменными, бинарными операциями (например, плюс и умножение), унарными операциями (например, возведение в квадрат, смену знака, факториал). Здесь уже нужно будет реализовать не только валидатор, проверяющий с помощью свёрток грамматическую правильность, но и генерацию дерева синтаксического разбора, позволяющее легко переводить из одной записи в другую, или проводить исполнение (вычисление) разобранных выражений.
**Определение 5.** [C. 44]
Деревом вывода //D// (или деревом синтаксического разбора) называется помеченное упорядоченное дерево в КС-грамматике, если
- Каждая вершина (узел) имеет метку --- символ из алфавита (//VT// ∪ //VN//).
- Корень дерева //D// помечен символом //S//.
- Если узел имеет по крайней мере одно потомка, то его метка должны быть нетерминалом.
- Если //n//1,...,//n////k// --- прямые потомки узла //n//, перечисленные слева направо, с метками //A//1,...,//A////k// соответственно, а метка узла //n// есть //A//, то //A// ⇒ //A//1...//A////k// в данной грамматике //G// = T, VN, P, S//>.
==== Урок 8.1 Восходящий Парсер ====
Вернёмся ещё раз к теме простой грамматики сбалансированных скобок. Рассмотрим упрощенную версию, когда и терминалы, и нетерминалы будут представлены символами из ''Char''.
терминалы: ''()''
нетерминал: ''S''
продукционные правила: ''S -> ()|(S)|SS''
Для дальнейшего описания нам потребуется техника монад.
import Control.Monad
import Data.Maybe
Проверим наличие только скобок во входной строке.
checksymb :: Char -> Char
checksymb c | (c `elem` "()") = c
| otherwise = error "There is an illegal symbol!"
Опишем продукционные правила как функции свёртки:
prodrule :: String -> Maybe Char
prodrule "()" = Just 'S'
prodrule "(S)" = Just 'S'
prodrule "SS" = Just 'S'
prodrule _ = Nothing
Воспользуемся общей схемой "восходящего анализатора".
0. На вход для анализа получаем строку символов.
В нашем представлении это будет список (стек) ''[Char]'', его символизирует переменная ''ss''.
Проектируемый парсер будет работать с парой ''(String,String)'' у которой первый элемент --- входная (точнее --- укорачиваемая текущая строка), а второй элемент ---
строка-магазин ''mss'' обрабатываемых на каждом шагу нетерминалов.
1. Отщепляем первый элемент ''s'' списка.
И, прежде чем поместить его в магазин ''mss'', проверяем его на корректность.
transfer :: (String,String) -> (String,String)
transfer ((s:ss),mss) = (ss, ((checksymb s):mss))
transfer ([],m) = ([], m)
Поместим его в магазин.
2. Пара <<технических>> функций. Функция ''justadd2list''
передаст результат удачно выполненной продукции обратно в магазин
(или выставит флаг ''Nothing'' в случае неудачи) и обернёт его монадой ''Maybe''.
Функция ''mmplus'' действует немного подобно своей тёзке ''mplus'' из ''MonadPlus'':
соединяя два аргумента --- пары (входная строка, магазин), причём в первом
аргументе-паре магазин обёрнут монадой ''Maybe''. В соответствии с обёрткой, если она ''Nothing'', то возвращаем второй аргумент, если ''(Just mss)'', то снимаем обёртку и возвращаем значение первого аргумента.
justadd2list :: Maybe a -> [a] -> Maybe [a]
(Just x) `justadd2list` mss = Just (x:mss)
Nothing `justadd2list` _ = Nothing
mmplus :: (t, Maybe t1) -> (t,t1) -> (t,t1)
(_, Nothing) `mmplus` t = t
(ss, Just mss) `mmplus` _ = (ss,mss)
3. Если в магазине есть два или три символа, извлечем их из него и попытаемся применить продукционное правило. Обратим внимание, что применяя продукционное правило, меняем порядок символов, извлечённых из магазина --- располагая их именно так как они шли в исходной строке (учитывая свёртку). Полученный нетерминал ''S'' вернем в магазин ''mss''.
use2symbols :: [Char] -> Maybe [Char]
use2symbols (m1:m2:mss) = prodrule [m2,m1] `justadd2list` mss
use2symbols _ = Nothing
use3symbols :: [Char] -> Maybe [Char]
use3symbols (m1:m2:m3:mss) = prodrule [m3,m2,m1] `justadd2list` mss
use3symbols _ = Nothing
Если продукцию применить не можем (выставляем флаг ''Nothing''), переходим к следующему шагу.
4. Если в шаге 3 мы не смогли применить продукции, переходим к шагу 5.
Если на шаге 3 мы смогли применить продукцию, то вновь возвращаемся к началу шага 3.
step :: (String,String) -> (String,String)
step ([],mss) | (isNothing res) = ([],mss)
| otherwise = step ([],(fromJust res))
where res :: Maybe String
res = (use2symbols mss `mplus` use3symbols mss)
step (ss,mss) = let
t = (ss,(use2symbols mss `mplus` use3symbols mss)) `mmplus` (transfer (ss,mss)) in step t
5. Кончились ли элементы во входном списке? Если да, то смотрим результаты парсинга:
получился единственный нетерминал ''S'' --- значит, все распозналось, если осталось что-то еще,
то не распозналось.. Если элементы во входном списке еще остались, то переходим к шагу 1.
Ниже применяем полученные функции для создания парсера ''parse''.
parse teststr = if (mss == "S")
then teststr ++ " is valid"
else teststr ++ " isn't valid"
where (_,mss) = step (teststr,[])
**Проверяем результат**
parse "()(())"
"()(())" is valid
parse "()("
"()(" isn't valid
{{:haskell:brgr.lhs|Скачать готовый файл}}, содержащий весь приведённый выше код.
==== Урок 8.2 Парсеры по Нотону ====
Определим тип парсеров в соответствии с рекомендацией Грэхама Нотона в статье...
[[http://ru.wikibooks.org/wiki/%D0%9C%D0%BE%D0%BD%D0%B0%D0%B4%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%BA%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D1%8B_%D0%BF%D0%B0%D1%80%D1%81%D0%B5%D1%80%D0%BE%D0%B2|Монадические комбинаторы парсеров]]
newtype Parser a = Parser (String -> [(a,String)])
Таким образом, парсер будет функцией, которая принимает строку в качестве аргумента и возвращает некоторый список результатов. Пустой список результатов будет обозначать неудачный разбор. В случае успеха, каждый результат в списке будет представлять пару, чей первый компонент будет значение некоторого типа (обычно --- некоторое дерево синтаксического разбора, или иное значение, например, арифметического выражения). Второй компонент будет неразобранным остатком входной строки. Список аргументов в качестве результата позволит нам конструировать парсеры для неоднозначных грамматик, со списком вариантов разбора, если строка может быть разобрана различными путями.
Функция, убирающая тэг у значения типа Parser
parse (Parser p) = p
будет нам полезной для запуска наших парсеров в будущем, например:
> parse myparser "helloworld!"
> [((),"")]