ничего не понимаю. и это программисты. говно какое-то. пидоры, бл..
бл.., Шейнфинкель с Карри дали им комбинаторы. комбинируй, комбинируй комбинаторы, бл..!
"Не хочу! Хочу жрать говно!"
что такое? это программирование? это программирование?
суки. мудачьё. программисты. SICP прочитали. говно жрут. придоры бл.. ё..ые!

 

хроники хасида


* * *

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

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

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

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

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

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

* * *

преимущества ФП значительны:

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

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

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

Роберт Харпер, "Типы вокруг нас"

вы можете получить из коллекции какое-нибудь одно значение - если знаете ключ. но я говорю о другом - вам нужно что-то сделать С КАЖДЫМ значением

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

что вам в этом случае велит делать ООП? какой метод вызывать? так чтобы не надо было делать цикла по итератору?

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

{-# LANGUAGE DeriveFunctor #-}

data Tree a = 
              Empty 
            | Leaf (a, String) 
            | Node (Tree a) (Tree a) (Tree a) 
   deriving (Show , Functor)

x :: Tree Int 
x = Node (Node Empty (Leaf (2 , "abc")) (Leaf (3 , "def"))) 
         (Leaf (4, "ghi"))
         (Node (Leaf (5 , "jkl")) (Leaf (6 , "mno")) Empty)

f :: Int -> Int
f = (+ 1)

g :: Int -> Bool
g x | x > 4 = True | otherwise = False

fmp :: (a -> b) -> (Tree a -> Tree b)
fmp = \z x -> z <$> x

ghci> x
Node (Node Empty (Leaf (2,"abc")) (Leaf (3,"def"))) (Leaf (4,"ghi")) 
  (Node (Leaf (5,"jkl")) (Leaf (6,"mno")) Empty)

ghci> fmp f x
Node (Node Empty (Leaf (3,"abc")) (Leaf (4,"def"))) (Leaf (5,"ghi")) 
  (Node (Leaf (6,"jkl")) (Leaf (7,"mno")) Empty)

ghci> fmp g x
Node (Node Empty (Leaf (False,"abc")) (Leaf (False,"def"))) (Leaf (False,"ghi")) 
  (Node (Leaf (True,"jkl")) (Leaf (True,"mno")) Empty)


вот эта вот магия с fmp - называется Functor. магию там производит оператор <$>

мы передаем не ссылку, а код, как данные, и именно поэтому можем передавать первым аргументом для fmp функции с РАЗЛИЧНЫМИ типами возвращаемого значения

а теперь реализуйте этот игрушечный пример на жабе или плюсах и сравните

* * *

монады - это крошечный интерфейс, определенный для типа и подчиняющийся неким правилам

Стефан Дихл


f : a -> b

pure : a -> M a

(>>=) : M a -> (a -> M b) -> M b

g : M a -> M b
g x = x >>= pure . f

join : M (M a) -> M a
join x = x >>= id

applic : M (a -> b) -> (M a -> M b)

 

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

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

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

это что получается в таком случае?

а получается вот что - нам нужно на каждую такую цепочку объектов определять новый класс или же строить классы так, чтобы они могли между собой свободно и непринужденно объединяться. вот тут и начинается самое интересное :)

обычная архитектура: собрать несколько компонент типа A вместе для того, чтобы сгенерить "network" или "topology" с типом B

архитектура Хаскеля: собрать несколько компонент типа A вместе для того, чтобы сгенерить новую компоненту того же типа A, неразличимую от составляющих ее частей

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

    " так - вот эти вот Bs несопряжимы посему давайте создадим сеть из них и назовем ее C"
    " так - хотелось бы собрать вместе несколько Cs, такшта создадим сеть из Cs и назовем ее D"
   ...

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

Gabriel Gonzalez, "Масштабируемая программная архитектура"

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

идея ФП в том, чтобы строить сложный код из простых функций

идея ООП в том, чтобы строить сложный код из обьектов

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

есть несколько функций: f1(x1), f2(x2), f3(x3) ..

например, это POSIX call-ы или что-то ещё в твоём алгоритме

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

