Why are monads not closed under composition?Applicatives compose, monads don'tComposing Monads v. Applicative FunctorsWhat is a monad?Prefer composition over inheritance?A monad is just a monoid in the category of endofunctors, what's the problem?What are Haskell's monad transformers in categorical terms?Relationship between Functor, Applicative Functor, and MonadMonad Transformers vs Passing parameters to functionsConcrete example showing that monads are not closed under composition (with proof)?Why do we need monads?Composing Monads v. Applicative FunctorsWhy are monad transformers different to stacking monads?
Balance Issues for a Custom Sorcerer Variant
How does buying out courses with grant money work?
How to write papers efficiently when English isn't my first language?
What Brexit proposals are on the table in the indicative votes on the 27th of March 2019?
Do all network devices need to make routing decisions, regardless of communication across networks or within a network?
How do we know the LHC results are robust?
What is the opposite of 'gravitas'?
How to Reset Passwords on Multiple Websites Easily?
Is a stroke of luck acceptable after a series of unfavorable events?
How did Arya survive the stabbing?
Failed to fetch jessie backports repository
What is the difference between "behavior" and "behaviour"?
For a non-Jew, is there a punishment for not observing the 7 Noahide Laws?
Detecting if an element is found inside a container
How does Loki do this?
Proof of work - lottery approach
What does the word "Atten" mean?
CREATE opcode: what does it really do?
Closest Prime Number
Trouble understanding the speech of overseas colleagues
Large drywall patch supports
Term for the "extreme-extension" version of a straw man fallacy?
Two monoidal structures and copowering
Type int? vs type int
Why are monads not closed under composition?
Applicatives compose, monads don'tComposing Monads v. Applicative FunctorsWhat is a monad?Prefer composition over inheritance?A monad is just a monoid in the category of endofunctors, what's the problem?What are Haskell's monad transformers in categorical terms?Relationship between Functor, Applicative Functor, and MonadMonad Transformers vs Passing parameters to functionsConcrete example showing that monads are not closed under composition (with proof)?Why do we need monads?Composing Monads v. Applicative FunctorsWhy are monad transformers different to stacking monads?
While I was learning Composing Types chapter from Haskell Book, I was given tasks to write Functor and Applicative instances for the following type.
newtype Compose f g a = Compose getCompose :: f (g a)
I wrote the following definitions
Functor:
fmap f (Compose fga) = Compose $ (fmap . fmap) f fga
Applicative:
(Compose f) <*> (Compose a) = Compose $ (<*>) <$> f <*> a
I learned that composing two Functors or Applicatives gives Functor and Applicative respectively.
The author also explained it is not possible to compose two Monads the same way. So we use Monad Transformers. I just do not want to read Monad Transformers unless I'm clear with why Monads do not compose.
So far I tried to write bind function like this:
Monad:
(>>=) :: Compose f g a -> (a -> Compose f g b) -> Compose f g b
(Compose fga) >>= h = (fmap.fmap) h fga
and of course got this error from GHC
Expected type: Compose f g b
Actual type: f (g (Compose f g b))
If I can strip the outermost f g somehow, the composition gives us a monad right? (I still couldn't figure out how to strip that though)
I tried reading answers from other Stack Overflow questions like this, but all answers are more theoretical or some Math. I still haven't learned why Monads do not compose. Can somebody explain me without using Math?
haskell monads composition monad-transformers
asked Mar 7 at 12:53
Nirvin MNirvin M
603
add a comment |
While I was learning Composing Types chapter from Haskell Book, I was given tasks to write Functor and Applicative instances for the following type.
newtype Compose f g a = Compose getCompose :: f (g a)
I wrote the following definitions
Functor:
fmap f (Compose fga) = Compose $ (fmap . fmap) f fga
Applicative:
(Compose f) <*> (Compose a) = Compose $ (<*>) <$> f <*> a
I learned that composing two Functors or Applicatives gives Functor and Applicative respectively.
The author also explained it is not possible to compose two Monads the same way. So we use Monad Transformers. I just do not want to read Monad Transformers unless I'm clear with why Monads do not compose.
So far I tried to write bind function like this:
Monad:
(>>=) :: Compose f g a -> (a -> Compose f g b) -> Compose f g b
(Compose fga) >>= h = (fmap.fmap) h fga
and of course got this error from GHC
Expected type: Compose f g b
Actual type: f (g (Compose f g b))
If I can strip the outermost f g somehow, the composition gives us a monad right? (I still couldn't figure out how to strip that though)
I tried reading answers from other Stack Overflow questions like this, but all answers are more theoretical or some Math. I still haven't learned why Monads do not compose. Can somebody explain me without using Math?
haskell monads composition monad-transformers
asked Mar 7 at 12:53
Nirvin MNirvin M
603
2
@RobinZigmond But given that a monad is a functor, something about the extra structure in a monad "breaks" composition. I think that's what the OP is looking for, what that "something" is.
– chepner
Mar 7 at 13:48
@NirvinM - not sure why you think I'm being "mean". I'm just trying to understand what you need by way of further explanation. (Not that I'm necessarily able to give it, being no expert in this area.) @chepner - I agree, unfortunately I had to drastically cut my original comment due to the character limit so the part where I acknowledged that ended up not being there. But I think the linked-to answer did a good job about explaining that, based on thejoindefinition of a Monad (I presume something similar happens when you try using>>=)
– Robin Zigmond
Mar 7 at 13:51
@RobinZigmond Perhaps what's missing form the linked answer is a concrete counterexample. The answer simply shows that if we attempt to prove that monads compose in the straightforward way, we fail. Strictly speaking, this does not prove that monads don't compose: we need a counterexample.
– chi
Mar 7 at 14:10
Note that even though monads are not closed under composition, monad transformers are indeed closed under composition. Though it won't work with the kind of composition you have in your example, you need one which works for higher kinds.
– svenningsson
Mar 7 at 14:52
Does this answer your question? stackoverflow.com/questions/7040844/…
– Benjamin Hodgson♦
Mar 7 at 16:24
add a comment |
While I was learning Composing Types chapter from Haskell Book, I was given tasks to write Functor and Applicative instances for the following type.
newtype Compose f g a = Compose getCompose :: f (g a)
I wrote the following definitions
Functor:
fmap f (Compose fga) = Compose $ (fmap . fmap) f fga
Applicative:
(Compose f) <*> (Compose a) = Compose $ (<*>) <$> f <*> a
I learned that composing two Functors or Applicatives gives Functor and Applicative respectively.
The author also explained it is not possible to compose two Monads the same way. So we use Monad Transformers. I just do not want to read Monad Transformers unless I'm clear with why Monads do not compose.
So far I tried to write bind function like this:
Monad:
(>>=) :: Compose f g a -> (a -> Compose f g b) -> Compose f g b
(Compose fga) >>= h = (fmap.fmap) h fga
and of course got this error from GHC
Expected type: Compose f g b
Actual type: f (g (Compose f g b))
If I can strip the outermost f g somehow, the composition gives us a monad right? (I still couldn't figure out how to strip that though)
I tried reading answers from other Stack Overflow questions like this, but all answers are more theoretical or some Math. I still haven't learned why Monads do not compose. Can somebody explain me without using Math?
haskell monads composition monad-transformers
asked Mar 7 at 12:53
Nirvin MNirvin M
603
While I was learning Composing Types chapter from Haskell Book, I was given tasks to write Functor and Applicative instances for the following type.
newtype Compose f g a = Compose getCompose :: f (g a)
I wrote the following definitions
Functor:
fmap f (Compose fga) = Compose $ (fmap . fmap) f fga
Applicative:
(Compose f) <*> (Compose a) = Compose $ (<*>) <$> f <*> a
I learned that composing two Functors or Applicatives gives Functor and Applicative respectively.
The author also explained it is not possible to compose two Monads the same way. So we use Monad Transformers. I just do not want to read Monad Transformers unless I'm clear with why Monads do not compose.
So far I tried to write bind function like this:
Monad:
(>>=) :: Compose f g a -> (a -> Compose f g b) -> Compose f g b
(Compose fga) >>= h = (fmap.fmap) h fga
and of course got this error from GHC
Expected type: Compose f g b
Actual type: f (g (Compose f g b))
If I can strip the outermost f g somehow, the composition gives us a monad right? (I still couldn't figure out how to strip that though)
I tried reading answers from other Stack Overflow questions like this, but all answers are more theoretical or some Math. I still haven't learned why Monads do not compose. Can somebody explain me without using Math?
haskell monads composition monad-transformers
haskell monads composition monad-transformers
asked Mar 7 at 12:53
Nirvin MNirvin M
603
asked Mar 7 at 12:53
Nirvin MNirvin M
603
asked Mar 7 at 12:53
Nirvin MNirvin M
603
asked Mar 7 at 12:53
Nirvin MNirvin M
603
asked Mar 7 at 12:53
Nirvin MNirvin M
603
603
2
@RobinZigmond But given that a monad is a functor, something about the extra structure in a monad "breaks" composition. I think that's what the OP is looking for, what that "something" is.
– chepner
Mar 7 at 13:48
@NirvinM - not sure why you think I'm being "mean". I'm just trying to understand what you need by way of further explanation. (Not that I'm necessarily able to give it, being no expert in this area.) @chepner - I agree, unfortunately I had to drastically cut my original comment due to the character limit so the part where I acknowledged that ended up not being there. But I think the linked-to answer did a good job about explaining that, based on thejoindefinition of a Monad (I presume something similar happens when you try using>>=)
– Robin Zigmond
Mar 7 at 13:51
@RobinZigmond Perhaps what's missing form the linked answer is a concrete counterexample. The answer simply shows that if we attempt to prove that monads compose in the straightforward way, we fail. Strictly speaking, this does not prove that monads don't compose: we need a counterexample.
– chi
Mar 7 at 14:10
Note that even though monads are not closed under composition, monad transformers are indeed closed under composition. Though it won't work with the kind of composition you have in your example, you need one which works for higher kinds.
– svenningsson
Mar 7 at 14:52
Does this answer your question? stackoverflow.com/questions/7040844/…
– Benjamin Hodgson♦
Mar 7 at 16:24
add a comment |
2
@RobinZigmond But given that a monad is a functor, something about the extra structure in a monad "breaks" composition. I think that's what the OP is looking for, what that "something" is.
– chepner
Mar 7 at 13:48
@NirvinM - not sure why you think I'm being "mean". I'm just trying to understand what you need by way of further explanation. (Not that I'm necessarily able to give it, being no expert in this area.) @chepner - I agree, unfortunately I had to drastically cut my original comment due to the character limit so the part where I acknowledged that ended up not being there. But I think the linked-to answer did a good job about explaining that, based on thejoindefinition of a Monad (I presume something similar happens when you try using>>=)
– Robin Zigmond
Mar 7 at 13:51
@RobinZigmond Perhaps what's missing form the linked answer is a concrete counterexample. The answer simply shows that if we attempt to prove that monads compose in the straightforward way, we fail. Strictly speaking, this does not prove that monads don't compose: we need a counterexample.
– chi
Mar 7 at 14:10
Note that even though monads are not closed under composition, monad transformers are indeed closed under composition. Though it won't work with the kind of composition you have in your example, you need one which works for higher kinds.
– svenningsson
Mar 7 at 14:52
Does this answer your question? stackoverflow.com/questions/7040844/…
– Benjamin Hodgson♦
Mar 7 at 16:24
2
2
@RobinZigmond But given that a monad is a functor, something about the extra structure in a monad "breaks" composition. I think that's what the OP is looking for, what that "something" is.
– chepner
Mar 7 at 13:48
@RobinZigmond But given that a monad is a functor, something about the extra structure in a monad "breaks" composition. I think that's what the OP is looking for, what that "something" is.
– chepner
Mar 7 at 13:48
@NirvinM - not sure why you think I'm being "mean". I'm just trying to understand what you need by way of further explanation. (Not that I'm necessarily able to give it, being no expert in this area.) @chepner - I agree, unfortunately I had to drastically cut my original comment due to the character limit so the part where I acknowledged that ended up not being there. But I think the linked-to answer did a good job about explaining that, based on the
join definition of a Monad (I presume something similar happens when you try using >>=)– Robin Zigmond
Mar 7 at 13:51
@NirvinM - not sure why you think I'm being "mean". I'm just trying to understand what you need by way of further explanation. (Not that I'm necessarily able to give it, being no expert in this area.) @chepner - I agree, unfortunately I had to drastically cut my original comment due to the character limit so the part where I acknowledged that ended up not being there. But I think the linked-to answer did a good job about explaining that, based on the
join definition of a Monad (I presume something similar happens when you try using >>=)– Robin Zigmond
Mar 7 at 13:51
@RobinZigmond Perhaps what's missing form the linked answer is a concrete counterexample. The answer simply shows that if we attempt to prove that monads compose in the straightforward way, we fail. Strictly speaking, this does not prove that monads don't compose: we need a counterexample.
– chi
Mar 7 at 14:10
@RobinZigmond Perhaps what's missing form the linked answer is a concrete counterexample. The answer simply shows that if we attempt to prove that monads compose in the straightforward way, we fail. Strictly speaking, this does not prove that monads don't compose: we need a counterexample.
– chi
Mar 7 at 14:10
Note that even though monads are not closed under composition, monad transformers are indeed closed under composition. Though it won't work with the kind of composition you have in your example, you need one which works for higher kinds.
– svenningsson
Mar 7 at 14:52
Note that even though monads are not closed under composition, monad transformers are indeed closed under composition. Though it won't work with the kind of composition you have in your example, you need one which works for higher kinds.
– svenningsson
Mar 7 at 14:52
Does this answer your question? stackoverflow.com/questions/7040844/…
– Benjamin Hodgson♦
Mar 7 at 16:24
Does this answer your question? stackoverflow.com/questions/7040844/…
– Benjamin Hodgson♦
Mar 7 at 16:24
add a comment |
1 Answer
1
active
oldest
votes
I think this is easiest to understand by looking at the join operator:
join :: Monad m => m (m a) -> m a
join is an alternative to >>= for defining a Monad, and is a little easier to reason about. (But now you have an exercise to do: show how to implement >>= from join, and how to implement join from >>=!)
Let's try to make a join operation for Composed f g and see what goes wrong. Our input is essentially a value of type f (g (f (g a))), and we want to produce a value of type f (g a). We also know that we have join for f and g individually, so if we could get a value of type f (f (g (g a))), then we could hit it with fmap join . join to get the f (g a) we wanted.
Now, f (f (g (g a))) isn't so far from f (g (f (g a))). All we really need is a function like this: distribute :: g (f a) -> f (g a). Then we could implement join like this:
join = Compose . fmap join . join . fmap (distribute . fmap getCompose) . getCompose
Note: there are some laws that we would want distribute to satisfy, in order to make sure that the join we get here is lawful.
Ok, so that shows how we can compose two monads if we have a distributive law distribute :: g (f a) -> f (g a). Now, it could be true that every pair of monads has a distributive law. Maybe we just have to think really hard about how to write one down?
Unfortunately there are pairs of monads that don't have a distributive law. So we can answer your original question by producing two monads that definitely don't have a way of turning a g (f a) into an f (g a). These two monads will witness to the fact that monads don't compose in general.
I claim that g = IO and f = Maybe do not have a distributive law
-- Impossible!
distribute :: IO (Maybe a) -> Maybe (IO a)
Let's think about why such a thing should be impossible. The input to this function is an IO action that goes out into the real world and eventually produces Nothing or a Just x. The output of this function is either Nothing, or Just an IO action that, when run, eventually produces x. To produce the Maybe (IO a), we would have to peek into the future and predict what the IO (Maybe a) action is going to do!
In summary:
- Monads can only compose if there is a distributive law
g (f a) -> f (g a). - There are some monads that don't have such a distributive law.
Some monads can compose with each other, but not every pair of monads can compose.
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
distribute aka sequenceA? the types fit (besides the Traversable constraint ong)
– Will Ness
Mar 7 at 15:53
@WillNess there are various way to distribute functors, e.g. hackage.haskell.org/package/distributive-0.6/docs/… is another one.
– phadej
Mar 7 at 16:08
while this is a good answer, I'm not sure the counterexample is totally convincing given thatunsafePerformIOexists, which should be "impossible" for much the same reason.
– Robin Zigmond
Mar 7 at 16:28
@RobinZigmond: I think there are two answers to that: (1) We reason aboutMonadin the total and pure fragment of Haskell – if we don't worry aboutundefined, we certainly don't worry aboutunsafePerformIO(especially sinceunsafePerformIOcan be used to implementunsafeCast :: a -> b). (2)unsafePerformIOdoesn't (I presume) satisfy the laws that, as Matt mentioned, we need for the resultingMonadinstance to be lawful.
– Antal Spector-Zabusky
Mar 7 at 18:12
1
@RobinZigmonddistribute ( getLine >>= (s -> if length s > 2 then return (Just s) else return Nothing) ) :: Maybe (IO String). So it's a value which already knows what a user will type. If it'sJust act, we can execute thatact, and it will magically produce a user which is guaranteed to type in no less than 3 characters! that's not unsafe I/O, that's pure magic. // that's how I understand that argument anyway.
– Will Ness
Mar 7 at 18:48
|
show 4 more comments
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55044292%2fwhy-are-monads-not-closed-under-composition%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
I think this is easiest to understand by looking at the join operator:
join :: Monad m => m (m a) -> m a
join is an alternative to >>= for defining a Monad, and is a little easier to reason about. (But now you have an exercise to do: show how to implement >>= from join, and how to implement join from >>=!)
Let's try to make a join operation for Composed f g and see what goes wrong. Our input is essentially a value of type f (g (f (g a))), and we want to produce a value of type f (g a). We also know that we have join for f and g individually, so if we could get a value of type f (f (g (g a))), then we could hit it with fmap join . join to get the f (g a) we wanted.
Now, f (f (g (g a))) isn't so far from f (g (f (g a))). All we really need is a function like this: distribute :: g (f a) -> f (g a). Then we could implement join like this:
join = Compose . fmap join . join . fmap (distribute . fmap getCompose) . getCompose
Note: there are some laws that we would want distribute to satisfy, in order to make sure that the join we get here is lawful.
Ok, so that shows how we can compose two monads if we have a distributive law distribute :: g (f a) -> f (g a). Now, it could be true that every pair of monads has a distributive law. Maybe we just have to think really hard about how to write one down?
Unfortunately there are pairs of monads that don't have a distributive law. So we can answer your original question by producing two monads that definitely don't have a way of turning a g (f a) into an f (g a). These two monads will witness to the fact that monads don't compose in general.
I claim that g = IO and f = Maybe do not have a distributive law
-- Impossible!
distribute :: IO (Maybe a) -> Maybe (IO a)
Let's think about why such a thing should be impossible. The input to this function is an IO action that goes out into the real world and eventually produces Nothing or a Just x. The output of this function is either Nothing, or Just an IO action that, when run, eventually produces x. To produce the Maybe (IO a), we would have to peek into the future and predict what the IO (Maybe a) action is going to do!
In summary:
- Monads can only compose if there is a distributive law
g (f a) -> f (g a). - There are some monads that don't have such a distributive law.
Some monads can compose with each other, but not every pair of monads can compose.
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
distribute aka sequenceA? the types fit (besides the Traversable constraint ong)
– Will Ness
Mar 7 at 15:53
@WillNess there are various way to distribute functors, e.g. hackage.haskell.org/package/distributive-0.6/docs/… is another one.
– phadej
Mar 7 at 16:08
while this is a good answer, I'm not sure the counterexample is totally convincing given thatunsafePerformIOexists, which should be "impossible" for much the same reason.
– Robin Zigmond
Mar 7 at 16:28
@RobinZigmond: I think there are two answers to that: (1) We reason aboutMonadin the total and pure fragment of Haskell – if we don't worry aboutundefined, we certainly don't worry aboutunsafePerformIO(especially sinceunsafePerformIOcan be used to implementunsafeCast :: a -> b). (2)unsafePerformIOdoesn't (I presume) satisfy the laws that, as Matt mentioned, we need for the resultingMonadinstance to be lawful.
– Antal Spector-Zabusky
Mar 7 at 18:12
1
@RobinZigmonddistribute ( getLine >>= (s -> if length s > 2 then return (Just s) else return Nothing) ) :: Maybe (IO String). So it's a value which already knows what a user will type. If it'sJust act, we can execute thatact, and it will magically produce a user which is guaranteed to type in no less than 3 characters! that's not unsafe I/O, that's pure magic. // that's how I understand that argument anyway.
– Will Ness
Mar 7 at 18:48
|
show 4 more comments
I think this is easiest to understand by looking at the join operator:
join :: Monad m => m (m a) -> m a
join is an alternative to >>= for defining a Monad, and is a little easier to reason about. (But now you have an exercise to do: show how to implement >>= from join, and how to implement join from >>=!)
Let's try to make a join operation for Composed f g and see what goes wrong. Our input is essentially a value of type f (g (f (g a))), and we want to produce a value of type f (g a). We also know that we have join for f and g individually, so if we could get a value of type f (f (g (g a))), then we could hit it with fmap join . join to get the f (g a) we wanted.
Now, f (f (g (g a))) isn't so far from f (g (f (g a))). All we really need is a function like this: distribute :: g (f a) -> f (g a). Then we could implement join like this:
join = Compose . fmap join . join . fmap (distribute . fmap getCompose) . getCompose
Note: there are some laws that we would want distribute to satisfy, in order to make sure that the join we get here is lawful.
Ok, so that shows how we can compose two monads if we have a distributive law distribute :: g (f a) -> f (g a). Now, it could be true that every pair of monads has a distributive law. Maybe we just have to think really hard about how to write one down?
Unfortunately there are pairs of monads that don't have a distributive law. So we can answer your original question by producing two monads that definitely don't have a way of turning a g (f a) into an f (g a). These two monads will witness to the fact that monads don't compose in general.
I claim that g = IO and f = Maybe do not have a distributive law
-- Impossible!
distribute :: IO (Maybe a) -> Maybe (IO a)
Let's think about why such a thing should be impossible. The input to this function is an IO action that goes out into the real world and eventually produces Nothing or a Just x. The output of this function is either Nothing, or Just an IO action that, when run, eventually produces x. To produce the Maybe (IO a), we would have to peek into the future and predict what the IO (Maybe a) action is going to do!
In summary:
- Monads can only compose if there is a distributive law
g (f a) -> f (g a). - There are some monads that don't have such a distributive law.
Some monads can compose with each other, but not every pair of monads can compose.
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
distribute aka sequenceA? the types fit (besides the Traversable constraint ong)
– Will Ness
Mar 7 at 15:53
@WillNess there are various way to distribute functors, e.g. hackage.haskell.org/package/distributive-0.6/docs/… is another one.
– phadej
Mar 7 at 16:08
while this is a good answer, I'm not sure the counterexample is totally convincing given thatunsafePerformIOexists, which should be "impossible" for much the same reason.
– Robin Zigmond
Mar 7 at 16:28
@RobinZigmond: I think there are two answers to that: (1) We reason aboutMonadin the total and pure fragment of Haskell – if we don't worry aboutundefined, we certainly don't worry aboutunsafePerformIO(especially sinceunsafePerformIOcan be used to implementunsafeCast :: a -> b). (2)unsafePerformIOdoesn't (I presume) satisfy the laws that, as Matt mentioned, we need for the resultingMonadinstance to be lawful.
– Antal Spector-Zabusky
Mar 7 at 18:12
1
@RobinZigmonddistribute ( getLine >>= (s -> if length s > 2 then return (Just s) else return Nothing) ) :: Maybe (IO String). So it's a value which already knows what a user will type. If it'sJust act, we can execute thatact, and it will magically produce a user which is guaranteed to type in no less than 3 characters! that's not unsafe I/O, that's pure magic. // that's how I understand that argument anyway.
– Will Ness
Mar 7 at 18:48
|
show 4 more comments
I think this is easiest to understand by looking at the join operator:
join :: Monad m => m (m a) -> m a
join is an alternative to >>= for defining a Monad, and is a little easier to reason about. (But now you have an exercise to do: show how to implement >>= from join, and how to implement join from >>=!)
Let's try to make a join operation for Composed f g and see what goes wrong. Our input is essentially a value of type f (g (f (g a))), and we want to produce a value of type f (g a). We also know that we have join for f and g individually, so if we could get a value of type f (f (g (g a))), then we could hit it with fmap join . join to get the f (g a) we wanted.
Now, f (f (g (g a))) isn't so far from f (g (f (g a))). All we really need is a function like this: distribute :: g (f a) -> f (g a). Then we could implement join like this:
join = Compose . fmap join . join . fmap (distribute . fmap getCompose) . getCompose
Note: there are some laws that we would want distribute to satisfy, in order to make sure that the join we get here is lawful.
Ok, so that shows how we can compose two monads if we have a distributive law distribute :: g (f a) -> f (g a). Now, it could be true that every pair of monads has a distributive law. Maybe we just have to think really hard about how to write one down?
Unfortunately there are pairs of monads that don't have a distributive law. So we can answer your original question by producing two monads that definitely don't have a way of turning a g (f a) into an f (g a). These two monads will witness to the fact that monads don't compose in general.
I claim that g = IO and f = Maybe do not have a distributive law
-- Impossible!
distribute :: IO (Maybe a) -> Maybe (IO a)
Let's think about why such a thing should be impossible. The input to this function is an IO action that goes out into the real world and eventually produces Nothing or a Just x. The output of this function is either Nothing, or Just an IO action that, when run, eventually produces x. To produce the Maybe (IO a), we would have to peek into the future and predict what the IO (Maybe a) action is going to do!
In summary:
- Monads can only compose if there is a distributive law
g (f a) -> f (g a). - There are some monads that don't have such a distributive law.
Some monads can compose with each other, but not every pair of monads can compose.
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
I think this is easiest to understand by looking at the join operator:
join :: Monad m => m (m a) -> m a
join is an alternative to >>= for defining a Monad, and is a little easier to reason about. (But now you have an exercise to do: show how to implement >>= from join, and how to implement join from >>=!)
Let's try to make a join operation for Composed f g and see what goes wrong. Our input is essentially a value of type f (g (f (g a))), and we want to produce a value of type f (g a). We also know that we have join for f and g individually, so if we could get a value of type f (f (g (g a))), then we could hit it with fmap join . join to get the f (g a) we wanted.
Now, f (f (g (g a))) isn't so far from f (g (f (g a))). All we really need is a function like this: distribute :: g (f a) -> f (g a). Then we could implement join like this:
join = Compose . fmap join . join . fmap (distribute . fmap getCompose) . getCompose
Note: there are some laws that we would want distribute to satisfy, in order to make sure that the join we get here is lawful.
Ok, so that shows how we can compose two monads if we have a distributive law distribute :: g (f a) -> f (g a). Now, it could be true that every pair of monads has a distributive law. Maybe we just have to think really hard about how to write one down?
Unfortunately there are pairs of monads that don't have a distributive law. So we can answer your original question by producing two monads that definitely don't have a way of turning a g (f a) into an f (g a). These two monads will witness to the fact that monads don't compose in general.
I claim that g = IO and f = Maybe do not have a distributive law
-- Impossible!
distribute :: IO (Maybe a) -> Maybe (IO a)
Let's think about why such a thing should be impossible. The input to this function is an IO action that goes out into the real world and eventually produces Nothing or a Just x. The output of this function is either Nothing, or Just an IO action that, when run, eventually produces x. To produce the Maybe (IO a), we would have to peek into the future and predict what the IO (Maybe a) action is going to do!
In summary:
- Monads can only compose if there is a distributive law
g (f a) -> f (g a). - There are some monads that don't have such a distributive law.
Some monads can compose with each other, but not every pair of monads can compose.
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
answered Mar 7 at 14:53
Matt NoonanMatt Noonan
28614
28614
distribute aka sequenceA? the types fit (besides the Traversable constraint ong)
– Will Ness
Mar 7 at 15:53
@WillNess there are various way to distribute functors, e.g. hackage.haskell.org/package/distributive-0.6/docs/… is another one.
– phadej
Mar 7 at 16:08
while this is a good answer, I'm not sure the counterexample is totally convincing given thatunsafePerformIOexists, which should be "impossible" for much the same reason.
– Robin Zigmond
Mar 7 at 16:28
@RobinZigmond: I think there are two answers to that: (1) We reason aboutMonadin the total and pure fragment of Haskell – if we don't worry aboutundefined, we certainly don't worry aboutunsafePerformIO(especially sinceunsafePerformIOcan be used to implementunsafeCast :: a -> b). (2)unsafePerformIOdoesn't (I presume) satisfy the laws that, as Matt mentioned, we need for the resultingMonadinstance to be lawful.
– Antal Spector-Zabusky
Mar 7 at 18:12
1
@RobinZigmonddistribute ( getLine >>= (s -> if length s > 2 then return (Just s) else return Nothing) ) :: Maybe (IO String). So it's a value which already knows what a user will type. If it'sJust act, we can execute thatact, and it will magically produce a user which is guaranteed to type in no less than 3 characters! that's not unsafe I/O, that's pure magic. // that's how I understand that argument anyway.
– Will Ness
Mar 7 at 18:48
|
show 4 more comments
distribute aka sequenceA? the types fit (besides the Traversable constraint ong)
– Will Ness
Mar 7 at 15:53
@WillNess there are various way to distribute functors, e.g. hackage.haskell.org/package/distributive-0.6/docs/… is another one.
– phadej
Mar 7 at 16:08
while this is a good answer, I'm not sure the counterexample is totally convincing given thatunsafePerformIOexists, which should be "impossible" for much the same reason.
– Robin Zigmond
Mar 7 at 16:28
@RobinZigmond: I think there are two answers to that: (1) We reason aboutMonadin the total and pure fragment of Haskell – if we don't worry aboutundefined, we certainly don't worry aboutunsafePerformIO(especially sinceunsafePerformIOcan be used to implementunsafeCast :: a -> b). (2)unsafePerformIOdoesn't (I presume) satisfy the laws that, as Matt mentioned, we need for the resultingMonadinstance to be lawful.
– Antal Spector-Zabusky
Mar 7 at 18:12
1
@RobinZigmonddistribute ( getLine >>= (s -> if length s > 2 then return (Just s) else return Nothing) ) :: Maybe (IO String). So it's a value which already knows what a user will type. If it'sJust act, we can execute thatact, and it will magically produce a user which is guaranteed to type in no less than 3 characters! that's not unsafe I/O, that's pure magic. // that's how I understand that argument anyway.
– Will Ness
Mar 7 at 18:48
distribute aka sequenceA? the types fit (besides the Traversable constraint on
g)– Will Ness
Mar 7 at 15:53
distribute aka sequenceA? the types fit (besides the Traversable constraint on
g)– Will Ness
Mar 7 at 15:53
@WillNess there are various way to distribute functors, e.g. hackage.haskell.org/package/distributive-0.6/docs/… is another one.
– phadej
Mar 7 at 16:08
@WillNess there are various way to distribute functors, e.g. hackage.haskell.org/package/distributive-0.6/docs/… is another one.
– phadej
Mar 7 at 16:08
while this is a good answer, I'm not sure the counterexample is totally convincing given that
unsafePerformIO exists, which should be "impossible" for much the same reason.– Robin Zigmond
Mar 7 at 16:28
while this is a good answer, I'm not sure the counterexample is totally convincing given that
unsafePerformIO exists, which should be "impossible" for much the same reason.– Robin Zigmond
Mar 7 at 16:28
@RobinZigmond: I think there are two answers to that: (1) We reason about
Monad in the total and pure fragment of Haskell – if we don't worry about undefined, we certainly don't worry about unsafePerformIO (especially since unsafePerformIO can be used to implement unsafeCast :: a -> b). (2) unsafePerformIO doesn't (I presume) satisfy the laws that, as Matt mentioned, we need for the resulting Monad instance to be lawful.– Antal Spector-Zabusky
Mar 7 at 18:12
@RobinZigmond: I think there are two answers to that: (1) We reason about
Monad in the total and pure fragment of Haskell – if we don't worry about undefined, we certainly don't worry about unsafePerformIO (especially since unsafePerformIO can be used to implement unsafeCast :: a -> b). (2) unsafePerformIO doesn't (I presume) satisfy the laws that, as Matt mentioned, we need for the resulting Monad instance to be lawful.– Antal Spector-Zabusky
Mar 7 at 18:12
1
1
@RobinZigmond
distribute ( getLine >>= (s -> if length s > 2 then return (Just s) else return Nothing) ) :: Maybe (IO String). So it's a value which already knows what a user will type. If it's Just act, we can execute that act, and it will magically produce a user which is guaranteed to type in no less than 3 characters! that's not unsafe I/O, that's pure magic. // that's how I understand that argument anyway.– Will Ness
Mar 7 at 18:48
@RobinZigmond
distribute ( getLine >>= (s -> if length s > 2 then return (Just s) else return Nothing) ) :: Maybe (IO String). So it's a value which already knows what a user will type. If it's Just act, we can execute that act, and it will magically produce a user which is guaranteed to type in no less than 3 characters! that's not unsafe I/O, that's pure magic. // that's how I understand that argument anyway.– Will Ness
Mar 7 at 18:48
|
show 4 more comments
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55044292%2fwhy-are-monads-not-closed-under-composition%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
@RobinZigmond But given that a monad is a functor, something about the extra structure in a monad "breaks" composition. I think that's what the OP is looking for, what that "something" is.
– chepner
Mar 7 at 13:48
@NirvinM - not sure why you think I'm being "mean". I'm just trying to understand what you need by way of further explanation. (Not that I'm necessarily able to give it, being no expert in this area.) @chepner - I agree, unfortunately I had to drastically cut my original comment due to the character limit so the part where I acknowledged that ended up not being there. But I think the linked-to answer did a good job about explaining that, based on the
joindefinition of a Monad (I presume something similar happens when you try using>>=)– Robin Zigmond
Mar 7 at 13:51
@RobinZigmond Perhaps what's missing form the linked answer is a concrete counterexample. The answer simply shows that if we attempt to prove that monads compose in the straightforward way, we fail. Strictly speaking, this does not prove that monads don't compose: we need a counterexample.
– chi
Mar 7 at 14:10
Note that even though monads are not closed under composition, monad transformers are indeed closed under composition. Though it won't work with the kind of composition you have in your example, you need one which works for higher kinds.
– svenningsson
Mar 7 at 14:52
Does this answer your question? stackoverflow.com/questions/7040844/…
– Benjamin Hodgson♦
Mar 7 at 16:24