You are viewing ru_lambda

Лямбда - функциональное программирование - Монады как контейнеры (перевод) [entries|archive|friends|userinfo]
Лямбда - функциональное программирование

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Монады как контейнеры (перевод) [Feb. 1st, 2006|05:39 pm]
Previous Entry Add to Memories Share Next Entry

ru_lambda

[lomeo]
[Tags|, ]

Это перевод статьи CaleGibbard

Перевод окончен.

Если у кого то есть какие то замечания - огромная просьба тут же их и высказывать. Спасибо!


Огромное спасибо polter , vanja_y , zhuzh !




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

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

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

Обычно Haskell использует пару функций, называющихся return и bind (>>=), но иногда проще рассмотреть map (fmap), return и join, т.к. они легче для понимания. Позже мы определим bind в терминах этих функций.

Первая из этой тройки обычно называемая map, (но под именем fmap в Haskell 98) на самом деле следует из определения функтора. Мы можем думать о функторе, как о типе контейнера, в котором мы можем применить единую функцию к каждому объекту.

То есть, если f - функтор, и мы имеем функцию типа (a -> b), и контейнер типа (f a), то мы можем получить новый контейнер типа (f b).

Это ясно из типа fmap:
fmap :: (Functor f) => (a -> b) -> f a -> f b

Если вы дадите мне ягоду голубики за каждое яблоко, которое я дам вам (a -> b), и у меня есть коробка яблок (f a), значит я получу коробку с голубикой (f b).

Каждая монада является функтором.

Второй метод, return, специфичен для монад. Если m - монада, тогда return принимает элемент типа a, и возвращает контейнер типа (m a) с этим элементом в нём. Таким образом, её тип в Haskell
return :: (Monad m) => a -> m a

Если у меня есть яблоко (a) , то я могу положить его в коробку (m a).

Третий метод, join, также специфичный для монад, принимает контейнер контейнеров m (m a), и комбинирует их в один m a каким-то осмысленным образом. Её тип в Haskell
join :: (Monad m) => m (m a) -> m a

Если у меня есть коробка коробок яблок (m (m a)) , то я могу взять яблоки из каждой, и положить их в новую коробку (m a).

Используя эти методы, мы можем сконструировать важную операцию, называющуюся bind или extend, которая обычно обозначается символом (>>=). Когда вы определяете свою собственную монаду в Haskell, предполагается, что вы определите только return и bind. Оказывается, что маппинг и джойнинг бесплатны из-за этой парочки. Несмотря на то, что только return и bind необходимы для определения монады, обычно проще сначала подумать о map, return и join, и затем получить bind из них, так как map и join в общем проще, чем bind.

Функция bind берёт контейнер типа (m a) и функцию типа (a -> m b). Сначала она отображает функцию на контейнер, (что даст нам m (m b)) и затем применяет join, возвращая контейнер типа (m b). Её тип и определение в Haskell
(>>=) :: (Monad m) => m a -> (a -> m b) -> m b
xs >>= f = join (fmap f xs)
  -- какой бы была bind (>>=) в Haskell, если бы join и fmap были выбраны в качестве первичных

Если у меня есть коробка яблок (m a) и для каждого яблока, вы дадите мне коробку голубики (a -> m b) тогда я смогу получить коробку со всеми ягодами голубики (m b).

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

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

Список - наиболее подходящий, простой и иллюстративный пример. Здесь, fmap - это просто обычный map, return - простой (\x -> [x]), а join - concat.
instance Monad [] where
    return :: a -> [a]
    return x = [x] -- создает список, содержащий этот единственный элемент

    (>>=) :: [a] -> (a -> [b]) -> [b]
    xs >>= f = concat (map f xs)
        -- собирает все результаты f (которые есть списки)
        -- и комбинирует их в новый список


Монада списка, в некотором смысле, моделирует вычисления, которые могут вернуть произвольное количество значений. Bind вкладывает значения, и собирает результаты всех значений. Подобные вычисления известны в computer science как недетерминированные. То есть список [x,y,z] представляет собой значение, которое является всеми значениями x, y и z одновременно.

Пара примеров, использующих это определение bind:
[10,20,30] >>= \x -> [x, x+1]
   -- функция, принимающая число и возвращающая одновременно его и следующее за ним.
= [10,11,20,21,30,31]

[10,20,30] >>= \x -> [x, x+1] >>= \y -> if y > 20 then [] else [y,y]
= [10,10,11,11,20,20]

