автор : dotneter

легкая прогулка от функтора через монаду к стрелке

давайте совершим прогулку по цепочке Functor, Applicative, Monad, Category, Arrow, в процессе которой я попытаюсь показать, что все это придумано не для того, чтобы взорвать мозг, а для решения вполне реальных проблем

рассмотрим один из распространённых сценариев, когда функция может и не вернуть результат, и представим ответ такой функции в виде класса Maybe. по сути это тот же null, только более цивилизованный

Lifting

что есть класс Maybe? можно считать его функцией над типом, которая все обычные типы a переводит в специализированные типы Maybe a:

f Int → Maybe Int f Double → Maybe Double f Bool → Maybe Bool f Char → Maybe Char -------------------------------- f a → Maybe a

будем называть такое преобразование - лифтингом

проблема номер один: нам необходима функция над типом a, которая позволит сделать переход a → Maybe a

class Lifting a where
  lift :: a → f a

instance Lifting Maybe 
  lift x = Just x

теперь мы можем все что угодно поднять на уровень Maybe:

λ> (lift 3) :: Maybe Int
Just 3
λ> (lift False) :: Maybe Bool
Just False
λ> (lift 'b') :: Maybe Char
Just 'b'

Functor

хорошо, поднять-то мы подняли, но у нас осталась куча функций вида a → b, которая работает для предыдущего уровня, но не работает для нового. что же делать?

очевидно, что можно каждый раз проверять есть ли в Maybe что либо с типом a, и если есть, то применять функцию a → b к тому, что в нем содержится, и возвращать Maybe для результата, а если ничего там нет, то возвращать Nothing. собственно, это тот сценарий, который используется в случае проверки на null

закодируем такой подход в виде:

class Functoring m where 
  mmap :: (a → b) → m a → m b

instance Functoring Maybe where 
  mmap f (Just x) = Just (f x)
  mmap f Nothing  = Nothing 

таким образом мы подружили наши старые функции с новым уровнем

λ> mmap not (lift False) :: Maybe Bool
Just True
λ> mmap (+4) (lift 12) :: Maybe Int
Just 16
λ> mmap not Nothing
Nothing
λ> mmap (+4) Nothing
Nothing
λ> mmap (+4) (Just 6)
Just 10
λ> mmap not (Just False)
Just True

Applicative

функции одной переменной типа a → b нам покорились, но что делать с функциями, принимающими несколько параметров: a → b → c? очевидно, что mmap нам тут особо не поможет

каррирование - это преобразование функции таким образом, чтобы ее возможно было частично применить и получить на выходе новую функцию:

λ> let add = \x y -> x + y
λ> let inc = add 1
λ> inc 10
11

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

class Applicativing f where
  apply :: f (a → b) → f a → f b

instance Applicativing Maybe where
  apply Nothing  _ = Nothing
  apply (Just f) x = mmap f x 

этот подход работает для любого количества параметров:

  λ> let add = \x y z -> x + y + z
  λ> let k1  = lift 1 
  λ> let k2  = lift 2 
  λ> let k3  = lift 3 
  λ> (lift add `apply` k1 `apply` k2 `apply` k3) :: Maybe Int
  Just 6

Monad

с обычными (a → b, a → b → c, a → b → c ... → z) функциями разобрались, но раз у нас есть два уровня, то значит возможны и функции вида a → Maybe b и параметры типа Maybe a

естественно, что теперь мы хотим, чтобы у нас была такая возможность: Maybe a → (a → Maybe b) → Maybe b

решить проблему с помощью mmap не выйдет, так как в результате получим Maybe (Maybe b). поскольку apply реализована через mmap, то и она тут не поможет. поэтому нам нужна еще одна функция над типами:

class Monading m where
  bind :: m a → (a → m b) → m b
  
instance Monading Maybe where
  bind (Just x) f = f x
  bind Nothing  _ = Nothing

итак, мы решили практически все проблемы, которые касаются применения функций, возникшие при использовании Maybe

λ> let s = \x -> if x == 0 then Just False else Just True
λ> (Just 5) `bind` s
Just True
λ> Nothing `bind` s
Nothing
λ> (Just 0) `bind` s
Just False

Category

давайте перейдем к композиционному стилю программирования и посмотрим, какие здесь проблемы у Maybe a и как их можно решить

что такое композиционный стиль? это такой подход, когда мы вместо того, чтобы применять функции одна за другой к результату предыдущего вычисления, объединяем их в некое подобие конвейера:

 f = length . filter (>3) . map (+1) . drop 3 

(.) - это оператор композиции в Haskell , с очень низким приоритетом

функция f отбрасывает первые три элемента списка, прибавляет 1 ко всем остальным, фильтрует все что больше трех и возвращает длину полученного списка

такой стиль отличается наглядностью

