Содержание

Haskell: введение в функциональное программирование

Автор: к.ф.-м.н., доцент кафедры информатики В.Н. Власов


удобный для просмотра вид

Ссылки на важные ресурсы по Haskell

  1. Основной сайт разработчиков (англ.) Haskell.org (есть небольшой раздел на русском языке).
  2. Сайт с переводом основной документации по синтаксису языка (рус.) Haskell-98.
  3. Ряд статей на сайте RSDN.org (рус.) о декларативном, функциональном программировании и о Haskell, в частности Декларативное программирование . Особый интерес для начинающих представляют статьи Мягкое введение в Haskell-1 и Мягкое введение в Haskell-2, Функциональные типы и композиция функций в Хаскелле.МОНАДЫ!!!
  4. Цикл переводов «Еще Одно Руководство по Монадам» от Mike Vanier в 4-х частях: Основы, Функции '>>=' и return, Монадные законы, Монада Maybe и монада списка (возможно, самое лучшее введение по монадам на русском языке). Оригиналы и ещё 4-е статьи смотреть тут Mike's World-O-Programming;
  5. «Жесткое введение» в Haskell Через тернии к Haskell (перевод). 2/2;
  6. Официальная документация на модуль Prelude
  7. Учебник по Haskell. Антон Холомьёв (пока лучший учебник на русском!!)

Урок 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}

Многострочные записи делают следующим образом:

> :{
| let f :: Int -> Int
|     f n = n * 2
> :}

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

> :set +m:
| let f :: Int -> Int
|     f n = n * 2

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

Урок 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 – это функция от двух переменных. Тип у них тоже будет разный, и это можно будет узнать командой :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

Два странных (для программистов из «другого» мира) оператора «.» и «$». Сначала рекомендуется о них прочесть статьи:

Функциональные типы и композиция функций в Хаскелле