и тогда ты - шмак - и делаешь монаду, например, catch_error:

catch_error ([f1, f2, f3, f4] , initial_value)

где initial_value — это то, что будет отдано в f1(x1). эта монада будет устроена так: она запустит f1 с initial_value, проверит результат, запустит f2, если не было ошибки, и т.д.

* * *

ошибки/исключения
отсутсвующие значение
изменяемое состояние

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

module OptionFunctor =
    struct
	let fmap f = function
	      Some a  -> Some (f a)
	    | _       -> None
    end

module Demo1 =
    struct
	open OptionFunctor
	let eg1 = fmap abs     (Some      5 )
	let eg2 = fmap List.hd (Some [3;4;5])
	let eg3 = fmap abs      None
    end  

type 'a valid = Success of 'a | Failure of string                 

module ValidFunctor =
    struct
	let fmap f = function
	    | Success a -> Success (f a)
	    | Failure e -> Failure e
    end                                                  

module Demo2 =
    struct
	open ValidFunctor
	let eg4 = fmap String.length (Success        "abc")
	let eg5 = fmap List.tl       (Success      [1;2;3])
	let eg6 = fmap abs           (Failure "smth wrong")
    end                             

# open Demo1 ;;
    
# eg1 ;;
- : int option = Some 5

# eg2 ;;
- : int option = Some 3

# eg3 ;;
- : int option = None

# open Demo2 ;;

# eg4 ;;
- : int valid = Success 3

# eg5 ;;
- : int valid = Success [2;3]

# eg6 ;;
- : int valid = Failure "smth wrong"

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

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

* * *

первая проблема - это фундаментальное непонимание термина "ФП".

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

Роберт Харпер, "Типы вокруг нас"

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

1. частичность области определения функции

а именно - ограниченность, неполность этой самой области определения

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

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

с монадами же эта проблема решается удобно - функция возвращает не просто результат, а результат в виде монады - опциональное Maybe (результат либо отстутствие результата, aka Option),

f :: Int -> Int -> Maybe Int
f x y | y == 0 = Nothing
      | otherwise = Just $ div x y


взято из "Антон Холомьев. Учебник по Хаскелю"

или в виде суммы типов Either (aka Co-Product, либо результат либо сообщение об ошибке, причем сообщение может быть какого угодно типа - как нам удобнее, так тип и определим в каждом конкретном случае, а вот монаду Either при этом переписывать нам не надо будет :)

g :: Int -> Int -> Either String Int
g x y = case y of
  0 -> Left "div by zero!"
  _ -> Right $ div x y

вот и стала бибилиотечная функция div тотальной, а мы и не напрягались особо

2. сложные структуры и коллекции данных

у вас могут быть коллекции, которые представляют собой сложную конструкцию, но из достаточно простых элементов, которые скомпонованы в контейнере из ограниченного набора типов - List, Set, Map или Tree. задача в том, чтобы эту сложную структуру данных как-то обрабатывать

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

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

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

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

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

data Tree a b = Empty | Leaf (a , b) | Node (Tree a b) (Tree a b) (Tree a b) 
  deriving (Show)

plus :: (Num a , Num b) => Tree a b -> Tree a b -> Tree a b
plus Empty d = d 
plus d Empty = d 
plus (Node l1 x1 r1) (Node l2 x2 r2) = Node (plus l1 l2) (plus x1 x2) (plus r1 r2) 
plus (Node l1 c r1) d = Node l1 (plus c d) r1 
plus c (Node l2 d r2) = Node l2 (plus c d) r2 
plus (Leaf (x1 , s1)) (Leaf (x2 , s2)) = Leaf (x1 + x2 , s1 * s2) 

instance (Num a , Num b) => Monoid (Tree a b) where
  mempty = Node Empty Empty Empty 
  mappend x y = plus x y

x , y , z :: Tree Int Int 
x = Node Empty 
         (Leaf (1, 1))
         (Node (Leaf (2 , 1)) (Leaf (3 , 1)) (Leaf (4 , 1)))
