Посмотри на странице с 3. Monads.

Можно так сформулировать — для функтора m есть стрелки f : a -> m b и g : b -> m c, так что попытка сделать fmap g . f даст a -> m^2 c, что есть 1) возможная data dependency между результатом(-ами) f и аргументом(-ами) g, то есть необходимость в sequencing вычислений с «эффектами» чисто на уровне этой зависимости (а получение b может быть связанно с «эффектами» данного типа/вычисления), 2) не a -> m^1 c исходного вида, что с точки зрения композиционности ставит вопрос о возможности введения join и Kleisli категории (с (<=<) для (.)).

Для примера, частичность:

(+1) <$> 30 `safeDiv` 3
Just 11

(`safeDiv` 2) <$> 30 `safeDiv` 3
Just (Just 5)

((`safeDiv` 2) <=< (`safeDiv` 3)) 30
Just 5

многозначность:

(+1) <$> [1, 2, 3]
[2,3,4]

const [1, 2, 3] <$> [1, 2, 3]
[[1,2,3],[1,2,3],[1,2,3]]

(const [1, 2, 3] <=< const [1, 2, 3]) ()
[1,2,3,1,2,3,1,2,3]

identity: Kleisli -> (->) и (<=<) -> (.).

Т.е. видно наличие цепочки (в смысле зависимости данных!) и в чистом коде и в любой монаде, т.к. f . g != g . f, как в (->), так и в Kleisli.

Параллельность никак не спасает от того, что в g . f g ждёт результата f, а при переходе от (->) к Kleisli (<=<) та же композиция, g так же ждёт, да и ещё и extra stuff случается ассоциированный с монадой. Параллельность спасёт ровно тогда, когда вместо (>>=)/(>=>)/join будет (>>)/(*>), то есть независимость вида (\_ -> g) . f :)

Там используется 'return wtf', в общем то ИО в хацкеле достаточно ленив, чтобы было тоже самое (если мы про пример с undefined), что уже не прокатит с эффектами как выше.так что инчтанс написанный на Haskell меня бы убедил.

Я тебе привел пример который:

1. Оставляет последовательность вычилсений незаданной

2. строго требует монад, то есть аппликативом невыразим. Это то что ты требовал.

Очевидно что написать на хаскел такой пример нельзя - потому что на хаскеле вообще нельзя написать реализация ИО монады.

С другой стороны такие монады как identity и reader желаемыми мне свойствами не обладают. В принципе можно ослабить моё утверждение и ввести смешные определения чтобы уточнить мою т.з., но большого смысла в этом нет.

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

Если Mem это вся физическая память

Во-первых не mem, а world, то есть копировать надо не память а всю вселенную. Во-вторых, даже если брать память - куда ты будешь ее копировать? Это же _вся_ память. Значит, свободного места нет.

то копировать нечего, Mem ~ (), если это страница / массив / ссылка, то передаём адрес, Mem ~ Addr (разумеется, операции put/get используют строгие unpure примитивы работы с памятью (соответствующие вполне стандартизированные для данной машины инструкции, например), один фиг оно за монадой будет скрыто, в чём весь трюк — в GHC работая с IO напрямую тоже можно вся чистоту сломать).

Еще раз - ты не имеешь права копировать старую память, передавать ссылки и т.п. Ты должен именно скопировать всю память, куда-то. Такова семнатика. Вопрос - куда?

Ну и, да, на самом деле это не память а вся вселенная. Каким образом ты собрался создавать новую копию вселенной? Пока не опишешь этот процесс - не защитано.

Похоже, quasimoto вернулся и он уже не quasi.

Во-первых не mem, а world

DMA, не?

куда ты будешь ее копировать?

Я написал:

копировать нечего

Никуда, копирование и вселенные ты сам придумал, никто так не делает (RealWorld у GHC это типа шютка, как BLACKHOLE) — есть у тебя доступ к памяти как к устройству, вот и меняй её грязными инструкциями под монадой (процессор будет выполнять их, помимо обычной редукции).

http://www.haskell.org/ghc/docs/7.4.2/html/libraries/ghc-prim-0.2.0.0/GHC-Pri...

We never manipulate values of type RealWorld; it's only used in the type system, to parameterise State#.

http://ogi.altocumulus.org/~hallgren/ICFP2005/house.pdf

We have implemented the H interface directly on top of real IA32

hardware

