If it does type check, this would mean that an applicative instance of (->) a implies a monad instance, that is, they would be interchangeable. Is that the case? Does this happen with other monads?
{-# LANGUAGE FlexibleInstances #-}{-# LANGUAGE UndecidableInstances #-}moduleArrowwhereimportPreludehiding(Functor(..),Applicative(..),Monad(..))classFunctorfwherefmap::(a->b)->fa->fbinstanceFunctor((->)a)wherefmap=(.)classFunctorf=>Applicativefwherepure::a->fa(<*>)::f(a->b)->fa->fbinstance{-# OVERLAPPING #-}Applicative((->)a)wherepure=constf<*>g=\x->fx(gx)k::a->b->ak=purei::a->ai=k<*>kclassFunctorm=>Monadmwherereturn::a->ma-- (x -> a) -> (x -> a -> b) -> x -> b-- (x -> a) -> (a -> x -> b) -> x -> b---- (a -> b -> c) -> (a -> b) -> a -> c-- (a -> b) -> (b -> a -> c) -> b -> c(>>=)::ma->(a->mb)->mbinstanceMonad((->)a)wherereturn=constf>>=g=\x->g(fx)xs::(a->b->c)->(a->b)->a->csxy=dox<-xy<-yreturn(xy)s'::(a->b->c)->(a->b)->a->cs'xy=x>>=\x->y>>=\y->return(xy)instance{-# OVERLAPPABLE #-}(Functorm,Monadm)=>Applicativemwherepure=returnf<*>x=f>>=\f->x>>=\x->return(fx)
input:
main = \f g x -> g (f x) x
intermediate form:
s(k(s(k(s(k(ss(sk)))))(s(s(ks)k))))kuz
I would guess neither of these terms type check as variables probably get coupled together by unification somewhere. I was wrong! It does type check:
λ> :t s (k (s (k (s (k (s s (s k))))) (s (s (k s) k)))) k
s (k (s (k (s (k (s s (s k))))) (s (s (k s) k)))) k
:: (b1 -> b2) -> (b2 -> b1 -> c) -> b1 -> c
The λ-calculus, or lambda calculus, is a logical system based on anonymous functions. For example, this a λ-expression:
λf.(λx.xx)(λx.f(xx))
However, for the purposes of this challenge, we'll sim...
Answering the original question: yes, it is entirely possible to implement (>>=) in terms of (<*>) for the (->) a monad! Specifically: f >>= g = flip g <*> f. In fact, you can do this sort of thing for any Representable functor (i.e. functors which are isomorphic to (->) a), though it is of course impossible in general.
The Applicative/Monad instances for (->) a are in fact _very_ useful — I use them all the time! For instance, if I have two predicates, pred1 :: a -> Bool and pred2 -> Bool, I can combine them by doing (||) <$> pred1 <*> pred2 or (&&) <$> pred1 <*> pred2. Or, if that’s too unreadable, you could use do notation:
That being said, I can’t think of any reason why I would prefer do notation to (<*>) — usually the former is more powerful, but as I already said, they’re of equal power when using (->) a.
(<*>)
andpure
for the(->) a
monad are respectively the S and K combinators of SK calculus.(>>=)
is remarkably similar to the S combinator:It gets a lot clearer when one flips
(>>=)
:My question is, can I implement
(>>=)
in terms of S and K? That is, in terms of(<*>)
andpure
?I believe it should be possible, as one can compile lambda calculus to SK, but it may not type check.
If it does type check, this would mean that an applicative instance of
(->) a
implies a monad instance, that is, they would be interchangeable. Is that the case? Does this happen with other monads?Using this lambda calculus to SK translator
(>>=)
becomes the following expression:Using this online lambda calculus to SK translator it becomes:
I would guess neither of these terms type check as variables probably get coupled together by unification somewhere.I was wrong! It does type check:Pedro Minicz said:
Should be
(>>=) :: ... -> a -> c
if the effect is(a->)
.Answering the original question: yes, it is entirely possible to implement
(>>=)
in terms of(<*>)
for the(->) a
monad! Specifically:f >>= g = flip g <*> f
. In fact, you can do this sort of thing for anyRepresentable
functor (i.e. functors which are isomorphic to(->) a
), though it is of course impossible in general.Kim-Ee Yeoh said:
Indeed! Thank you for spotting that!
I've written a small piece about this monad. Any and all feedback/criticisms are highly welcome!
I didn’t manage to think of any useful examples of do notation for the (->) a monad.
job security!
The
Applicative
/Monad
instances for(->) a
are in fact _very_ useful — I use them all the time! For instance, if I have two predicates,pred1 :: a -> Bool
andpred2 -> Bool
, I can combine them by doing(||) <$> pred1 <*> pred2
or(&&) <$> pred1 <*> pred2
. Or, if that’s too unreadable, you could usedo
notation:That being said, I can’t think of any reason why I would prefer
do
notation to(<*>)
— usually the former is more powerful, but as I already said, they’re of equal power when using(->) a
.The precedence of
(<$>)
/(.)
and<*>
seems to make things kind of annoying:I personally always use liftA2 when I want to lift two functions over the same argument instead of the operators