полагаю у вас в подсознии уже начал мелькать образ теории категорий, и это неспроста. давайте вспомним о чем там идет речь

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

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

 

 

так вот - для морфизмов как раз и определено понятие композиции:

g : A - > B, f : B → C === f compose g : A → C

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

class Categoring cat where
  compose :: cat b c → cat a b → cat a c

instance Categoring (→) where
  f `compose` g = \x → f (g x) 

вернемся к композиционному стилю. у обычных функций с ним нет никаких проблем:

λ> let f1 = \y -> y + 1
λ> let f2 = \y -> y * 2
λ> (f2 `compose` f1) 1
4

однако у функций вида a → Maybe b , b → Maybe c проблема есть и заключается она в том, что выход первой не стыкуется сo входом второй

так как у нас сейчас пойдет много сигнатур вида a → Maybe b давайте напишем для них обертку. можно и без нее, но с ней как-то нагляднее:

newtype Kleisli m a b = Kleisli { runKleisli :: a → m b }

категория Клейсли - категория, где морфизмы имеют вид a → M b . напишем функцию для их композиции:

instance Monading m => Categoring (Kleisli m) where
  (Kleisli f) `compose` (Kleisli g) = Kleisli (\a → bind (g a) f)

если не использовать оберток, запись была бы точно такой же, как и у обычных функций: f `compose` g

теперь мы можем создавать композиции из Клейсли-морфизмов:

λ> let f = \x -> Just (2 + x)
λ> let g = \x -> Just (3 * x)
λ> let h = (Kleisli f) `compose` (Kleisli g)
λ> runKleisli h 5
Just 17

Arrow

вот мы и подошли к последней проблеме

у нас есть функции двух видов: a → b и a → Maybe b и законное желание соединять их между собой в любой последовательности

при текущем раскладе это у нас не получится, но можно написать функцию:

class Categoring a => Arrowing a where
  arr :: (b → c) → a b c

instance Arrowing (→) where
  arr f = f

instance (Monading m, Lifting m) => Arrowing (Kleisli m) where
  arr f = Kleisli (compose lift f)

в итоге: мы можем комбинировать функции обоих видов, как нам заблагорассудится

λ> let f1 = \x -> x + 1
λ> let f2 = \x -> x * 10

λ> let m1 = \x -> lift (x * 2)
λ> let m2 = \x -> lift (x - 5)

λ> let a1 = arr f1
λ> let a2 = arr f2

λ> let k1 = Kleisli m1
λ> let k2 = Kleisli m2

λ> let r1 = k2 `compose`  a1 `compose` k1 `compose` a2
λ> let r2 = k1 `compose`  a2 `compose` k2 `compose` a1

λ> runKleisli r1 2
Just 36
λ> runKleisli r2 3
Just (-20)

у стрелок еще есть много интересных функций, с помощью которых можно виртуозно жонглировать конвейерами практически любой сложности. например:

и пр. но, пожалуй, на этом мы остановимся

заключение

возможно у вас возникнет вопрос, почему же такая иерархия практически ни в каких языках не встречается. ответ скорее всего в том, что для реализации нужна система типов сложнее, чем в том же C#

например, если мы, написав на C# подобный код для Maybe a, захотим написать все то же самое для списков (которые являются точно таким же переходом между уровнями a → [a], то нам придется ПРОДУБЛИРОВАТЬ ~90% кода

в Haskell , за счет классов и полиморфизма высшего порядка, существенная часть абстракций выделена и все манипуляции происходят над обобщенным типом X a где X может быть любым типом с одним параметром (например - [a], Maybe a, YourType a, ...)

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


listing

import Prelude hiding (Functor,map,Monad)

class Pointed f where
  pure :: a → f a

instance Pointed Maybe where
  pure = Just

class Functor f where
  map :: (a → b) → f a → f b

instance Functor Maybe where  
  map f (Just x) = Just (f x)  
  map f Nothing = Nothing  

class (Functor f, Pointed f) => Applicative f where
  apply :: f (a → b) → f a → f b

instance Applicative Maybe where  
  apply Nothing  _ = Nothing  
  apply (Just f) something = map f something  

class Applicative f => Monad f where
  bind :: f a → (a → f b) → f b

instance Monad Maybe  where
  bind (Just x)  k      = k x
  bind Nothing   _      = Nothing

newtype Kleisli m a b = Kleisli { runKleisli :: a → m b }

class Category cat where
  compose :: cat b c → cat a b → cat a c

instance Category (→) where
  compose f g = \x → f (g x) 

instance Monad m => Category (Kleisli m) where
  compose (Kleisli f) (Kleisli g) = Kleisli (\b → bind (g b) f)

class Category a => Arrow a where
  arr :: (b → c) → a b c

instance Arrow (→) where
  arr f = f

instance Monad m => Arrow (Kleisli m) where
  arr f = Kleisli (compose pure f)