И простой фрактал, использующий тот факт, что списки упорядочены:
f x | x == '#'  = "# #"
    | otherwise = "   "

"#" >>= f >>= f >>= f >>= f
= "# #   # #         # #   # #                           # #   # #         # #   # #"

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

Можно спросить - как, имея только bind и return, мы можем вернуться к map и join.

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

Функция, которая делает это для люой монады в Haskell называется liftM -- она может быть описана в терминах return и bind следующим образом:
liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f xs = xs >>= (return . f)
-- берем контейнер, заполненный a-элементами, к каждому применяем f,
-- кладем результат типа b в новый контейнер,
-- и затем объединяем (join) все контейнеры вместе.

Объединение эквивалентно связыванию контейнера с тождественным отображением. Оно на самом деле называется join в Haskell:
join :: (Monad m) => m (m a) -> m a
join xss = xss >>= id

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

Заметьте, что в дальнейшем синтаксис подчеркивает тот факт, что списочная монада моделирует недетерминизм: о коде y <- xs можно думать, как о y, берущем все значения списка xs единовременно.

Представленное выше (возможно немного глупое) списочное вычисление может быть описано как:
do x <- [10,20,30]
   [x, x+1]

и,
do x <- [10,20,30]
   y <- [x, x+1]
   if y > 20 then [] else [y,y]

Код для liftM может быть описан как:
liftM f xs = do a <- xs
                return (f a)



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

Хорошее упражнение - сообразить, как определить bind и return (или fmap, join и return), для описания следующей монады "дерево". Просто помните, что именно, как предолагается, они должны делать.
data Tree a = Leaf a | Branch (Tree a) (Tree a)

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


Вопрос, который люди чаще всего задают в этом месте это "Какой отношение всё это имеет к IO?"

Ну, в Haskell IO является монадой. Как она соотносится с понятием контейнера?

Рассмотрим getChar :: IO Char -- это IO контейнер с символьным значением внутри. Конкретный символ, который контейнер содержит, определяется тогда, когда программа срабатывает в зависимости от того, какие клавиши нажал пользователь. Попытка получить символ из контейнера приводит к побочному эффекту: программа приостанавливается и ожидает нажатия клавиши пользователем. Это в общем верно для значений IO - при получении значений с помощью bind, происходит побочный эффект. Множество IO контейнеров на самом деле не содержат интересующие нас значения. Например,
putStrLn "Hello, World!":: IO ()

То есть значение, возвращаемое putStrLn "Hello, World!" - это IO контейнер, заполненный значением типа (), не такой уж интересный тип. Однако, когда вы получаете это значение при операции bind, строка Hello, World! печатается на экране. Таким образом, другой способ думать о значениях типа IO t - это думать о них, как о вычислениях, которые при исполнении вызывают побочный эффект перед возвратом значения типа t.

Еще одно, что вы также могли бы заметить - в Haskell нет обычных функций, которые вы могли бы вызвать (по меньшей мере в стандартном Haskell) для получения значения из IO контейнера/вычисления, иначе, чем в bind, который кладет его обратно. Подобный тип функции IO a -> a мог бы быть очень небезопасным в мире чистого Haskell, потому что производимое значение могло бы отличаться каждый раз, когда его вызывают, и IO вычисление могло бы иметь побочный эффект, не было бы способа управлять временем его выполнения (Haskell ленив как-никак). НУ так, как же IO акции всё же исполняются? IO акция, называющаяся main, запускается при исполнении программы. Она может использовать другие IO акции в процессе, и всё начинается с неё.

При исполнении IO есть специальная удобная форма bind, когда вы просто желаете вызвать побочный эффект и не интересуетесь значениями, возвращаемыми контейнером налево:
(>>) :: Monad m => m a -> m b -> m b
m >> k  =  m >>= \_ -> k

Пример IO в do нотации:
main = do putStrLn "Hello, what is your name?"
          name <- getLine
          putStrLn ("Hello " ++ name ++ "!")

или, в терминах bind, использование специальной формы:
main = putStrLn "Hello, what is your name?" >>
       getLine >>= \name ->
       putStrLn ("Hello " ++ name ++ "!")

или, очень примитивно, без специальной формы для bind:
main = putStrLn "Hello, what is your name?" >>= \x ->
       getLine >>= \name ->
       putStrLn ("Hello " ++ name ++ "!")



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