Еще Одно Руководство по Монадам (часть 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
 
<interactive>:1:4:
    No instance for (Fractional Integer)
      arising from the literal `2.0' at <interactive>:1:4-6

Почему ошибки не было в первом случае, и откуда она взялась во втором? И как ее избежать? Ведь в других языках приведение констант делает автоматически…

2.6 Использование монады состояния

Пока без комментариев, вычисление факториала:

import Control.Monad.State

fact' :: Integer -> State Integer Integer -- тип состояния - Int, тип результата - тоже Int
fact' 0 = do
    acc <- get -- получаем накопленный результат
    return acc -- возвращаем его
fact' n = do
    acc <- get -- получаем аккумулятор
    put (acc * n) -- домножаем его на n и сохраняем
    fact' (n - 1) -- продолжаем вычисление факториала

-- fact :: Int -> Int
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)

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;
  • zip xs ys — вернет список пар вида (x,y), в каждой из которых первый элемент x является очередным элементом первого списка xs, а второй элемент y — второго списка ys;
  • zip xs [0..] — нумерация (альтернативная, ср. с п.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;
  • ltist1 ++ 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 ]

В примере также показан способ построения списков, называемых диапазон:

  • [1..] — список всех натуральных чисел;
  • [1,3..] — список всех нечетных натуральных чисел;
  • [1,3..99] — список всех нечетных натуральных чисел от 1 до 99;

Простые задачи. Описать списки четных и нечетных чисел, список квадратов четных чисел, список кубов нечетных. Выбрать из них список чисел, делящихся на 7, от 2000 до 10000.

Задача 1. Написать код, генерирующий потенциально бесконечный список чисел Фиббоначи. Рассмотреть возможности «лобового решения» с бинарной рекурсией и оптимизации. (см. варианты решения)

Задача 2. Написать код, генерирующий потенциально бесконечный список простых чисел. Оптимизация по скорости, памяти и краткости кода не требуется. (см. решение здесь)

3.8 Дополнительные функции из модуля Data.List

Для целей «разгрузки» базового модуля 'Prelude' в плане работы со списками, создан модуль Data.List, который содержит помимо основных дополнительные удобные функции. Модуль необходимо вызывать квалифицированно:

import qualiаfied 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
)

Но что делать, если возникает конфликт имен при импорте? Рассмотрим возможные решения ниже.

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

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<n;i++){
 for (j=0;j<n;j++){
   if(j<i) {
     d = distance(da[j], da[i]);
     res.push(d);
   }
 }
};
alert ('res: '+res);

Основная «соль» в том, что решение мы делаем через использование двух вложенных циклов. Как провести аналогичные вычисления на функциональном языке?

Прежде всего, воспользуемся типом данных точки 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<n]
maximum $ rset  ((length da) -1)

Это решение очень наглядно, вполне математично. Однако и в нём есть неэффективные места, связанные с особенностью работы списков в 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<n]
Прокомментируем его. Во-первых, если длину списка 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

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

Урок 6. Начинаем писать «реальные программы»

Для того, чтобы наш код на Haskell был полноценным кодом, он должен быть организован надлежащим образом и мы должны уметь грамотно делать «ввод-вывод». И то, и другое подразумевает работу с монадами, конкретно, с монадой IO.

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

Урок 6.1 Структура «реальной программы»

Такая программа должны иметь точку входа, именованную «main», так же как и в других си-подобных языках. Предполагаем, что ее тип должен быть IO(). Вот классический пример:

main = print "Hello, world!"

Рассмотрим более сложный случай, когда нам необходимо получить данные из консоли:

main = do c <- getChar
          print (c == 'y')
(здесь мы ожидаем, что пользователь введет «y» или что-либо другое – соответственно программа выведет True или False).

Во втором примере мы видим, что некоторым аналогом присваивания выступает конструкция c<-getChar.

Урок 6.2 Взаимодействие с STDIN-STDOUT

Список базовых функций ввода-вывода может быть найден тут: Basic Input and output или на русском языке тут: 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 сам этого делать не будет.

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

import 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 Образец самостоятельного проекта

На уроке Замыкания... мы разрабатывали функцию для решения квадратного уравнения. Оформим ее в виде самостоятельного модуля:

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 a: "    
	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 будет скомпилирован и слинкован автоматически.

Урок 6.4 Изменяемые переменные

Чтобы научиться работать с изменяемыми переменными, нам необходимо изучить тему работы с монадами и монадными трансформерами. Это — отдельная и трудная для беглого понимания тема. Вот небольшой пример, а тему оставим пока что «на потом».

import Control.Monad.State
 
data Vars = Vars {
   var1 :: Int,
   var2 :: Float
}
 
type MyState a = StateT Vars IO a
type Selector a = (MyState a, a -> MyState ())
 
s1 :: Selector Int
s1 = (gets var1, \x -> modify (\vs -> vs {var1 = x}))
 
s2 :: Selector Float
s2 = (gets var2, \x -> modify (\vs -> vs {var2 = x}))
 
sel :: Selector a -> MyState a
sel = fst
 
mods :: Selector a -> (a -> a) -> MyState ()
mods (gf,uf) mfun = do st <- gf
                       uf (mfun st)
 
sample :: MyState ()
sample = do a <- sel s1
            mods s2 (\x -> x * (fromIntegral a))
            b <- sel s2
            liftIO $ print b
 
main = runStateT sample (Vars 2 1.3)

Урок 6.5 Работа с файлами

(в процессе…)

Урок 6.6 Запуск и компиляция

Запуск подготовленных указанным выше способом возможен разными путями. Во-первых, мы можем по-прежнему из ghci загружать нужный файл и указывать на выполнение функцию main.

Во-вторых возможен запуск на прямое исполнение командой runghc myfile.hs (если будет запуск как скрипта, то всегда можно в первой строке указать

#!/usr/bin/haskell
.

В-третьих, компиляция в исполняемый двоичный код: ghc --make myfile.hs.

Урок 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
(Напомним, здесь Maybe – это конструктор типов, в данном случае полиморфный, параметризованный произвольным типом a, Nothing и Just – конструкторы данных)

Можно задать значение данных, применив конструктор данных Just к значению:

mynumber = Just 5

Полиморфные типы похожи на контейнеры, которые могут содержать значения многих различных типов. Так, Maybe Int можно считать контейнером типа Maybe, который содержит Int или Nothing.

Теперь, предположим, что необходимо написать программу для обслуживания экспериментов по клонированию и скрещиванию овец. Нам потребуются функции mother и father. Но если овцы клонированы, у них не всегда могут быть и отец, и мать!

Опишем возможность отсутствия матери или отца с помощью конструктора типов Maybe:

type Sheep = ...
 
father :: Sheep -> Maybe Sheep
father = ...
 
mother :: Sheep -> Maybe Sheep
mother = ...

Вынесем конкретную реализацию этого типа и функций в отдельный модуль: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, вполне можно обходиться и без монад. Но монады делаются код яснее, лаконичнее и увеличивают контроль над последовательностью при комбинировании функции, чего императивные языки не делают совсем (об этом подробнее будет в других главах).

Урок 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.2 Монада List

Монада List — это новая точка зрения на применение списков. В данном случае, монада List вводит поддержку функций с неоднозначным результатом, а главное — стратегию их связывания. Будем считать, что монадическая функция дает неоднозначный результат, если она возвращает список, а ее тип будет выглядеть примерно так:

f :: a -> [b]

Урок 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<m) && (m<100)

Для фильтрования нужен фильтр:

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 Комбинированная задача

Сформулируем задачу: предположим, необходимо проводить цепочку вычислений функции 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 Трансформеры монад

Подготовим вторую версию функции для задачи выше. Предыдущее решение было «лобовым», и хотя в аналогичной решении при императивном программировании нет ничего необычного в большом количестве вложенных проверок 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)

Мы видим, что код и правда получился кратким и изящным. Цена вопроса — это существенные мозговые усилия по вдумчивому освоению идей монад, трансформеров монад и API (различных функций-утилит), связанных с этим.

Прокомментируем этот пример подробнее…

Далее, рассмотрим ещё одно «вложение», ещё один трансформер, который увеличит функциональность примера путём работы с системой ввода-вывода.

Урок 7.4 Пример простого парсера

Начнем проектирование парсера! :-) Запуск парсера удобно делать в 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 — множество нетерминальных (служебных) символов, причем VTVN = ∅ (т.е. пересечение данных множеств пусто), P — конечное множество правил (продукций), каждое из которых имеет вид A → a, где AVN, a ∈ (VTVN)*, SVN — стартовый символ. Тогда мы говорим, что задана грамматика G = <VT, VN, P, S>.

Определение 2. Пусть (A → β) ∈ P — правило, γ, δ — любые цепочки символов (слова) из множества (VTVN)*. Тогда говорят, что «из γAδ непосредственно выводится γβδ в грамматике G (при помощи данного правила)» и обозначают: γAδ ⇒ γβδ(G).

Определение 3. Пусть α1, α2, …, αm — цепочки из множества (VTVN)* и α1⇒α2, …, αm-1⇒αm. Тогда мы пишем: α1 ⇒* αm и говорим, что «из α1 выводится αm в грамматике G».

Определение 4. Язык, порождаемый грамматикой G, определим как

L(G) = { w | wVT*, 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.

Урок 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.

Ниже применяем полученные функции для создания парсера parser.

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

Скачать готовый файл, содержащий весь приведённый выше код.

Урок 8.2 Парсеры по Нотону

Определим тип парсеров в соответствии с рекомендацией Грэхама Нотона в статье… Монадические комбинаторы парсеров

newtype Parser a = Parser (String -> [(a,String)])

Таким образом, парсер будет функцией, которая принимает строку в качестве аргумента и возвращает некоторый список результатов. Пустой список результатов будет обозначать неудачный разбор. В случае успеха, каждый результат в списке будет представлять пару, чей первый компонент будет значение некоторого типа (обычно — некоторое дерево синтаксического разбора, или иное значение, например, арифметического выражения). Второй компонент будет неразобранным остатком входной строки. Список аргументов в качестве результата позволит нам конструировать парсеры для неоднозначных грамматик, со списком вариантов разбора, если строка может быть разобрана различными путями.

Функция, убирающая тэг у значения типа Parser

parse (Parser p) = p

будет нам полезной для запуска наших парсеров в будущем, например:

> parse myparser "helloworld!"
> [((),"")]

haskell.txt · Последние изменения: 02/12/2016 00:07 — vlasov
CC Attribution-Noncommercial 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0