y = Node (Node (Leaf (5 , 1)) (Leaf (6 , 1)) (Leaf (7 , 1))) 
         (Leaf (8 , 1))
         (Node (Leaf (9 , 1)) (Leaf (10 , 1)) Empty)
z = Leaf (11 , 1)


ghci> mconcat [x , y, z]
  Node (Node (Leaf (5,1)) (Leaf (6,1)) (Leaf (7,1))) (Leaf (20,1)) (Node (Leaf (11,1)) 
    (Leaf (13,1)) (Leaf (4,1)))

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

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

тут все колдовство происходит в моноиде. если ваша структура данных - моноид, то она тоже будет околдована

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

а можно написать этот код монадически и тогда - сразу полиморфно, но моноид тоже стоит того, чтобы быть отмеченным, в конце концов "монада - это моноид в категории эндофункторов, в чем проблема?"©

3. асинхронность выполнения

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

4. работа со структурами данных, которые предполагают (дополнительное) изменяемое состояние

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


взято из "Антон Холомьев. Учебник по Хаскелю"

import Control.Monad.State
import Data.Map as M

main :: IO ()
main = readLn >>= \c -> readLn >>= \v -> print $ evalState (f0 v c) ini 

f1 :: String -> Int -> State Sta (Maybe Int)
f1 v c = eval $ Add (Dec v) (Val c)

type Sta = Map String Int

ini :: Sta 
ini = fromList [("var0" , 0) , ("var1" , 1) , ("var2" , 2) , ("var3" , 3)]

data Expr = Dec String 
          | Inc String 
          | Val Int 
          | Var String 
          | Add Expr Expr 

eval :: Expr -> State Sta (Maybe Int) 
eval (Val n)   = return $ Just n
eval (Var m)   = get >>= return . M.lookup m 
eval (Inc m)   = modify (update (\x -> Just (x + 1)) m) >> eval (Var m)
eval (Dec m)   = modify (update (\x -> Just (x - 1)) m) >> eval (Var m)
eval (Add i j) = eval i >>= \x -> eval j >>= \y -> return $ liftM2 (+) x y
    

5. переменные среды

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

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


взято из "Антон Холомьев. Учебник по Хаскелю"

import Control.Monad.Reader

main :: IO ()
main =
  read <$> getLine >>= \c -> getLine >>= \v -> print $
  runReaderT (eval $ Add (Var v) (Val c)) env

type Env = [(String , Int)]

env :: Env
env = [("z" , 5) , ("y" , 12) , ("x" , 34) , ("w" , 7)]

data Expr = Val Int | Var String  | Add Expr Expr  

eval :: Expr -> ReaderT Env Maybe Int
eval (Val n)   = return n
eval (Var m)   = ask >>= lift . lookup m >>= return 
eval (Add i j) = liftM2 (+) (eval i) (eval j)
  

6. журналирование

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


взято из "Антон Холомьев. Учебник по Хаскелю"

import Control.Monad.Writer

main :: IO ()
main = 
  read <$> getLine >>= \x1 -> read <$> getLine >>= \x2 -> 
  return (runWriterT (eval $ Add (Val x1) (Val x2))) >>= \(Just (rez , log)) ->
  print (show rez) >> writeFile "your.log" log 

data Expr = Val Int | Add Expr Expr 

eval :: Expr -> WriterT String Maybe Int
eval (Val n)   = return n
eval (Add i j) = 
  tell "sum of\t" >> eval i >>= \x -> 
  tell (show x)   >> eval j >>= \y -> 
  tell ("\tand\t" ++ show y) >> return (x + y) >>= \z -> 
  tell ("\tis\t" ++ (show z) ++ "\n") >> return z 

7. парсеры

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

TODO : examples

8. интерпретаторы/компиляторы/DSL

здесь огромные возможности по использованию монад в качестве инструмента реализации для AST и последующей обработке этого самого дерева в виде некоторой его прямой интерпретации либо трансформации в тоже некоторую монадическую структуру которая потом сама непосредственно будет исполнять требуемый результат :) например для этого может очень быть удобна в использовании так называемая свободная монада

