itmo_conspects

Лекция 5. Полугруппа, моноид и функтор

Полугруппа и моноид

Полугруппа - это алгебраическая структура (S, R), которая определяет множество значений S и бинарную ассоциативную операцию R (такую, что (x R y) R z = x R (y R z)), результатом которой является элемент множества (то есть операция замкнута над множеством)

Примерами полугрупп являются:

Множество целых чисел и операция нахождения минимума между ними
Множество всех строк и операция конкатенации
Множество натуральных чисел и операция сложения и так далее

В Haskell полугруппа представлена в виде класса типов Semigroup, которая имеет такое определение:

ghci> :i Semigroup
type Semigroup :: * -> Constraint
class Semigroup a where
  (<>) :: a -> a -> a
  sconcat :: NonEmpty a -> a
  stimes :: Integral b => b -> a -> a
  {-# MINIMAL (<>) | sconcat #-}
        -- Defined in `GHC.Internal.Base'
-- представители класса...

Здесь такой операцией R является оператор <>, который достаточно определить в представителе

Для примера сделаем представителя для полугруппы из целых чисел и операции минимума. Сделаем обертку над Int с помощью newtype, чтобы семантически выделить, что операция <> будет работать как минимум для значений

newtype Min = Min Int
  deriving (Eq, Show)

instance Semigroup Min where
  (<>) :: Min -> Min -> Min
  Min x <> Min y
    | x <= y    = Min x
    | otherwise = Min y

ghci> Min 5 <> Min 2 <> Min 53 <> Min 3
Min 2

Аналогично можно реализовать полугруппы из целых чисел и сложения:

newtype Sum = Sum Int
  deriving (Eq, Show)

instance Semigroup Sum where
  (<>) :: Sum -> Sum -> Sum
  Sum x <> Sum y = Sum (x + y)

ghci> Sum 5 <> Sum 2 <> Sum 53 <> Sum 3
Sum 63

Некоторые полугруппы уже определены в стандартной библиотеке, в том числе Min, Max, Sum, Product, And, Xor, Predicate и другие

Для некоторых производных типов представитель Semigroup определен, например:

Для двух кортежей (a, b), типы a и b которого имеют свои операторы <>, оператор <> производит операции <> с каждым элементом в отдельности, выдавая новый кортеж:
```
ghci> (Sum 1, Min 4) <> (Sum 2, Min 1)
(Sum 3,Min 1)
```
Аналогично для (a, b, c), (a, b, c, d) и (a, b, c, d, e)
Для списков [a] оператор <> производит конкатенацию

Для типа Ordering оператор <> возвращает первое значение, которое не является EQ:

ghci> compare 2 2 <> compare 2 5 -- EQ <> LT
LT
ghci> compare 2 2 <> compare 2 5 <> compare 5 2 -- EQ <> LT <> GT
LT
ghci> compare 2 2 <> compare 5 2 <> compare 2 5 -- EQ <> GT <> LT
GT

Чаще всего оператор <> семантически обозначает присоединения или склейки значения (поэтому его называют append operator)

Другая структура, моноид (S, R, e) - это полугруппа (S, R) с нейтральным элементом e таким, что x R e = e R x = x

В Haskell моноид определен так:

ghci> :i Monoid
type Monoid :: * -> Constraint
class Semigroup a => Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a
  {-# MINIMAL mempty | mconcat #-}
-- представители моноида

До появления модуля Data.Semigroup в стандартной библиотеке компилятора GHC 8.0.1 в 2016 году полугрупп не существовало, поэтому использовался использовался Monoid, который имеет свой оператор mappend - аналог <>. Сейчас mappend по умолчанию выполняет то же самое, что и <>

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

instance Monoid Min where
    mempty :: Min
    mempty = Min maxBound -- возвращаем наибольшее целое число

instance Monoid Sum where
    mempty :: Sum
    mempty = Sum 0 -- возвращаем ноль

ghci> mempty <> (Min 5) == (Min 5) <> mempty
True
ghci> mempty <> (Min 5) == (Min 5)
True

Нейтральный элемент позволяется сделать такую свертку:

ghci> foldr (+) 0 [1, 2, 3, 4]
10

Вот так:

ghci> foldr (<>) mempty [Sum 1, Sum 2, Sum 3, Sum 4]
Sum 10

Функция mconcat по своей сути принимает список и делает то же самое, что и foldr (<>) mempty, упрощая запись:

ghci> mconcat [Sum 1, Sum 2, Sum 3, Sum 4]
Sum 10

Также можно определить полугруппу и моноид для множества функций a -> b. Для этого:

Каждая функция этого множества должна принимать значение типа a
И возвращать значение типа b, причем множество b должно иметь определенную полугрупп/моноид

Оператор <> для такой группы определяется так:

instance Semigroup b => Semigroup (a -> b) where
  f <> g = \x -> f x <> g x
  -- по сути лямбда, которая объединяет результаты
  -- двух функций

А нейтральный элемент так:

instance Monoid b => Monoid (a -> b) where
  mempty = \_ -> mempty
  -- по сути нейтральный элемент типа b

Такой реализацией пользуется моноид All из модуля Data.Monoid, который проверяет, что все функции возвращают True для заданного параметра, например:

import Data.Monoid (All(..))

positive, evenInt, small :: Int -> All

positive x = All (x > 0)
evenInt x = All (even x)
small x = All (x < 100)

ghci> positive <> evenInt <> small $ 5
All {getAll = False}
ghci> positive <> mempty $ 5 -- для All нейтральный элемент - All True
All {getAll = True}

В общем случае моноид на таком множестве является поточечным (операция между функциями определяется независимо для каждой точки)

В частном случае моноид из функции a -> a (такое преобразование называется эндоморфизмом) является моноидом эндоморфизмов. Для этого в Haskell есть обертка Endo { appEndo :: a -> a } из модуля Data.Monoid, которая реализует композицию как оператор <> и хранит ее в поле appEndo:

ghci> fs = [Endo (+1), Endo (*2), Endo (+10)]
ghci> appEndo (mconcat fs) 5
31  -- ((5 + 10) * 2) + 1

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

Функтор

В Haskell выделяют 3 уровня абстракций:

Значения (Value или Term) - конкретные данные, с которыми работает программа, например, 42::Int
Типы (Type) - множества возможных значений, например, Int
Роды (или тип типов, Kind) - мета-типы, определяющие, является ли тип самостоятельным или ему не хватает других типов в качестве параметров, чтобы стать таковым

Главный род обозначается * (или Type в современных версиях) и является родом для всех обычных типов, таких как Int или String

Типы рода с параметрами принимают один или несколько типов и возвращают конкретный тип, например Maybe, род которого обозначается * -> *, или Either рода * -> * -> * (Maybe и Either являются конструкторами типов)

Рода помогают компилятору проверять корректность конструирования типов

Род типа можно посмотреть в интерпретаторе с помощью команды :k:
```
ghci> :k Int     
Int :: *
ghci> :k Maybe
Maybe :: * -> *
ghci> :k Maybe Int
Maybe Int :: *
ghci> :k []   
[] :: * -> *
ghci> :k (,,)
(,,) :: * -> * -> * -> * -- кортежу из 3 элементов нужно 3 типа-параметра
ghci> :k (Int, Char, Float)
(Int, Char, Float) :: * -- а этот кортеж уже является конкретным типом
```

Функтор же - это класс типов Functor в Haskell, который определен так:

ghci> :i Functor
type Functor :: (* -> *) -> Constraint
class Functor f where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}
        -- Defined in `GHC.Internal.Base'
-- представители

Здесь f - это конструктора типа, род которого * -> * (то есть имеющий один тип-параметр), а fmap - это функция, которая принимает функцию a -> b и превращает в функцию f a -> f b. По сути fmap говорит, как выполнить функцию для значения типа a, если у нас есть значение типа f a, и аналогично получить f b вместо b

Например, Maybe a имеет представителя Functor, который определен так:

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just a) = Just (f a)