Монады возникают ровным счётом при правильной возможности композиций a -> m b, так что вопрос последовательности (но не стратегии) имеет смысл настолько, насколько он его имеет для функций {f, g, h} в h . g . f, как для тех же чистых вычислений, так и для ассоциированных с типом эффектов — можно взять только их, в () -> State Set (), например, всё что может происходить это эффекты по изменению состояния (в отличии от () -> Identity (), где нечему происходить), их последовательность в общем случае играет роль и фиксирована порядком применения. Проще говоря, если месить память или её эквивалент в do-нотации, то вне зависимости от стратегии операции изменения памяти (будучи некоммутативными) имеют вполне ясную последовательность (опуская проблемы останова и т.п.) которую нельзя менять в общем случае.

Похоже, quasimoto вернулся и он уже не quasi.

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

Но он, кстати, более понятно стал писать, не такая жёсткая шизофазийная шелуха, как раньше.

он, кстати, более понятно стал писать, не такая жёсткая шизофазийная шелуха, как раньше.

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

BTW, я придумал для qnikst достойный пример, который точно нельзя записать с помощью Applicative:

f :: Monad m => a -> m ()
f _ = return ()

Пруф, что формализма Applicative тут недостаточно, думаю, очевиден: см. сигнатуру.

В ответ на возражение: «а теперь придумай невырожденный пример» я отвечу:

1) define невырожденный

2) в изначальном утверждении ни про какое вырождение ничего сказано не было.

не надоело уже 7уй страницу приводить один и тот же пример?

про последовательнсти whnf и прочих друзей:

import Control.Applicative

import Debug.Trace

newtype I a = I {unI ::a}

instance Functor I where
  fmap f = trace "functor" . I . f . unI 

instance Applicative I where
  pure = trace "pure" . I
  f <*> g = trace "<*>" $ I $ (unI f) (unI g)

instance Monad I where
  return = pure
  m >>= g = trace ">>=" $ g (unI m)

*Main> unI (return 5 >> return 3)
>>=
pure
3

Не надоело тупить уже восьмую страницу?

Предлагаю каждый раз, когда пример сводится к >>= const . , или fmap, или *>, или попытке высказать тривиальное утверждение не нажимать кнопку «отправить».

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

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

Мой пример не сводится к >>= const . , или fmap, или *>. Ответь пожалуйста по нему.

Предложение отклонено.

Поскольку ты не знаешь, что лежит внутри произвольной функции — const или нет, утверждение нетривиально.

кстати оттуда же про sequencing

Coherency The operations for monads have a variety of equali- ties which must hold, known as the identity and associativity laws. We do not repeat those laws here, rather we convey their significance. Consider the expression (((64 ÷ x) ÷ y) ÷ z) + 5. This is essentially five computations sequenced together: 64, λv.v ÷ x, λv.v ÷ y, λv.v ÷ z, and λv.v + 5. Using the structures above we can sequence these computations (maintaining order) in a variety of ways depending on how we combine consecutive pairs and whether we turn pure computations into effectful computations or simply use functorial structure to propagate effects through them, but the result should be the same no matter which way is used. We call this concept semantic coherency, and the monad laws are necessary and sufficient to ensure this for sequential composition.

так что если я хочу говорить про sequencing то должен это делать с точнотью до semantic coherency, который позволяет вносить «непоследовательность» тогда, когда выполняются законы.

я бы с удовольствием ответил, если бы у меня был код, который я могу запускать и что-то с ним делать, т.к. компилировать в уме ракетку я не умею, но т.к. у меня руки растут из задницы, то запустить твой пример я не смог. Поэтому предложил сделать пример на нём. Подозреваю, что сделав newtype LIO a = LIO { unLIO :: IO () } или сделав foreign import ccall "function_you_want_to_show_me" :: a (т.е. якобы чистую) ты сможешь выразить свою идею, ну или сказав какие кнопки мне жать чтобы имея dev-scheme/racket-6.0.1 запустить твой пример.

ну.. в этом примере ничего кроме *> pure (), или fmap (const ()) или const $ return (), что является одним и тем же, там лежать не может (см. типы).

О господи, дай мне терпения.

Есть произвольная функция типа Monad m => a -> m b. Её тела мы не видим. Как ты поймёшь, действительно ли она зависит от своего аргумента или нет? Hint: никак. Даже если спуститься на value-level.

ну.. в этом примере ничего кроме *> pure (), или fmap (const ()) или const $ return (), что является одним и тем же, там лежать не может

Ну давай сузим общность до Monad m => a -> m a. Вот здесь, по крайней мере, может лежать return, а может const undefined.

хочу заметить, что в теле поста у тебя был тип Monad m => a -> m (), впрочем про я был не прав про угадывание, т.к. в классе Monad есть операция fail, а ещё есть bottom, если бы их не было, то я бы с уверенностью могу сказать, что функция от аргумента не зависит.

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