TODO : examples

* * *

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

	              step -> step -> step -> …

а теперь представьте себе, что вы хотите расширить эту идею в двух направлениях:

более того, вы бы хотели внести такие изменения без изменения уже имеющихся функций для шагов

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

          step -> glue -> (step -> glue -> (step -> glue … )))
задача "клея" - обновлять мета-данные и/или принимать решения об останове или ветвлении. некоторые "склеивающие" функции будут очень простыми, другие могут быть посложнее. и вот, если вы назовете вашу первую функцию (содержащию первоначальные вход и мета-данные) “unit” а вашу "склеивающую" функцию назовете “bind”, то в общем-то вы получили монаду

а поскольку “unit” и “bind” имеют одну и ту же "форму", то вы можете строить наборы операций над монадами без необходимости изменять ваши “step”-функции

* * *


f1 : Int -> Bool 
f1 = \x => if x > 5 then True else False 

f2 : Bool -> String 
f2 = \x => if x then "aaa" else "zzz" 

g : (a -> b) -> (Maybe a -> Maybe b) 
g = \f , x => (Just f) <*> x

h : (a -> b) -> (Either String a -> Either String b) 
h = \f , y => (Right f) <*> y 

t1 : Maybe Int -> Maybe Bool
t1 = g f1 

t2 : Maybe Bool -> Maybe String
t2 = g f2 

t3 : Either String Int -> Either String Bool
t3 = h f1 

t4 : Either String Bool -> Either String String
t4 = h f2

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

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

так монады это как раз и есть по сути одна из таких функций :)

монады - это просто две функции - bind и unit

unit - это конструктор монады (полиморфный)

bind - это композиция двух функций, каждая из которых возвращает монаду

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


module type MONAD =
  sig
      type 'a t
      val bind   : 'a t -> ('a -> 'b t) -> 'b t
      val pure   : 'a -> 'a t
  end

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

* * *

Правило Номер Раз монадического паттерна говорит о том, что всегда есть возможность "завернуть" значение типа T в экземпляр типа M<T>. т.е. требуется, чтобы был вспомогательный метод:

        static M<T> CreateSimpleM<T> (T value)

Правило Номер Два монадического паттерна говорит о том, что если есть функция с сигнатурой A→R, то вы можете применить ее к экземпляру типа M<A> и получить в результате экземпляр типа M<R>. т.е. требуется, чтобы был вспомогательный метод:

        static M<R> ApplyFunction<A, R> (M<A> wrapped, Func<A, R> function)
все? нет, не все

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

"Ну теперь-то уж все? Да? <вздыхая ...> Нет." мы все еще нуждаемся в еще одном правиле:

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

    Func<X, M<Y>> f = whatever;
    M<X> mx = whatever;
    M<Y> my = ApplyFunction (mx, f);

    Func<Y, M<Z>> g = whatever;    
    M<Z> mz1 = ApplyFunction (my, g);
    
    Func<X, M<Z>> h = ComposeSpecial (f, g);
    M<Z> mz2 = ApplyFunction (mx, h);
необходимо, чтобы mz1 и mz2 были семантически одинаковы

стандартная терминология: первый метод называется "unit", а второй - "bind"

расставим точки над "i": "bind" принимает на вход поток выполнения и функцию и возвращает обратно поток выполнения. этот оператор "bind" НЕ ВЫПОЛНЯЕТ ПОТОК - он СОЗДАЕТ НОВЫЙ ПОТОК из старого и функции

* * *

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

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

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

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

* * *

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

Дийкстра

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

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

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

и это настолько удобно и просто, что никак иначе это и не захочется и не получится сделать

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

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

* * *

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

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

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

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

В ООП, чтобы добиться такого уровня масштабирования и компонентности, вам придется фактически закончить тем же самым ФП, только реализованным в виде объектов и при этом это все будет выглядеть хуже, чем если бы вы сразу же все сделали через ФП (пусть даже и через объекты - это тоже возможно, но усилий требует больше)

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

* * *

вот алгоритм ваших действий:

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

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

