Аналоги монад Haskell

1. Аналоги на чем? 2. http://habrahabr.ru/post/127556/ http://habrahabr.ru/post/128070/ http://habrahabr.ru/post/128538/ http://habrahabr.ru/post/129909/

1. Аналоги на чем?

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

Функторный интерфейс (на слове интерфейс нужно акцентировать внимание) суть функция map:

class Functor f where
  map :: (a -> b) -> f a -> f b

-- map id == id
-- map (g . h) == map g . map h

(маленькое замечание: если типы это объекты категории Hask, а функции ─ её стрелки, то конструктор типа f :: * -> * осуществляет отображение из одного типа A :: * (объекта Hask) в другой тип f A :: * (другой объект), map при этом отображает функции (a -> b) (стрелки Hask) в функции (f a -> f b) (тоже стрелки); с соблюдением законов получаем эндофунктор Hask -> Hask).

Точечный = функторный + функция pure:

class Functor f => Pointed f where
  pure :: a -> f a

-- map g . pure == pure . g

Аппликативный = (функторный +) точечный + функция (<*>):

class Pointed f => Applicative f where
  (<*>) :: f (a -> b) -> f a -> f b

-- map g x == pure g <*> x

Монадический = (функторный + точечный +) аппликативный + функция (>>=):

class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b

-- pure a >>= k == k a
-- m >>= pure == m
-- m >>= (\x -> k x >>= h) == (m >>= k) >>= h
-- map f xs == xs >>= pure . f

Любые типы данных (конкретные, вроде заданных ADT, или абстрактные) к которым можно, так или иначе, построить монадический интерфейс называют «монадами».

Самый знаменитый пример ─ ST/IO:

{-# LANGUAGE RebindableSyntax, TypeOperators #-}

import Prelude hiding ( map, (>>), (>>=), return, Maybe(..) )
import Control.Arrow

-- | State transformer is a function that updates a state @s@ and returns an 
-- associated result @r@.
-- 
type s :~> r = s -> (r, s)

map :: (r -> r') -> s :~> r -> s :~> r'
map = (.) . first -- function composition
-- ^
-- map :: (r -> r') -> (s -> (r, s)) -> s -> (r, s)
-- map f st s = case st s of (r, s') -> (f r, s')

pure :: r -> s :~> r
pure = (,) -- pair
-- ^ aka @return@
-- pure :: r -> s -> (r, s)
-- pure r s = (r, s)

return = pure

run :: s :~> r -> s -> r
run st = fst . st -- function application
-- ^
-- run :: s -> (r, s) -> s -> r
-- run st s = case st s of (r, _) -> r

(>>=) :: s :~> r -> (r -> s :~> r') -> s :~> r'
st >>= f = uncurry f . st -- function composition
-- ^
-- (>>=) :: (s -> (r, s)) -> (r -> s -> (r', s)) -> s -> (r', s)
-- (st >>= f) s = case st s of (r, s') -> f r s'

(>>) :: s :~> r -> s :~> r' -> s :~> r'
st >> st' = st >>= const st' -- function composition
-- ^
-- (>>) :: (s -> (r, s)) -> (s -> (r', s)) -> s -> (r', s)

-- -----------------------------------------------------------------------------
-- * Example -- stack.

type Stack a = [a]

type SIO a = Stack a :~> a

push :: a -> SIO a
push x xs = (x, x : xs)

pop :: SIO a
pop (x : xs) = (x, xs)
pop [] = error "empty stack"

initialize :: SIO a
initialize = pure undefined

test :: SIO Integer
test = do initialize; push 1; push 2; push 3; pop

-- > test []
-- (3,[2,1])

-- -----------------------------------------------------------------------------
-- * Example -- RealWorld and I/O.

data RealWorld -- blah-blah-blah, abstract data type (no visible accessors, no
               -- visible constructors), supported by RTS.

type IO t = RealWorld :~> t

То есть монадический интерфейс к ST это, с точностью до незначительных переформулировок, конструктор кортежа в качестве pure/return и обычная композиция функций в качестве bind, run ─ обычная аппликация функции. IO это ST над RealWorld (ну, не совсем, тут обсуждается разница связанная с полиморфизмом ─ Lazy Functional State Threads, кроме того, run существует только в виде unsafePerformIO).

Подробнее ─ All About Monads, Typeclassopedia.

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

т.е. если есть srt.len() то тип стринг - монада?

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

А зачем аналоги монад?

Вот короткое, не слишком заумное (но философское) про монады на русском:

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

Тем не менее, жизнь на этом остановилась. Это лишь один взгляд на вычисления, и далеко не всегда самый удобный.

«Аналогами монад» является все многообразие исчислений, доступных в языках программирования. Выбирай любое и развлекайся. Не надо пытаться возводить удобный теоретический инструмент в абсолют.

т.е. если есть srt.len()

У len тип string -> int, так что она тут как-то ни при чём.

то тип стринг - монада?

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

[1,2,3] >>= \x -> [4,5,6] >>= \y -> return (x * y)

-- немного сахара:
do x <- [1,2,3]; y <- [4,5,6]; return (x * y)

-- ещё немного:
[x * y | x <- [1,2,3], y <- [4,5,6]]

-- результат:
[4,5,6,8,10,12,12,15,18]

т.е. list/arrow comprehensions это монадические вычисления для списков и массивов.

что есть монадический интерфейс и «соответствующие законы»?

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

map :: (a -> b) -> f a -> f b

для списков превращается (f = []) в реализацию интерфейса:

map :: (a -> b) -> [a] -> [b]
map ...

законы:

-- map id == id
-- map (g . h) == map g . map h

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

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

А зачем аналоги монад?

Придумали с начальником некий абстрактный тип данных + механизмы для работы с ним. Теперь ищем аналогичные абстракции.

Инварианты для начала можно поискать.

что-то похожее на монады в языках программирования

Без нормальной системы типов это всё равно больше риторический вопрос - «что является монадой?» или «что является категорией?». Что угодно - сопряжённые функторы задают монаду, а The slogan is ‘Adjoint functors arise everywhere’ (с) Saunders Mac Lane. Но начиная с λ₂ (+ ad-hoc polymorphism/instance arguments) можно гарантировать, что код на одном уровне Monad m => m a и на другом Monad m' => m' a не будет смешиваться (не только для Monad - и для более слабых и для более сильных классов от * -> *, и для трансформеров) и можно:

• Иметь слой (IO) в котором допустимо всё, в том числе системные вызовы, выделение плоской памяти, её изменение, адреса и их арифметика.
• Иметь слой в котором допустимы системные вызовы, но только с правами текущего пользователя, произвольного пользователя, или root-а.
• Слой в котором возможны только STM транзакции.
• Слой в котором строятся коллекции элементов (list comprehensions) и осуществляются операции над элементами этих коллекций (nondeterministic computation) ([], Set, etc.).
• Слой в котором вычисление может вернуть либо полезное значение, либо бесполезное (но безопасное) (Maybe).
• Слой в котором можно только писать в окружение, только читать из окружения, или только читать и писать из/в окружение (State, Environment, Reader, Writer).
• Слой в котором можно только задавать парсеры комбинаторами. Парсер - трансформер.
• Или только заниматься комбинаторным pretty printing-ом чего либо (html, например). Pretty printer или монада, или трансформер.
• Ну и так далее. Cont, Async, Error, Exception - тоже монады. Тайп-чекер в agde - трансформер. Взаимодействие с X-ами в xmonad - монада. jQuery is a monad. Разные уровни веб-сервера организуются в виде монадических трансформеров (например).
• Переходить с уровня на уровень с помощью трансформеров и liftинга.

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

определение из all about monades

1.1 What is a monad?

A monad is a way to structure computations in terms of values and sequences of computations using those values. Monads allow the programmer to build up computations using sequential building blocks, which can themselves be sequences of computations. The monad determines how combined computations form a new computation and frees the programmer from having to code the combination manually each time it is required.

определение состояние из Concepts, Techniques, and Models of Computer Programming

A state is a sequence of values in time that contains the intermediate results of a desired computation.

насколько я понимаю монады добавлены, чтобы можно было использовать explicit state + параллельное выполнение, хаскель он lazy(на самом дела strict) execution, a lazy + параллельность + explicit external state плохо дружат.

p.s. короче читай книжку.

Теорию категорий мне не осилить

Два фейспалма этому быдлокодеру за счет заведения!

Говноилиты в треде уже хватает, проходите мимо.

не слишком заумное (но философское)
монады

Хаскелисты не осилили.

монадический интерфейс к ST это, с точностью до незначительных переформулировок, конструктор кортежа в качестве pure/return и обычная композиция функций в качестве bind, run ─ обычная аппликация функции

  Монадический тип                       | Монадический интерфейс
  ---------------------------------------+----------------------------------------
  Любой (Identity monad)                 | map = ($)
                                         | return = id
  type Id a = a                          | (>>=) = flip ($)
                                         | run = id
  ---------------------------------------+----------------------------------------
  Функция из данного типа (Reader monad) | map = (.)
                                         | return = const
  type Reader = (->)                     | (f >>= k) r = k (f r) r
                                         | run = ($)
                                         | ask = id
                                         | local = flip (.)
                                         | asks r = ask >>= return . r -- id!
  ---------------------------------------+----------------------------------------
  Кортеж (Writer monad)                  | map = second
                                         | return a = (mempty, a)
  type Writer w a = (w, a)               | (w, a) >>= f = first (mappend w) $ f a
                                         | run = id
                                         | exec = fst
                                         | eval = snd
                                         | pass (w, (f, a)) = (f w, a)
                                         | listen (w, a) = (w, (w, a))
                                         | tell s = (s, ())
                                         | listens f m = m >>= return . first f
                                         | censor f m = pass $ m >>= return . (f,)
  ---------------------------------------+----------------------------------------
  s -> (a, s) (State monad)              | map = (.) . first
                                         | return = (,)
  type ST s a = s -> (a, s)              | (>>=) m = flip (.) m . uncurry
  type CoST s a = (a, s) -> s            | run = ($)
                                         | eval = (fst .)
  RealWorld -> (a, RealWorld) (IO, STM)  | exec = (snd .)
                                         | get s = (s, s)
  data RealWorld                         | put s = const ((), s)
  type IO a = ST RealWorld a             | modify f = get >>= put . f
  type STM a = ST RealWorld a            | gets f = get >>= return . f
  ---------------------------------------+----------------------------------------
  Продолжение (Cont monad)               | map f m c = m (c . f)
                                         | return = flip ($)
  type Cont r a = ((a -> r) -> r)        | (>>=) c = (.) c . flip
                                         | run = ($)
                                         | callCC f k = f (flip $ const k) k
  ---------------------------------------+----------------------------------------
  Maybe                                  | map f = maybe Nothing (Just . f)
                                         | return = Just
                                         | (>>=) = flip (maybe Nothing)
                                         | run = fromJust
  ---------------------------------------+----------------------------------------
  Список                                 | map = Data.List.map
                                         | return x = [x]
                                         | (>>=) xs = concat . flip fmap xs
                                         | run = head
  ---------------------------------------+----------------------------------------

чаще всего монадический тип это либо какой-то функциональный тип (монада - просто любая функция с данной сигнатурой), в этом случае функции монадического интерфейса это какие-то спецификации обычных комбинаторов (id, const, ($), (.)), либо какой-то контейнерный тип (кортеж, массив, список, множество, дерево, Maybe, etc.) - в этом случае return это просто синоним какого-нибудь конструктора, а bind с map - какие-то отображения контейнера.

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

Спасибо! Сохранил у себя как PDF.

Расскажи тогда еще и про монадические трансформеры.

Ещё бы про применение нужно написать. С контейнерными типами понятно. Со State тоже - ST, IO, STM. Writer может использоваться для pretty printеров (что логично), например:

import Data.Tree
import Data.DList
import "mtl" Control.Monad.Writer

type AST s = Tree s
type UnitT s a = Writer (DList (AST s)) a
type Unit s = UnitT s ()
type Combinator s = Unit s -> Unit s

-- * In case of HTML.

html, head, body, ... :: Combinator
[ html, head, body, ... ] = map mkElement [ "html", "head", "body", ...]

...

utf8 :: Unit
...

title :: String -> Unit
...

string :: String -> Unit
...

...

tmpl :: String -> String -> ByteString
tmpl tt hw = render $
  html $ do
    head $ do
      utf8
      title tt
    body $
      string hw

Reader может использоваться для парсеров вроде parsec (тоже логично). С другой стороны, на чём-то вроде Reader можно целый тайп-чекер организовать (это тот который теоремы доказывает). А Writer может быть чем-то вроде такого. Вот ещё применений Cont я не видел.

reader удобен ещё для банального хранения неизменяемых настроек и конружания как-то пул соединений к БД.

Cont я использую в моделировании.

hlint советует:

bindWT m f = m >>= \x -> liftM (bindW x) (liftfM f $ snd x)

liftfM = (liftM const .)

В vala есть монады.

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