Монада Reader можелирует вычисления, которые читают из (зависят от) совместно используемого окружения. Для установления соответствия тип окружения принимается за тип индекса в нашем проиндексированном контейнере.
type Reader e = (->) e -- наша монада

Return просто напросто порождает контейнер, имеющий данное значение в каждом слоте.
return :: a -> (Reader e a)
return x = (\k -> x)

Отображение функции на такой контейнер делает то же самое, что и композиция.
fmap :: (a -> b) -> Reader e a -> Reader e b
      = (a -> b) -> (e -> a) -> (e -> b)
        -- согласно определению (Reader a b) = (a -> b)

fmap f xs = f . xs

Как насчёт join? Ну, давайте взглянем на типы.
join :: (Reader e) (Reader e a) -> (Reader e a)
      = (e -> e -> a) -> (e -> a) -- согласно определению (Reader a)

Есть только одна вещь, которую функция типа (e -> a) могла бы на самом деле делать:
join xss = (\k -> xss k k)

С точки зрения контейнера, мы берем индексируемый контейнер индексируемых контейнеров и создаем новый, который по индексу k имеет значение, находящееся по индексу k в контейнере по индексу k.

Также мы можем установить, что на основании этого должен делать bind:
(>>=) :: (Reader e a) -> (a -> Reader e b) -> (Reader e b)
       = (e -> a) -> (a -> (e -> b)) -> (e -> b)  -- согласно определению

xs >>= f = join (fmap f xs)
         = join (f . xs)
         = (\k -> (f . xs) k k)
         = (\k -> f (xs k) k)

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

Обзор Монады как вычисления, возможно, более очевидно объясняет цель подобной монады: bind берёт вычисление, которое может читать из окружения перед созданием значения типа a, и функцию, преобразующую значения типа a в вычисления, которые могут читать из окружения перед возвращением результата типа b, и объединяет их вместе, чтобы получить вычисление, которое может читать из (совместно используемого) окружения перед возвращением значения типа b.


Ну, а что насчёт State монады? Несмотря на то, что, я признаюсь, для State и IO в частности более естественно придерживаться мнения Монад как вычислений, неплохо увидеть, что аналогия с контейнерами также успешна. State монада - это особенная отделка монады Reader, рассмотренной ранее.

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

По аналогии значение типа (State s a) - это как контейнер, индексированный значениями типа s и для каждого индекса имеющий значение типа a и другого, нового значения типа s. Функция runState как раз осуществляет этот поиск.
newtype State s a = State { runState :: (s -> (a,s)) }

Что же делает return? Он возвращает State-контейнер с данным элементым на каждом индексе и с неизменным "адресом" (параметром состояния).
return :: a -> State s a
return x = State (\s -> (x,s))

Отображение естественно - применение функции к каждому значению типа a на всём протяжении структуры.
fmap :: (a -> b) -> (State s a) -> (State s b)
fmap f (State m) = State (onVal f . m)
    where onVal f (x, s) = (f x, s)

Join требует чуть больше мыслительной деятельности. Мы хотим взять значение типа (State s (State s a)) и естественно преобразовать его в (State s a). Это важное устранение косвенности. Мы берём новый адрес и новую коробку, которую мы получили поиском по данному адресу в коробке, и делаем ещё один поиск - заметьте, что это почти то же самое, что мы делали с Reader монадой, только мы используем новый адрес, который мы получили при поиске, вместо того же адреса, что и для первого поиска.

Итак, получаем
join :: (State s (State s a)) -> (State s a)
join xss = State (\s -> uncurry runState (runState xss s))



Надеюсь, что написанное выше является достаточно ясным введением в монады. Не стесняйтесь высказывать свои комментарии и задавать вопросы.

CaleGibbard
linkReply

Comments:
[User Picture]From: dluciv
2006-02-01 03:38 pm (UTC)

Сорри за оффтоп

(Link)

Благородный и нужный обществу труд.
Искренне спасибо :)

А раз пошли такие штуки, может где-нибудь написано доходчиво, как монады комбинировать? Например, [], IO, и - о ужас! - State. Я сам в данное время изучаю хаскель и как раз сижу в этом месте, и оно у меня производит впечатление довольно загрузного.
[User Picture]From: lomeo
2006-02-01 03:51 pm (UTC)

Re: Сорри за оффтоп

(Link)

для этого есть трансформеры монад.
Для начала отсюда http://www.haskell.org/hawiki/MonadTransformers.
А дальше больше :)
[User Picture]From: dimrub
2006-02-01 03:49 pm (UTC)