и забудьте о теории категорий! монады - это просто шаблон проэктирования, такой же как две дюжины шаблонов из книги Gang of Four “Design Patterns”. точнее - это шаблон для манипулирования потоком вычислений при сохранении некоторых семантических ограничений

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

но именно сами вот эти идеи - они дают уровень абстракций и возможностей по декларативному определению логики, которую в ООП достичь нельзя (или очень сложно) - при том, что в ФП они есть "бесплатно" (если о них знать и уметь их использовать правильно)

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

* * *

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

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

Бартоз Милевский

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

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

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

и так во всем: не любой парсер это монада, не любой асинхронный код это монада, и т.д.

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

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

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

вот если бы был фантастический ООП язык, в котором у "класса" List[Int] появлялись методы increment, +, * и константа 0, волшебным образом позаимствованные у Int и доопределённые для списка; а у "класса" List[String] появлялись методы append, charAt, ... и константа "пустая строка"; и у класса List[List[Int]] появлялись методы increment, +, *, ........ позаимствованные у List[Int] и доопределённые до List[List[Int]] и т.д., рекурсивно, вот ТОГДА это был бы функтор - то есть, когда этот генерик класс не только умеет строить списки определённого типа, но и дополняет список методов, ЗАИМСТВУЯ МЕТОДЫ У ПАРАМЕТРА

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

в ОО языках прямого аналога этому нет; да даже и кривого аналога "автодополнения" методов нет. в известных мне ОО языках даже List[Int] не является классом отдельным от List[String], поэтому в кавычках. с этим ничего нельзя поделать; нужно как-то въезжать, больше ничего не остаётся

* * *

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

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

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

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

Крис Окасаки

вот вы говорите что "да ведь не проблема же вернуть вместе с результатом еще и код статуса выполнения - успех или не успех" и т.д. ну вот тут бы я не торопился с вами согласиться - еще какая проблема! вот как на практике это сделать?

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

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

так почему же тогда монады оказывается не нужны? может просто потому, что вы не знаете о них ничего?

обычно лучше писать так:

	
	void УправляющаяФункция()
	{
		Status status = ВычисляющаяФункция()
		switch(status)
		{
			case StatusOne: NextFunction1(); break;
			case StatusTwo: NextFunction2(); break;
			default: NextDefault(); break;
		}
	}
чтобы каждый блок кода отвечал за свою часть и его можно было бы легко понять

так а результат собственно там где в вашем этом коде?

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

вы все таки главного не понимаете - нам нужны именно функции. нам не нужно изменение в поле класса и тем более в базе данных

работа с запросами к реляционной базе данных есть по сути своей обращение к такой огромной глобальной переменной - без мальейшей возможности рассуждений о ее поведении. при этом наблюдается жуткое несоответствие между "желанием исользовать бизнес-обьекты" и "поведением реальных данных". конечно, гораздо приятнее работать с "умными данными" нежели чем с "тупыми", но это несоответствие рушит стройную концепцию ООП. если же вы используете ФП, то вы не "чините" это несоответствие - вы используете парадигму, которая такого несоответствия просто и не имеет! вы конечно теряете "вкусности" от "бизнес-обьектов", но программирование - это всегда trade off

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

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

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

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

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

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

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

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

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

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

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

в этом смысл монад - мы можем строить сколько угодно вложенное создание монад, но на выходе у нас всегда будет только одна монада как результат

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

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

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

и вот только после того как мы начинаем программировать в исключительно чистых функциях вот только тогда нам становятся нужны (и понятны) монады

ну, в смысле "что такое" вам тут уже понаписали :) а в смысле "как работает" - вот мой вариант:

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


for a in [1..100]:
  for b in [a..10]:
    for c in [1..a+b]:
      ...ешё много for-ов
или:

a = do_something_1 (&success);
if (success) {
  b = do_something_2 (a , &success);
  if (success) {
    c = do_something_3 (a , b , &success);
      ..
  }
}
можно и ещё примеров подобрать, но суть в этом

правильно подобранная монада делает из этого вот что:


a <- [1..100]
b <- [a..100]
c <- [1..a+b]
...
и, соответственно,

a <- do_something_1 ()
b <- do_something_2 (a)
c <- do_something_3 (a , b)
...
все детали прячутся в конкретную монаду

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

* * *

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

      class Control.Category.Category a => Arrow (a :: * -> * -> *) where

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

пример - структуры данных, точнее коллекции данных. это ведь - категории

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

вот допустим у нас есть такая структура данных (на Скале)

   Stream [Map [(A , B , C) , Map [K , V]]]
нам нужно обработать эту структуру данных и немного ее трансформировать в почти похожую, но немного другую - нам нужно например взять такую функцию
    (A , B , C) => Map [I , Map [K , V]]
и применить к вышеуказанной структуре, чтобы получить вот такую
    Stream [Map [I , Map [Map [K , V]]] , Map [K , V]]
то есть подставить результат туда, куда нужно и дальше продолжить в том же духе :) до победного конца

идея в том что мы можем взять функцию

                 (A , B , C)                    =>            Map [I , Map [K , V]]
и получить из нее функцию
    Stream [Map [(A , B , C) , Map [K , V]]]    =>    Stream [Map [I , Map [Map [K , V] , Map[K , V]]]]
а как это сделать? ну можно примерно вот так
   ( (A ,B , C) => Map [I , Map [K , V]] ) =>
       ( Stream [ Map [ (A , B , C) , Map [K , V] ] ] =>
         Stream [ Map [I , Map [Map [K , V]]] , Map [K , V] ] ) = ???

:)
идея понятна? но это еще не всё! это только начало :) идея-то в чем вообще заключается на самом-то деле? в том она заключается, что мы это дело можем легко обобщить! и помогут нам тут как раз стрелки

ведь что мы сделали? мы взяли чистую простую (относительно конечно) функцию

     (A , B , C) => Map [I , Map [K , V]]
и залифтили ее (поместили) в другой, более сложный, контекст (структуру данных), то есть в категорию (это есть функтор - он нам из одной категории в другую морфизмы помещает)

а если нам такие вещи нужно делать постоянно - каждый день по многу раз? ведь это же нормальная ситуация

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

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

    class Category A => Arrow A
       arr (b -> c) :: A b c 
для некоего A (которое может быть чем угодно) которое символизирует собой стрелку (на самом деле категорию назначения для лифтинга)

нам еще предлагается реализовать функцию >>> которая просто композит между собой две залифтинные стрелки (для функций - (.), для монад - (>>=), для аппликативов - (<*>) и тд)

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

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

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


маленькая Алиса с папой-математиком в зоопарке:

Алиса  : Котята!
Папа   : Милые, не правда-ли? Тут их двое.
Алиса  : Посмотри - щенята! 
Папа   : Ты же умеешь считать - двое щенят!
Алиса  : Лошадки!
Папа   : А скажи мне, что общего между котятами, щенятами и лошадками?
Алиса  : Ничего общего! 
Папа   : Ну что-то общее есть. Сможешь ли ты увидеть - что именно? 
Алиса  : Нет! Щенок не котенок и лошадка - тоже не котенок.
Папа   : Давай я тебе обьясню!
         Для начала возьмем множество S, которое строго упорядочено и в котором каждый
         элемент является подмножеством S. О чем тебе это говорит? 
Алиса  : [рыдает навсхлип]

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

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

предположим, что нам надо найти сумму первых восьми натуральных чисел. один способ сделать это - шаг-за-шагом:


sumUpTo2 = 1 + 2
sumUpTo3 = sumUpTo2 + 3
sumUpTo4 = sumUpTo3 + 4
..
result = sumUpTo7 + 8

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


sum1To4 = 1 + 2 + 3 + 4
sum5To8 = 5 + 6 + 7 + 8
result = sum1To4 + sum5To8

и рекурсивно разделить каждую из двух задач пополам и т.д. - пока не достигнем уровня одиночной бинарной операции:


sum1To2 = 1 + 2
sum3To4 = 3 + 4
sum1To4 = sum1To2 + sum3To4

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

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

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

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