Монады служат для sequencing effectfull computations, если кто не согласен, то можете кидать ссылки на статьи подтверждающие вашу точку зрения, точка. Пока работы Moggi, Wandler, SPJ, Tate подтверждают мою точку зрения, врочем высказанную достаточно криво.

Для любой монады есть Kleisli категория с композицией (<=<) которая не коммутирует, так как есть не коммутирующие функции (просто чистые под монадой), максимум можно показать, что есть монады в которых коммутируют именно побочные эффекты — identity (нет эффектов), maybe (добавление Nothing в любом месте даёт Nothing для всей последовательности), иначе нам важна последовательность эффектов на уровне порядка применений в (<=<) / кода do-нотации, State и его производные (то же IO) тут примеры.

хочу заметить, что в теле поста у тебя был тип Monad m => a -> m ()

С тем же успехом там мог быть Float -> IO Int. Я думал, что настолько разжёвывать не придётся.

Монады служат для sequencing effectfull computations

Душкина меньше читайте на ночь.

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

PROOFS?
R
O
O
F
S
?

Сперва докажите, что чайника Рассела не существует, а потом я начну искать пруфлинки про невыполнение какого-то свойства.

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

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

Зачем тебе код, не понимаю? Еще раз, рассматриваем бинд, который выполняет действия параллельно. Это будет монадический бинд, его можно реализовать, он невыразим через аппликатив. Чем тебя не устраивает такой пример?

ну или сказав какие кнопки мне жать чтобы имея dev-scheme/racket-6.0.1 запустить твой пример.

Gросто берешь и запускаешь, он работает, ничего дополнительно жать не надо. Если ты утверждаешь, что не работает - значит ты просто врешь.

pasterack тебе в помощ

http://pasterack.org/pastes/12444

Монады служат для sequencing effectfull computations

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

Это строгий вариант, чтобы был нестрогий - надо убрать форс в бинде.

я бы с уверенностью могу сказать, что функция от аргумента не зависит

Как я писал выше — мы можем взять () -> m (), где нет чистых вычислений, только эффекты («effectfull» в широком смысле — ок), и посмотреть — всегда ли имеет значение порядок «sequencing». Берём () -> State Set () как элемент S_n — порядок имеет значение, ST/IO/STM — очевидно. Берём Identity и Maybe (но не Either, например) — не имеет.

Дык я не спорю.

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

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

мы можем взять () -> m ()

!

Т.е. () -> Maybe () — цепочка из const $ Just () это всегда const $ Just (), наличие хоть одного const Nothing это всегда const Nothing в результате, порядок _только_ эффектов без вычислений под монадой не имеет значения. В случае Either это не так (Left бывает разный — должны получить первый), как и в случае большинства других более сложных монад.

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

Т.е., есть утверждение f <=< g != g <=< f, что мы можем сказать:

1) в Kleisli любой монады _существуют_ стрелки для которых как f <=< g != g <=< f, так и f <=< g == g <=< f.

2) в подкатегории () -> m () может быть f <=< g == g <=< f _для всех_ стрелок (некоторой _существующей_ монады), иначе — см. 1).

ST/IO/STM — очевидно.

Так можно взять ИО в котором не будет иметь значения.

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

Ну так вот:

let f = (printLn "yo!") >> readLn
let g x = (printLn "ya!") >> (printLn x)
main = f >>= g x

puts «1» >> puts «2» — я хочу увидеть именно 1\n2\n :)

Или puts =<< (+1) <$> geti — сначала напечатаем ответ, а потом прочитаем вопрос?

Или return 0 >> return 0 >> return 0 — не имеет, чё.

http://en.wikipedia.org/wiki/Sequence_point

puts «1» >> puts «2» — я хочу увидеть именно 1\n2\n :)

Да, но я могу реализовать бинд так, что оно выведет 2\n1\n. Или вообще будет выводить как повезет. И этот бинд - будет корректным монадическим биндом, то есть сам факт того что я засунул эффекты в монады не заставляет меня делать монаду так, чтобы эти эффекты были каким=то определенным образом упорядочены. А значит монада сама по себе не содержит «концепции» упорядочивания эффектов. Так же как аппликатив ее не содержит - можно написать аппликатив который упорядочивает, можно - который не упорядочивает.

Это ты к чему? Тут qnlist утверждает что если у тебя есть вычисления f и g x, то вычисление f >>= g x необходимо совершит эффекты g x после эффектов f, если g x зависит от f. Я привел контрпример.

ай-ай-ай, разные контексты.

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