(Link)

Отлично, как раз пытаюсь с монадами разобраться, а тут, я вижу, с примерами и на доступном уровне.
[User Picture]From: lomeo
2006-02-01 04:04 pm (UTC)

(Link)

Я грокал монады так

1. Прочитал Monads for functional programming. Ничего не понял.
2. Прочитал All about Monads. Тут уже понял чуть больше, но только первую часть. Тщательно позапускал все примеры - увидел, что они работают, как - не понял.
3. Прочитал супер вещь, после которой у меня в голове более менее все начала становится на место: The Haskell Programmer's Guide to the IO Monad
4. Брал каждую монаду начиная с Identity (да да :-)) и дальше - [], Maybe, State, (->) и применял к ним функции из модуля Monad, чтобы посмотреть, что получится и где это можно использовать. Для каждой из этой монады есть отдельный API, как например функции put/get для State или fromMaybe/isJust для Maybe, однако они не так важны для понимания, что такое монада вообще, хотя конкретную монаду проясняет, да.
5. Только после этого, когда в голове уже более менее все встало на свои места, стал смотреть do-нотацию :-)
6. Перечитал все верхние книги. До сих многое неясно ;-)

Надеюсь, кому нибудь мой способ окажется полезным.


[User Picture]From: jedal
2006-02-03 06:43 pm (UTC)

(Link)

О, начал читать "All about Monads" — все проясняется, кажется. Спасибо за ссылку.
[User Picture]From: vanja_y
2006-02-01 04:23 pm (UTC)

(Link)

"в некоторой осмысленной манере (?in some sensible fashion)"
некоторым разумным образом

"(?identity map)"
тождественное отображение

оЧепятка:"Используя эти методы, мы сожем сконструировать важную операцию,"
[User Picture]From: lomeo
2006-02-01 06:48 pm (UTC)

(Link)

Спасибо!
From: ex_ex_zhuzh
2006-02-01 04:24 pm (UTC)

(Link)

in some sensible fashion каким-то осмысленным образом
произвольное
identity map тождественное отображение
[User Picture]From: lomeo
2006-02-01 06:48 pm (UTC)

(Link)

Спасибо!
[User Picture]From: _darkus_
2007-03-03 02:04 pm (UTC)

(Link)

А почему эту статью на Викиучебник не закинуть? Думаю, там она очень помогла бы...
[User Picture]From: lomeo
2007-03-04 12:09 pm (UTC)

(Link)

Закинь, я, честно говоря не очень все эти оформительские работы люблю :-(
[User Picture]From: _darkus_
2007-03-04 12:51 pm (UTC)

(Link)

Экий хитрый... Будет время, закину...
From: four_atan_one
2007-07-21 05:37 pm (UTC)

update the link to monad laws

(Link)

You have a broken link to nomaware -- try this instead:

http://www.haskell.org/haskellwiki/Monad_laws

I changed it on the haskellwiki just now (you should also set yourself to watch for changes in the page, if you haven't, so you'll get notifications about updates. I apologize if I'm telling you to do something you've already done :).

[User Picture]From: lomeo
2007-08-25 03:04 am (UTC)

Re: update the link to monad laws

(Link)

done. thx!
From: (Anonymous)
2007-08-24 02:49 am (UTC)

(Link)

Спасибо за статью, перевод очень хороший!
Но ссылки битые. Почти все.
[User Picture]From: lomeo
2007-08-25 03:05 am (UTC)

(Link)

Спасибо, поправил те, что увидел
From: ex_chrobin
2008-01-16 03:05 pm (UTC)

(Link)

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

ps blueberry обычно черника вроде, в бытовом употреблении
[User Picture]From: lomeo
2008-01-16 03:13 pm (UTC)

(Link)

Спасибо!

На самом деле, можно было пойти с самого начала: http://www.haskell.org/haskellwiki/Monads_as_containers
Там есть линк на эту страничку сразу под заголовком.

Насчёт черники ничего не скажу, я так хорошо английский не знаю :-)
From: ex_chrobin
2008-01-16 03:19 pm (UTC)

(Link)

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

блуберри маффин на вкус точно с черникой :)
[User Picture]From: lomeo
2008-01-16 03:43 pm (UTC)

(Link)

Понятно.

Вот в ботанике я тоже как то не очень. Уж голубику от черники точно не отличу :(