То есть для Nothing результат любой функции - это Nothing, а применение функции f к (Just a) будет Just (f a). Таким образом, можно получить функцию, которая будет работать с типом Maybe a, от функции, которая работает с типом a:

ghci> (fmap (+1)) (Just 5)          
Just 6
ghci> (fmap (+1)) (Nothing)
Nothing

Аналогично fmap можно определить для списков:

instance Functor [] where
  fmap = map -- просто для каждого элемента применяем функцию

Работать это будет так:

ghci> fmap (+1) [1, 2, 3]
[2,3,4]
ghci> (+1) <$> [1, 2, 3] -- инфиксный аналог
[2,3,4]
ghci> (+1) <$> ((^2) <$> [1, 2, 3])
[2,5,10]

Функтор полезен не только для таких типов-контейнеров, но и для рекурсивных типов, например, для дерева:

data Tree a = Leaf a | Branch (Tree a) a (Tree a)
  deriving Show

Функция fmap, которая превращает функцию для работы с a в функцию для работы с деревом Tree a, выглядит так:

instance Functor Tree where
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Branch left x right) = Branch (fmap f left) (f x) (fmap f right)

Получаем:

ghci> let tree = Branch (Leaf 1) 2 (Leaf 3)
ghci> fmap even tree
Branch (Leaf False) True (Leaf False)

fmap сделал из функции even для целых чисел функцию для работы с деревом целых чисел

Для кортежа (,) (у которого род * -> * -> *) функтор будет выглядеть иначе. В этом случае нужно зафиксировать один из типов кортежа (возьмем первый):

instance Functor ((,) s) where
  fmap :: (a -> b) -> (s, a) -> (s, b)
  fmap f (x, y) = (x, f y)

Получаем преобразование функции, которое преобразует второй элемент кортежа:

ghci> fmap (+1) (1, 2)
(1,3)

Для функций функтор будет выглядеть так:

instance Functor ((->) e) where
  fmap :: (a -> b) -> (e -> a) -> (e -> b)
  fmap = (.)

Здесь fmap преобразует функцию a -> b для работы с a в функцию e -> b для работы с e, которая применяет функцию e -> a и функцию a -> b (по сути делает композицию)

ghci> :t fmap (+1) (*2)
fmap (+1) (*2) :: Num b => b -> b
ghci> fmap (+1) (*2) 10
21

У корректной функции fmap есть такие свойства:

Преобразование тождественного отображения равно тождественному отображению - fmap id == id (id - полиморфная функция, возвращающая то же значение)
Композиция преобразований функций равна преобразованию композиции функций - fmap f . fmap g == fmap (f . g)

Этот сайт имеет открытый исходный код! Вы можете улучшить эту страницу или этот репозиторий!