в примере было Monad m => a -> m () и именно об этой сигнатуре я и говорил, во-первых она говорит о том, что эта функция работает для любой монады, т.е. в отношении эффектов мы можем говорить только о функциях предоставляемых этими классами типов, во-вторых тут есть полиморфный тип a, т.е. функция работает для любого типа подставленного «пользователем», это значит, что данная функция никак не зависит от передаваемого значения, итого у нас есть 2 варианта:

1. fmap (const ()), *> (pure ())[/inlne], const (return ()) — т.е. мы не используем значение и возвращаем ()

2. fail "foo" — использование неожиданной функции в монаде

3. error "foo", undefined, или функция не детерминируется, типа foo = foo.

Если рассматривать второй предложенный вариант Monad m => a -> m b, то первый вариант отпадает, и остается только fail и _|_.

Но это все оффтоп по сравнению с тем, что затронуто в треде.

у меня не получилось...

instance Monad L where
   return = pure
   m >>= g = L $ do m' <- unsafeInterleaveIO $ unL m
                    unL $ g m'

lputStrLn  :: String -> L ()
lputStrLn = L . putStrLn

lprint :: Show a => a -> L ()
lprint = L . print

lreadLnInt :: L Int
lreadLnInt = L readLn


test1 :: L Int
test1 = lputStrLn "hi" >> lreadLnInt

test2 :: Int -> L ()
test2 x = lputStrLn "yo!" >> lprint x

в итоге «hi» и «yo!» вообще не вывелось, а чо от них же ничего не зависит..

Ок, если всё форкать, то это тогда не IO/ST/STM где важны SP, а Async — в ней сами по себе эффекты коммутируют (f <=< g == g <=< f для () -> Async ()), но с примешанными вычислениями уже нет (f <=< g != g <=< f для некоторых f и g), да и если правая часть bind-а повиснет на промисе (то есть использует его, то есть когда (>>=) честный, а не (>>)), то она всегда дождётся завершения левой.

Что касается концепции порядка — есть композиция (именно у монад, у аппликатива нет), так что порядок есть — h . g . f, даже если он где-то может иногда не играть роль, или всегда не играть роль :)

у меня не получилось...

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

в итоге «hi» и «yo!» вообще не вывелось

То есть ты реализовал корректный бинд, который не задает последовательность эффектов.

а чо от них же ничего не зависит..

А при чем тут они? в f >>= g x у тебя уже нету отдельных вычислений для вывода, у тебя есть вычисление f и вычисление g x. Далее:

1. g x очевидно зависит от f

2. значит (по-твоему) соответствующая монада должна выполянть эффекты g x строго после f

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

Может, конечно, ты имел ввиду что «упорядочиваются» только зависимые эффекты, но тогда твое утверждение самоочевидно. Никак нельзя выполнить эффект Х до эффекта Y, если Y зависит от результата Х - но монады тут не причем, так устроена наша вселенная. Причинно-следственные связи и все такое.

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

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

Ок, если всё форкать, то это тогда не IO/ST/STM где важны SP, а Async

Это не важно, важно, что это вариант ИО-монады :)

Что касается концепции порядка — есть композиция (именно у монад, у аппликатива нет), так что порядок есть — h . g . f, даже если он где-то может иногда не играть роль, или всегда не играть роль :)

У аппликатива тоже есть, точно такая же :)

в примере было Monad m => a -> m ()

Не образующие подкатегорию, например (если не a ~ ()), а то я через композицию определяю, тогда по аналогии — берём теорию групп, что можно сказать в общем случае про значение порядка операций? В частном абелевом случае? Вот с монадами так же.

У аппликатива тоже есть, точно такая же :)

join и bind определяются через эту композицию.

кстати, ты не смотрел связи Effectors из данной статьи и extensible-effects, т.к. похоже, что много общих идей разделяется?

Я не вижу конкретной связи, разве что первое предполагает возможность пойти по пути похожему на путь второго, то есть когда в conclusion говорится про композиции монад — существование трансформеров (на основе layered) и возможность альтернативно им строить сумму монад как монаду. Вот в extensible effects у нас одна монада Eff которая суммирует хоть и не монады, но их значения в одну большую суммы, так что потом разные эффекты спокойно пишутся без lift, альтернатива mtl c готовым кодом, а в первой статье не объясняется как строить продукторы и их композиции, вместо этого моноидальные эффекты с монадической семантикой обобщаются чтобы описать много разных систем эффектов (в т.ч. монадических). http://www.informatik.uni-bremen.de/~cxl/papers/icfp02.pdf (общее цитирование), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4131 (cat :: FilePath → Term (Teletype :+: FileSystem) () без lift-а, ок? разве что интерпретатор и с подтипированием возиться).