Seminar07.hs

{-# LANGUAGE InstanceSigs #-}
{-# OPTIONS_GHC -Wno-missing-fields #-}

module Seminar07 where

import qualified Prelude

-- Сегодня мы усложнили себе жизнь для лучшего знакомства со стандартной
-- библиотекой.

-- Все содержимое модуля Prelude можно найти здесь:
-- https://gitlab.haskell.org/ghc/ghc/-/blob/ghc-8.8.3-release/libraries/base/Prelude.hs

--------------------------------------------------------------------------------
-- ЧИСЛОВЫЕ ТИПЫ

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

-- Int - целые числа из диапазона -9223372036854775808..9223372036854775807.
type Int = Prelude.Int
-- Eq, Ord, Enum, Bounded
-- Num, Real, Integral
-- Read, Show

-- Integer - целые числа с длинной арифметикой.
type Integer = Prelude.Integer
-- Eq, Ord, Enum
-- Num, Real, Integral
-- Read, Show

-- Float - числа с плавающей точкой, одинарная точность.
type Float = Prelude.Float
-- Eq, Ord, Enum
-- Num, Real, Fractional, Floating, RealFrac, RealFloat
-- Read, Show

-- Double - числа с плавающей точкой, двойная точность.
type Double = Prelude.Double
-- Eq, Ord, Enum
-- Num, Real, Fractional, Floating, RealFrac, RealFloat
-- Read, Show

-- Каждый из указанных классов типов позволяет совершать различные операции
-- над типом. Ниже перечислены основные функции:

-- Eq         - (==) (/=)
-- Ord        - compare (<) (<=) (>) (<=) min max
-- Enum       - succ pred toEnum fromEnum
-- Bounded    - minBound maxBound
-- Num        - (+) (-) (*) negate abs signum fromInteger
-- Integral   - div mod toInteger
-- Fractional - (/)
-- Floating   - pi exp log sqrt (**) logBase
-- RealFrac   - truncate round ceiling floor
-- Show       - show

-- Классы Real и RealFloat сами по себе не содержат полезных нам функций.

-- Подробнее каждый из классов типов мы изучим ниже.

--------------------------------------------------------------------------------
-- ЛОГИЧЕСКИЙ ТИП

type Bool = Prelude.Bool
-- Eq, Ord, Enum, Bounded
-- Read, Show

-- Для начала создадим константы, населяющие наш тип:
false :: Bool
false = Prelude.False

true :: Bool
true  = Prelude.True

-- А также вспомним об otherwise, нужном для паттерн-матчинга.
otherwise :: Bool -- Prelude.otherwise
otherwise = true

-- Реализуем с их помощью функцию not из Prelude.
not :: Bool -> Bool -- Prelude.not
not cond | cond      = false
         | otherwise = true
-- Здесь нельзя написать not true, так как true - это не литерал, и тогда
-- true будет интерпретироваться как новое имя, которое перекрывает объявленное
-- выше. И разумеется, с ним может быть сопоставлено и False, так что реализация
-- получилась бы неверной.

-- Объявим теперь оператор (&&):
(&&) :: Bool -> Bool -> Bool -- (Prelude.&&)
cond1 && cond2 | cond1     = cond2
               | otherwise = false
infixr 3 &&
-- Замечание: из-за ленивой семнатики оператор cond2 не вычисляется, если
-- первый аргумент - False, то есть оператор работает по принципу short circuit.

-- Для коллекции объявим также оператор (||):
(||) :: Bool -> Bool -> Bool -- (Prelude.||)
cond1 || cond2 = not cond1 && not cond2
infixr 2 ||
-- Тоже short-circuit.

--------------------------------------------------------------------------------
-- СИМВОЛЬНЫЙ И СТРОКОВЫЙ ТИП

type Char = Prelude.Char
-- Eq, Ord, Enum, Bounded
-- Read, Show

type String = Prelude.String -- При этом сам Prelude.String - алиас на [Char].
-- Eq, Ord
-- Read, Show

--------------------------------------------------------------------------------
-- ТИП ORDERING

-- Тип Ordering содержит 3 значения: LT, EQ, GT.
type Ordering = Prelude.Ordering
-- Eq, Ord, Enum, Bounded
-- Read, Show

lt :: Ordering
lt = Prelude.LT

eq :: Ordering
eq = Prelude.EQ

gt :: Ordering
gt = Prelude.GT

-- Эти значения возвзвращаются функцией compare из класса типов Ord для
-- обозначения, как соотносятся между собой аргументы.

--------------------------------------------------------------------------------
-- ПАРАМЕТРИЧЕСКИЙ ПОЛИМОРФИЗМ

-- Функция называется полиморфной, если ее можно применить к значениям разных
-- типов. Существует два вида полиморфизма: параметрический и специальный.

-- Полиморфизм называется параметрическим, если реализация функции не зависит от
-- типа. Специальный полиморфизм характеризуется тем, что в зависимоти от типа
-- применяется та или иная реализация.

-- Приведем простейшую функцию с параметрическим полиморфизмом:
id :: a -> a -- Prelude.id
id x = x

-- В типе функции в id именем a названа переменная типа. Вместо нее может быть
-- подставлен любой тип: числовой, логический, список, даже функциональный.
-- Переменные типов называются с маленькой буквы, а конкретные с большой.
id1 :: b -> b
id1 = id id -- Здесь a во внешней id равна b -> b из внутренней функции.

-- Функция может быть полиморфной по двум разным типам:
const :: a -> b -> a -- Prelude.const
const a _ = a

-- Здесь переменная типа и аргумент имеют одинаковые имена, но поскольку
-- это разные пространства имен, ошибки не происходит.

-- Пример полиморфной константы:
undefined :: a -- Prelude.undefined
undefined = Prelude.undefined
-- Именно благодаря параметрическому полиморфизму контсанты undefined
-- ее можно использоваться вместо любого подвыражения в программе.

-- Аналогично с функцией error:
error :: String -> a -- Prelude.error
error = Prelude.error

--------------------------------------------------------------------------------
-- СПЕЦИАЛЬНЫЙ ПОЛИМОРФИЗМ

-- Пример специального полиморфизма: оператор сложения. Он применим как к целым
-- числам, так и к числам с плавающей точкой.
addInt :: Int -> Int -> Int
addInt = (Prelude.+)

addDouble :: Double -> Double -> Double
addDouble = (Prelude.+)

-- На низком уровне (+) для целых и вещественных чисел реализован по-разному,
-- поэтому (+) - пример функции со специальным полиморфизмом.

-- Замечание по синтаксису: в префиксной нотации для использования оператора из
-- модуля с квалифицированным импортом надо писать имя модуля внутри скобок.
-- Если используется инфиксная форма, то скобки не нужны:
--(Prelude.+) 2 2
--2 Prelude.+ 2

--------------------------------------------------------------------------------
-- ВЫВОД ТИПОВ

-- Если тип функции не указывать, то компилятор выводит наиболее общий тип,
-- опираяся на структуру функции: в зависимости от выражений, которые
-- используются внутри, составлятся система уравнений на типы, которая затем
-- решается с учетом всех ограничений. В Haskell используется система типов
-- Хиндли-Милнера, подробности можно найти в статье:
-- http://www.fprog.ru/2010/issue5/roman-dushkin-hindley-milner

-- Если указывать тип функции, заменяя переменные типов на конкретные типы,
-- то эти условия будут учтены в алгоритме вывода типов. Таким образом можно
-- ограничивать степень полиморфизма функции.

-- Так сделано выше в функциях addInt и addDouble.

--------------------------------------------------------------------------------
-- ФУНКЦИИ ВЫСШИХ ПОРЯДКОВ

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

-- Пример. Заодно рассмотрим, как здесь работает система вывода типов:
apply2 f x = f (f x)
-- Положим x :: a, f :: b. Так как f применяется к x, то b = a -> c.
-- Так как f :: a -> c применяется к (f x) :: c, то c = a. Значит,
-- f :: a -> a, x :: a , тогда  f x :: a, f (f x) :: a, откуда
-- apply2 :: (a -> a) -> a -> a.

-- Еше пример: фнукция, меняющая порядок аргументов функций местами.
flip :: (a -> b -> c) -> b -> a -> c -- Prelude.flip
flip f b a = f a b

const2 :: a -> b -> b
const2 = flip const

-- Оператор применения функции:
($) :: (a -> b) -> a -> b -- (Prelude.$)
f $ b = f b
infixr 0 $

-- Еще пример функции высшего порядка - это map для списка.
map :: (a -> b) -> [a] -> [b] -- Prelude.map
map f []       = []
map f (x : xs) = f x : map f xs

--------------------------------------------------------------------------------
-- ЛЯМБДА-АБСТРАКЦИИ

-- Абстрагирование по аргументу - универсальный подход, позволяющий превратить
-- произвольное выржения языка в функцию. Например, при абстрагировании
-- x * x * x получается функция возведения в куб:
cube :: Int -> Int
cube x = x * x * x where
    (*) = (Prelude.*)
    infixl 7 *
    -- Замчание: при таком объявлении создаем новый оператор, поэтому без явного
    -- указания ассоциативности и приоритета получаем значения умолчанию.

-- Но выше мы получили именованную функцию. Можно получить анонимную функцию,
-- используя лямбда-абстракции:
squaresBelow10 = map (\ x -> x Prelude.* x) [1, 2, 3]
-- Это полезно, когда функции достаточно простые и при этом нет нужной
-- именованной функции. Обратный слеш - это символ λ из лямбда-исчисления.

-- Лямбда-абстракции могут иметь несколько аргументов и даже выполнять
-- сопоставление с образцом.

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

-- Чтобы записывать еще меньше кода, можно использовать оператор композиции:
(.) :: (b -> c) -> (a -> b) -> a -> c -- (Prelude..)
(f . g) x = f (g x)
infixr 9 .
-- Ассоцитиновсть композиции не важна, поэтому для конкретики выбрали правую
-- (операторы совсем без ассоциативности нельзя записывать подряд без скобок).

-- Оператор композиции, а точнее, его сечения, можно использовать, чтобы
-- ~обфусцировать код~ писать код в бесточечном стиле, подробности можно найти в
-- статье: http://fprog.ru/2010/issue4/denis-moskvin-compositions-sections

-- Например, бывают ситуации, когда требуется записать композицию функции двух
-- аргументов и функции одного аргумента, то есть составить выражение вида
-- f (g x y). Обычно мы бы записали это в виде лямбда-абстракции:
-- \ x y -> f (g x y), но если мы знаем возможности сечений композиций, то это
-- упрощается до (\ x y -> ((f .) . g) x y), то есть, сокращая x и y с обеих
-- сторон, просто (f .) . g. В статье есть и более продвинутые примеры, но даже
-- этот достаточно сильно осложняет чтение кода для непрофессионалов.

--------------------------------------------------------------------------------
-- ПОЛИМОРФИЗМ КОРТЕЖЕЙ

-- Рассмотрим функцию создания тройки:
makeTriple1 :: a -> b -> c -> (a, b, c)
makeTriple1 a b c = (a, b, c)

-- Оказывается, есть функция, которая конструирует кортеж из трех элементов
-- и имеет три аргумента, как и функция makeTriple. Это функция (,,).
makeTriple2 :: a -> b -> c -> (a, b, c)
makeTriple2 a b c = (,,) a b c
-- Более того, сам тип можно записать в таком же префиксном стиле:
makeTriple3 :: a -> b -> c -> (,,) a b c
makeTriple3 = (,,)

-- Таким образом, конструкторы кортежей (для всех размерностей больше 0) -
-- полиморфные функции.

-- То же самое и с доступами к первому и второму элементам пары:
fst :: (a, b) -> a -- Prelude.fst
fst (a, _) = a

snd :: (a, b) -> b -- Prelude.snd
snd (_, b) = b

-- Наконец, в модуле Prelude для пар есть еще две полиморфные функции.
curry :: ((a, b) -> c) -> a -> b -> c -- Prelude.curry
curry f a b = f (a, b)

uncurry :: (a -> b -> c) -> (a, b) -> c -- Prelude.uncurry
uncurry f (a, b) = f a b

--------------------------------------------------------------------------------
-- ПОЛИМОРФИЗМ СПИСКОВ

-- Пример: тип [] - это [a], то есть список из элементов произвольного (хотя и
-- одинакового) типа.
emptyList = [] :: [a]

-- Также функции для работы со списками полиморфны:
(++) :: [a] -> [a] -> [a] -- (Prelude.++)
(x : xs) ++ ys = x : xs ++ ys
_        ++ ys = ys
infixr 5 ++

prepend :: a -> [a] -> [a]
prepend = (:)

-- Замечание для наблюдательных: типы, которые записаны в символьном виде
-- (например, список и кортежи), а также их конструкторы (например, (:)), можно
-- использовать просто так, без Prelude.

-- Кстати, для списков также существуте префиксная форма записи: [] a, но она
-- применима только к обозначению типов.

--------------------------------------------------------------------------------
-- КЛАССЫ ТИПОВ

-- Для реализации специального полиморфизма в Haskell используются классы типов.
-- Класс типов задает интерфейс, который могут реализовывать конкретные типы.

-- Сам по себе класс типов - это семейство типов, для которых определен
-- заданный набор функций. Для них возможны, но необязательные, реализации по
-- умолчанию, в том числе взаимно-рекурсивные. Главное: следить, чтобы не было
-- ошибок типизации.
class Eq a where -- Prelude.Eq
    (==), (/=) :: a -> a -> Bool

    x == y = not (x /= y)
    x /= y = not (x == y)

-- Объявленные функции имеют глобальную область видимости, поэтому недопустимо
-- объявлять другие классы типов с теми же функциями.

--------------------------------------------------------------------------------
-- ЭКЗМЕПЛЯРЫ КЛАССОВ ТИПОВ

-- Конкретный тип называется экземпляром класса типов, если для него реализованы
-- все функции, объявленные для данного класса типов.

-- Рассмотрим объявление экземпляра на примере типа Bool:
instance Eq Prelude.Bool where
    (==) :: Bool -> Bool -> Bool -- Используем расширение InstanceSigs.
    cond1 == cond2 = cond1 && cond2 || not cond1 && not cond2

-- Мы написали Prelude.Bool вместо Bool, потому что нельзя объявлять
-- экземплярами классов типов алиасы на существующие типы. Если бы это было
-- возможно, то тогда были бы возможны ситуации, когда тип и алиас на него
-- становились экземплярами одного класса типов, но функции имели разные
-- реализации. На самом деле это полезная возможность, и есть решение, которое
-- мы рассмотрим ниже.

-- При объявлении типа экземпляром класса типов по умолчанию нельзя указывать
-- тип функции, которую мы реализуем. Однако это тоже достаточно полезная
-- возможность, поэтому существует расширение языка от компилятора GHC, которое
-- позволяет писать сигнатуры: InstanceSign. Его достаточно написать в начале
-- файла в комментарии: {-# LANGUAGE InstanceSigs #-}.

-- Со списком всех расширений можно ознакомится здесь:
-- https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/glasgow_exts.html

-- Наконец, в данном объявлении стоит обратить внимание, что мы не реализуем
-- функцию (/=), а значит, для нее применяется реализация по умолчанию.
-- Поскольку она выполнена через (==), то объявление одного только (==)
-- достаточно для завершения объявления экземпляра.

-- Вообще говоря, в данном случае мы могли бы и не реализовывать даже (==),
-- поскольку для него так же есть реализация по умолчанию. Однако тогда
-- использование как (==), так и (/=) приводило бы к переполненю стека,
-- поскольку они реализованы рекурсивно через друг друга.

-- Для корректного объявления экземпляра класса типов достаточно реализовать
-- только одну из двух функций. Этот набор функций отмечается в документации.
-- Например, при запросе :info Prelude.Eq в выводе интерпретатора есть
-- комментарий "{-# MINIMAL (==) | (/=) #-}".

-- Почти все известные типы данных являются экземплярами класса типов Eq.
-- Пример типа, не являющегося его экземпляром: тип фунцкий.

-- Определим также инстантс для Ordering, он понадобится в дальнейшем.
instance Eq Prelude.Ordering where
    (==) :: Ordering -> Ordering -> Bool
    Prelude.LT == Prelude.LT = true
    Prelude.EQ == Prelude.EQ = true
    Prelude.GT == Prelude.GT = true
    _          == _          = false

--------------------------------------------------------------------------------
-- КОНТЕКСТЫ

-- Если в реализации полиморфной функции используется функция из класса типов,
-- то тогда в ее типе требуется указать контекст, то есть ограничения на
-- переременные типов вида "данный тип должен являться экземпляром класса
-- такого-то класса типов". Например, функция сравнения элементов пары:
compPair :: (Eq a, Eq b) => (a, b) -> (a, b) -> Bool
compPair (a, b) (c, d) = a == c && b == d

-- Если тип функции не указывается, то контексты будут выведены автоматически.

--------------------------------------------------------------------------------
-- ПОЛИМОРФНЫЕ ЭКЗЕМПЛЯРЫ

-- Экземплярами классов типов можно делать также и полиморфные типы. Например,
-- очевидно, что если уметь сравнивать тип каждого элемента пары, то можно
-- сравнивать и пары. Условие "если уметь сравнивать" здесь будет также записано
-- через контекст, но уже не для типа функции, а для типа экземпляра:
instance (Eq a, Eq b) => Eq (a, b) where
    (==) :: (a, b) -> (a, b) -> Bool
    (==) = compPair

--------------------------------------------------------------------------------
-- РАСШИРЕНИЯ КЛАССОВ ТИПОВ

-- Контектсы могут появляться и в объявлении самого класса типов, в таком случае
-- новый класс расширяет старый:
class Eq a => Ord a where -- Prelude.Ord
    compare :: a -> a -> Ordering
    (<), (<=), (>=), (>) :: a -> a -> Bool
    max, min :: a -> a -> a

    compare x y | x == y = eq
                | x <= y = lt
                | otherwise = gt

    x <= y = compare x y /= gt
    x < y  = compare x y == lt
    x >= y = compare x y /= lt
    x > y  = compare x y == gt

    max x y | x <= y    = y
            | otherwise = x

    min x y | x <= y    = x
            | otherwise = y

-- Почти известные типы являются экземплярами класса типов Ord. Не является,
-- например, тот же функциональный тип.

--------------------------------------------------------------------------------
-- КЛАСС ТИПОВ ENUM

-- Теперь, когда мы познакомились с тем, что такое классы типов, как создавать
-- их представителей и как расширять классы типов, познакомимся со стандартными
-- базовыми классами типов из модуля Prelude.

-- Enum содержит значения, которые можно перечислять, то есть получить по
-- элементу следующий или предыдущий.
class  Enum a where -- Prelude.Enum
    succ, pred :: a -> a
    toEnum     :: Int -> a
    fromEnum   :: a -> Int
    -- Что-то еще...

    succ = toEnum . (Prelude.+ 1)  . fromEnum
    pred = toEnum . (Prelude.subtract 1) . fromEnum
    -- Что-то еще...

-- Если тип ограничен, то в случае взятия предыдущего от минимального элемента,
-- или следующего за максимальным, или fromEnum при выходе за диапазон, получим
-- ошибку bad argument.

-- Пример реализации.
instance Enum Prelude.Bool where
    toEnum 0 = false
    toEnum 1 = true
    toEnum _ = error "bad argument"

    fromEnum cond = if cond then 1 else 0

-- Среди стандартных типов экземлярами являются следующие:
-- Bool, Ordering, Char, Int, Integer, Float, Double и внезапно ().

--------------------------------------------------------------------------------
-- КЛАСС ТИПОВ BOUNDED

-- В класс Bounded входят типы, для которых известна верхняя и нижняя граница
-- значений. Он содержит всего две константы - эти границы.

class Bounded a where -- Prelude.Bounded
    minBound, maxBound :: a

instance Bounded Prelude.Ordering where
    minBound = lt
    maxBound = gt

-- Примеры типов из стандартной библиотеке:
-- Bool, Ordering, Char, Int, () и непустые кортежи Bounded-типов.

-- Что логично, типы Integer, Float и Double не являются Bounded.

--------------------------------------------------------------------------------
-- КЛАСС ТИПОВ SHOW

-- Класс типов Show содержит типы, значения которых могут быть преобразованы в
-- строку:
class Show a where -- Prelude.Show
    show :: a -> String
    -- Что-то еще...

instance Show Prelude.Bool where
    show :: Bool -> String
    show cond = if cond then "True" else "False"

-- Почти все типы являются экземплярами класса типов Show:
-- Bool, Ordering, Char, Int, Integer, Float, Double, списки Show-типов,
-- пустой кортеж и непустые кортежи Show-типов.

--------------------------------------------------------------------------------
-- КЛАСС ТИПОВ READ

-- Класс типов Read сожержит типы, значения которых могут быть считаны из
-- строки:
class Read a where -- Prelude.Read
    -- Не будем разбирать функции, определенные в классе типов.

-- Рассмотрим вспомогательную функцию, определенную не в классе Read, но
-- требующая такого контекста: read. Она берет строку и возвращает значение.
-- При этом для выражения нужно ограничить степень полиморфизма, иначе будет
-- неясен итоговый тип значения, которое мы считываем.
read :: Read a => String -> a -- Prelude.read
read = undefined

-- Функция reads позволяется читать не из всей строки, а из ее префикса. Если
-- считать не удалось, то список пустой, если разбор однозначен, то один элемент
-- и остаток строки, а если неоднозначен, то несколько аналогичных структур.
-- Здесь также значение функции полиморфно, поэтому трубется ограчение
-- полиморфизма.
reads :: Read a => String -> [(a, String)] -- Prelude.reads
reads = undefined

-- Экземплярами класса типов Read являются стандартные типы:
-- Bool, Ordering, Char, Int, Integer, Float, Double, список Read-типов,
-- пустой кортеж и непустые кортежи Read-типов.

--------------------------------------------------------------------------------
-- ЧИСЛОВЫЕ КЛАССЫ ТИПОВ

-- Класс типов Num - базовый тип для всех операций, выполняемых над числами.
class Num a where -- Prelude.Num
    (+), (-), (*) :: a -> a -> a
    negate        :: a -> a
    abs           :: a -> a
    signum        :: a -> a
    fromInteger   :: Integer -> a

    x - y         = x + negate y
    negate x      = fromInteger 0 - x -- Здесь без fromInteger не комплируется.

-- Для класса типов Num существует закон. Закон - это уравение, которое должно
-- быть выполнено для произвольных значений экземпляра класса типов. Законы
-- проверяются только программистом, который должен доказывать, что законы
-- выполняются. Компилятор никаких ошибок в случае нарушений не выдает.
-- В стандарте языка к слову law не дается совершенно никаких пояснений
-- (проверено Ctrl+F'ом).

-- Закон для класса типов Num:
-- abs x * signum x == x

-- Класс типов Num не содержит в себе операцию деления, поскольку она
-- реализована по-разному для целых чисел и вещественных, но имеет два основных
-- наследника: Integral и Fractional соответственно:
class (Real a, Enum a) => Integral a where -- Prelude.Integral
    div, mod  :: a -> a -> a
    divMod    :: a -> a -> (a,a)
    toInteger :: a -> Integer
    -- Что-то еще...

    divMod x y = (x `div` y, x `mod` y)
    -- Что-то еще...

-- Для класса типов Integral есть закон:
-- (x `div` y) * y + (x `mod` y) == x
-- Есть также второй закон, связывающий функции, которые мы здесь опустили,
-- поэтому его рассматривать не будем.

-- Обратите внимание, что класс Integral расширяет Num не напрямую, а через
-- посредника, специальный тип Real, а также что он расширяет еще и Enum.
class (Num a, Ord a) => Real a where -- Prelude.Real
    -- Что-то еще...
-- Таким образом, интегральные числа можно также еще и сравнивать друг с другом.

-- Для вещественных чисел есть класс типов Fractional, содержащий привычное
-- деление.
class Num a => Fractional a where -- Prelude.Fractional
    (/)          :: a -> a -> a
    -- Что-то еще...

-- Этот класс расширяет класс типов Floating, которые содержит всю стандартные
-- математические функции и константу pi.
class Fractional a => Floating a where -- Prelude.Floating
    pi                  :: a
    exp, log, sqrt      :: a -> a
    (**), logBase       :: a -> a -> a
    -- Что-то еще...

-- Наконец, классы типов Fractional и Real (бесполезный) расширяет класс типов
-- RealFrac, содержащий функции для округления чисел с плавающей точкой:
class (Real a, Fractional a) => RealFrac a where -- Prelude.RealFrac
    truncate, round :: Integral b => a -> b
    ceiling, floor  :: Integral b => a -> b
    -- Что-то еще...
-- Как видно, округление возможно только до целочисленных типов, так как есть
-- Контекст Integral b, ограничивающий полиморфизм возвращаемого значения.

-- Напоследок, есть класс типов RealFloat, который содержит функции для
-- получения внутренней информации об устройстве числе с плавающей точкой,
-- поэтому он нам не нужен.
class (RealFrac a, Floating a) => RealFloat a where
    -- Что-то еще...

-- Есть также свободные функции, не принадлежащие ни одному из классов типов,
-- но полезные при работе с числами. Вот лишь некоторые из них:
--even, odd    :: Integral a          => a -> Bool
--gcd, lcm     :: (Integral a)        => a -> a-> a
--(^)          :: (Num a, Integral b) => a -> b -> a
--fromIntegral :: (Integral a, Num b) => a -> b

-- Теперь, чтобы собрать все в кучу, пройдемся по известным целочисленным типам
-- и отнесем их к разным классам типов:
-- Int, Integer  - Num, Integral
-- Float, Double - Num, Fractional, Floating, RealFrac

-- Интересующиеся могут почитать стандарт языка, модуль Prelude или Hoogle,
-- чтобы узнать о функциях и типах, о которых мы говорить не стали.

--------------------------------------------------------------------------------
-- АЛГЕБРАИЧЕСКИЕ ТИПЫ ДАННЫХ

-- Для объявления алгебраического типа данных в Haskell используется ключевое
-- слово, за которым следует имя (конструктор типа), а затем через знак `=`
-- перечисляются все значения (конструкторы данных), разделенные знаком `|`.
data Direction = Forward | Backward

-- Имена значений и типов в разных пространствах имен, поэтому могут совпадать;
-- так обычно поступают для типов с одним конструктором данных.
data Unit = Unit

-- Имена конструкторов типов и данных должны начинаться с большой буквы, иначе
-- будет ошибка компиляции.

-- Рассмотренные типы данных называют перечислениями. Конструкторы данных могут
-- иметь аргументы, в этом их называют произведениями.
data Point3 = Point3 Double Double Double

-- Аргументов может быть любое число, в том числе 1 или 0, как мы видели в
-- перечислениях.

-- Типом-аргументом может выступать даже сам исходный тип, в этом случае
-- тип называют рекурсивным.
data Loop = Loop Loop

-- Можно комбинировать перечисления с произведениями:
data IntTree = IntLeaf
             | IntNode Int
             | IntBranch IntTree IntTree

--------------------------------------------------------------------------------
-- DERIVED INSTANCES

-- Если мы попробуем вывести значения типа TypeConstructor1 на экран в
-- интерпретаторе, то возникнет сообщение об ошибке, что данноый тип не является
-- экземпляром класса типов Show, то есть его значения нельзя преобразовать в
-- строку.

-- Для решения этой проблемы есть так называемая автоматическая реализация
-- производных представителей:
data Movement = Up | Down
    deriving (Prelude.Eq, Prelude.Ord, Prelude.Enum, Prelude.Bounded,
              Prelude.Show, Prelude.Read)

-- Это возможно не для произвольных классов типов, а только для шести классов,
-- перечисленных выше. Но можно, конечно, определить все экземпляры вручную.

-- Нельзя создавтаь Enum для типа, если среди его конструктора есть
-- произведение.

--------------------------------------------------------------------------------
-- РАБОТА С ТИПАМИ ДАННЫХ

-- Каждый конструктор данных представляет собой функции с числом аргументом
-- (от 0), равным числу аргументов-типов при объявлении. Отличие в том, что
-- имена этих функций начинаются с заглавной буквы. Типы выводятся автоматически
forward = Forward :: Direction
center2 = Point3 0.0 0.0 0.0 :: Point3
nodeOf3 = IntNode 3 :: IntTree

-- Для работы с АТД используется сопоставление с образцом: каждый конструктор
-- является образцом, с которым возможно успешное сопоставление. Если это
-- конструктор произведения, то шаблон приобретает аргументы, как и конструктор
-- данных.
toString :: IntTree -> String
toString IntLeaf         = "Leaf"
toString (IntNode v)     = "Node " ++ Prelude.show v
toString (IntBranch l r) = "Branch(" ++ toString l ++ ", " ++ toString r ++ ")"

--------------------------------------------------------------------------------
-- ТИПЫ ДАННЫХ С МЕТКАМИ ПОЛЕЙ

-- Для алгебраических типов данных существует синтаксис записей.
data Person = Person { age :: Int, occupation :: String, city :: String }
    deriving (Prelude.Show, Prelude.Eq)

-- Объявление в таком виде дает много дополнительных возможностей.

-- Во-первых, теперь у нас определены две функции name :: Person -> String и
-- age :: Person -> Int - проекции произведения на его координаты.
occup = occupation $ Person 18 "garbage collector" "Berlin" :: String

-- Во-вторых, мы получили возможнсоть конструировать данные, меняя порядок
-- полей:
manager = Person { occupation = "manager", age = 30, city = "London" } :: Person
-- Если используется метки полей, то обязательные фигурные скобки, при этом
-- нужно перечислить все поля.

-- В-третьих, можно не указывать часть полей (в том числе все). Компилятор,
-- конечно, выдает предупреждение, но код компилируется:
unemployed = Person { age = 16, city = "Moscow" } :: Person
anon = Person {} :: Person
-- В этом случае все действия с полями, значения которых не указаны, будут
-- бросать ошибку. В том числе теперь не работает сравнение на равенство и
-- вывод на экран. Но с теми полями, которые определены, все хорошо:
moscow = city unemployed :: String

-- В-четвертых, теперь можно копировать следующим образом:
developer = manager { occupation = "developer" } :: Person
-- Получили Person, у которого все поля, кроме occupation, совпадают с manager,
-- а occupation = "developer". Можно таким образом определять поля, которые
-- остались не инициализированы:
sixYearOld = anon { age = 6 } :: Person

-- В пятых, синтаксис записей делает гибче сопоставление с образцом. В нем можно
-- так же сопоставлять не все поля и свободно менять порядок:
tgStyle :: Person -> String
tgStyle (Person { city = c, occupation = o, age = a }) =
    Prelude.show a ++ " y.o. " ++ o ++ " from " ++ c

showAge :: Person -> String
showAge (Person { age = a }) = Prelude.show a
-- Это работает даже с записями, где не все поля инициализированы:
sixStr = showAge sixYearOld

-- Синтаксис записей возможен также и для типов-перечислений, а также для
-- произведений, где нет аргументов (последнее не очень полезно):
data StringTree = StringLeaf {}
                | StringNode { value :: String }
                | StringBranch { left :: StringTree, right :: StringTree }
-- В этом случае применение функций-проекций к объектам, сконструированным через
-- неправильный тип, будет выдавать ошибку. Коллизии имен меток допустимы только
-- в случае, если поля имеют одинаковый тип.

--------------------------------------------------------------------------------
-- ОБЕРТКИ НАД ТИПАМИ

-- Ключевое слово type, рассмотренное в самом начале, создает алиас, или
-- синоним, уже существующего типа, и может использовать в качестве полной
-- замены старого типа.

-- Единственное ограничение, с которым мы встречались, это объявление экземпляра
-- класса типов, где запрещалось использование алиасов.

-- Это в некотором смысле логично, потому что если объявить экземрляра класса
-- типов для алиасов, то тогда код можно было бы интерпретировать как объявление
-- второго экземпляра для одного и того же типа.

-- Это вызывает сложности при применении функций из класса типов, потому что
-- раз типы полностью эквивалентны, непонятную, какую версию использовать.
-- Классы типов служат для специального полиморфизма, то есть реализации
-- действительно могут быть различны.

-- Конечно, встает вопрос, почему бы не разрешить создание классов типов для
-- алиасов, но и в этом объявлении трактовать алиас как полноценный синоним,
-- что приводило бы к ошибке, поскольку была бы попытка повторного объявления
-- алиаса. Предположение в том, что запретом на алиасы разработчики языка
-- запрещают нам интерпретировать код неправильно.

-- Но бывает, что все-таки потребность для одного типа сделать два разных
-- экземпляра одного и того же класса типов. В этом случае на помощь
-- приходят обертки над типами, которые объявляются с ключевым словом newtype:
newtype CharList = CharList String deriving Prelude.Show

-- Как и следует ожидать, newtype создает новый тип, формально не связанный с
-- оборачиваемым. Теряются все экземпляры классов типов, и его нельзя
-- использовать как замену внутреннего типа.

-- Для newtype есть все те же возможности, что и для data-типов, а именно:
-- derived instances, сопоставлеие с образцом, синтаксис с метками полей.

-- В чем отличия newtype и data: обертка имеет строго один конструктор с ровно
-- одним параметром. Раз так, то сам конструктор во время исполнения программы
-- не нужен, и в рантайме объявление заменяется на обернутый тип. Таким образом,
-- получается более эффективное решение.

-- Более того, это позволяет менее строго проводить сопоставление с образцом:
data Data = Data Int
newtype NewType = NewType Int

ignoreData :: Data -> ()
ignoreData (Data _) = ()

ignoreNewType :: NewType -> ()
ignoreNewType (NewType _) = ()

emptyTuple     = ignoreNewType undefined
errorUndefined = ignoreData undefined

-- Поскольку конструктор типов один, то его можно игнорировать при сопоставлении
-- с образцом, поэтому фактически здесь (NewType _) - неопровержимый образец.

-- В случае с data нет гарантии, что конструктор типов единственный, поэтому
-- необходимо вычислить выражение undefined и посмореть, какой конструктор
-- используется. Неудивительно, что эта процедура завершается ошибкой.

--------------------------------------------------------------------------------
-- ТИПЫ С ПАРАМЕТРАМИ

-- Типы данных можно параметризовать другим типом, в этом случае после имени
-- типа пишется одна или более переменных типов. Далее переменную типа можно
-- использовать в качестве обычного типа в каждом из конструкторов данных.
data Tree a = Leaf | Node (Tree a) a (Tree a)
newtype Identity a = Identity { runIdentity :: a }

-- Мы уже знаем стандартные параметризованные типы: кортежи, списки и функции.
-- Каждый из этих типов можно записать в префиксном виде, чтобы показать
-- общность конструкции:
str = "string" :: [] Char
tup = (1, 2) :: (,) Int Int
fun = (\ str -> "'" ++ "'" ) :: (->) String String

--------------------------------------------------------------------------------
-- ТИП ДАННЫХ MAYBE

-- Кроме перечисленных выше, есть и другие стандартные параметрические типы
-- данных из модуля Prelude. Самый простой из них - это Maybe.

data Maybe a = Nothing | Just a deriving Prelude.Show -- Prelude.Maybe
-- Его смысл в том, что значение этого типа - такой объект, который содержит
-- значение указзного типа-параметра, либо не содержит ничего.

-- Тип Maybe используют в ситуациях, когда по смыслу значение может
-- отсутстовать. Например, поиск в списке.

-- Конструктор данных Nothing :: Maybe a - полиморфная константа.

-- Для типа Maybe существует полезная вспомогательная функция maybe:
maybe :: b -> (a -> b) -> Maybe a -> b -- Prelude.maybe
maybe b _ Nothing  = b
maybe _ f (Just a) = f a

--------------------------------------------------------------------------------
-- ТИП ДАННЫХ EITHER

-- Второй важный тип данных - это Either.
data Either a b = Left a | Right b deriving Prelude.Show -- Prelude.Either
-- Его семантике жестко не фиксируется, но как правило, он примерно следующий:
-- выражение может либо завершиться корректно значением типа b, в этом случае
-- результат оборачивается в Right, либо завершиться ошибкой типа a, в этом
-- случае результат оборачивается в Left.

-- Используется в вычислениях, которые могут завершаться с ошибками, которые мы
-- впоследствии сможем обработать (а не как с error).

-- Для типа Either есть вспомонательная функция either по аналогии с maybe:
either :: (a -> c) -> (b -> c) -> Either a b -> c -- Prelude.either
either f _ (Left a)  = f a
either _ g (Right b) = g b

--------------------------------------------------------------------------------
-- ИНФИКСНЫЕ КОНСТРУКТОРЫ ДАННЫХ

-- Конструкторы данных могут не только в префиксном, но и в инфиксном стиле.
-- В этом случае создается оператор, первым символом котрого обязательно
-- является двоеточие `:` (например, для списка конструктор (:) - инфиксиный).
data List a = Nil | a :+ List a deriving Prelude.Show
infixr 5 :+

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

evenUpTo6 = 2 :+ 4 :+ 6 :+ Nil :: List Int

--------------------------------------------------------------------------------
-- КАЙНДЫ

-- С введением типов с параметрами сильно усложнилось пространство типов, так
-- как теперь типы можно рассматривать не как постоянные, а как функции с
-- аргументами - типовыми переменными или конкретными типами.

-- Подстановка типов-аргументов в другой тип может быть корректной или нет, и
-- это нужно контролировать. Это сделано с помощью введение системы типов над
-- типами, называемой кайндами (kinds).

-- Кайнд типов * содержит в себе все типы без аргументов. Если у типа есть
-- аргумент, то его кайнд - это * -> *. И так далее.

-- В интеретаторе GHCi можно командой :k (или :kind) узнать кайнд передаваемого
-- типа:
-- Bool :: *
-- []   :: * -> *
-- (->) :: * -> * -> *
-- (,,) :: * -> * -> * -> *

-- Типы допускают каррирование:
-- (->)           :: * -> * -> *
-- (->) Char      :: * -> *
-- (->) Char Char :: *

-- Кайнды допускают также "функциональные" аргументы:
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) } -- :: (* -> *) -> *