например: 3 - 2 есть 3 + (-2). вместо "вычитания"-глагола, используем "отрицание"-существительное. тогда

        5 + (-3) + (-2)
и поскольку мы теперь используем ассоциативное сложение, то
        5 + (-3 + -2) = (5 + -3) + -2

тот же самый подход работает и с делением:

        12 / 3 / 2 = 12 * (1/3) * (1/2)
, и мы уже имеем дело с ассоциативным "умножением" и свойством "обратность"

идея использования списка обьектов в качестве моноида пришла из математики, где это называется "free monoid". а в CS это стало называться "Kleene star" (A*) и если не использовать пустых листов, т.е. обходиться без нейтрального элемента, то такая структура называется в математике "free semigroup" а в CS - "Kleene plus" (A+). обозначения "star" and "plus" хорошо знакомы всем тем, кто имел дело с регулярными выражениями

моноид легко создать из типа "record" - стоит только убедиться, что каждое поле есть моноид

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

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

нейтральный элемент не всегда нужен, но если вам все же приходится иметь дело с пустыми списками - то его все же придется иметь. а что делать, если наши данные - не числа? как придумать "нейтраль" в таких случаях? например, натуральные числа не имеют в своем составе нуля - они являются полугруппой. и если вы все же захотите иметь нейтраль, тогда вам на помощь придет трюк называемый "augmentation with extra case" - мы сперва определим специальный случай Zero (не число!), а после этого создадим функцию addPositive которая будет обрабатывать в том числе и сложение с этой исскуственной нейтралью:


type positiveNum = Positive of int | Zero

let addPositive i1 i2 =
    match i1 , i2 with
    | Zero , _ → i2
    | _ , Zero → i1
    | Positive p1 , Positive p2 → Positive (p1 + p2)

есть в таком подходе и "подводные камни":

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


      type 'a normalOrIdentity = Normal of 'a | Zero

в Окамле такой тип уже есть в языке - это встроенный тип option и всякий раз, когда нам нужна "нейтраль" которой нет - мы будем использовать None для ее представления. а тип Some будем использовать для "нормальных" значений


 let optionOpp f x1 x2 =
    match x1 , x2 with
    | None , _          → x2
    | _ , None          → x1
    | Some s1 , Some s2 → Some (f s1 s2)

optionOpp превращает любую функцию 'a → 'a → 'a в функцию "lifted" to the option тип, которая имеет сигнатуру 'a option → 'a option → 'a option

module type MONOID =
  sig
        type t

	val append  : t → t → t
	val zero    : t
	val concat  : t list → t
  end

module OptInt : (MONOID with type t = int option) =
  struct
        type t           = int option

        let zero         = None

        let append x1 x2 = match x1 , x2 with
                             | None , _          → x2
                             | _ , None          → x1
                             | Some s1 , Some s2 → Some (s1 + s2)

        let concat xs    = List.fold_left append zero xs
  end

module AddPositive = OptInt

let p1 = Some 1
let p2 = Some 2
let z0 = None
let f  = fun x → Some x

let ex1 = AddPositive.append p1 p2
let ex2 = AddPositive.append p1 z0
let ex3 = AddPositive.append z0 p2
let ex4 = AddPositive.append z0 z0

let ex5 = [1; 2; 3; 4] |> List.map f |> AddPositive.concat

let ex6 = [] |> List.map f |> AddPositive.concat

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

простейший пример: подсчет среднего у массива. допустим ваш массив выглдит так:

                     [ 24.0 ; 29.0 ; 31.1 ; 26.4 ; 23.4 ; 24.1 ; 28.2 ]  
ну, вы пишете код и получаете результат: 26.599999999999998. а что вот это вот число именно значит? должны ли мы округлить его до 27? или до 30? или все же до 26.6? а что мы хотим узнать - изучая полученный результат? правильный ответ зависит в конце концов от того, откуда мы получили первоначальный массив и что по сути является его "нейтралью". и вовсе не обязательно, что это - численный ноль! и тогда вам нужен особый, "свой", моноид