Merging the Functor and Monad classes: ((->) a) as a monad type constructor
The problem: for every new monad type I want to map over I have to make it
an instance of the class Functor:
class Functor f where
map :: (a -> b) -> (f a -> f b)
which is annoying since Wadler's work with monads ([3]) has shown that map
can be defined for any monad type:
map f ma = ma >>= (\ a -> return (f a))
This lack of generality is due to one particular instance of Functor:
instance Functor ((->) a) where
map f g x = f (g x)
While this definition of map thwarts any direct attempt to generalise it,
the instance declaration together with the type for map over monad types
((a -> b) -> (M a -> M b)) hints at a possible solution: could ((->) a)
be used as a monad type constructor?
This hint is enhanced by Hughes's work with arrows ([2]), which shows that
the function type (->) is an instance of ArrowApply:
instance ArrowApply (->) where
app = \ (f,x) -> f x
and any arrow which is an instance of ArrowApply can be transformed into
a monad:
newtype ArrowApply a => ArrowMonad a b = M (a Void b)
instance ArrowApply a => Monad (ArrowMonad a) where
return x = M (arr (\ x -> x))
M m >>= f = M (m >>>
arr (\ x -> let M h = f x in (h,undefined)) >>>
app)
So it is possible to transform (->) to a monad type in this way but it is
simpler in this case to construct the neccessary operators using their
expected type signatures.
Basic information - if (M a) is a monad type then there exist operators
return :: b -> M b
(>>=) :: M b -> (b -> M c) -> M c
Thus
return :: b -> ((->) a) b
:: b -> (a -> b)
return b = \ _ -> b
and
(>>=) :: ((->) a) b -> (b -> ((->) a) c) -> ((->) a) c
:: (a -> b) -> (b -> (a -> c)) -> (a -> c)
(>>=) m k = \ x -> k (m x) x
Monad operations also satify three laws:
left-unit: return a >>= \ b -> n = n[a/b]
right-unit: m >>= \ a -> return a = m
associative:
m >>= (\ a -> n >>= \ b -> o) = (m >>= \ a -> n) >>= \ b -> o
iff a does not occur free in o
for left-unit:
return a >>= \ b -> n = n[a/b]
(return a >>= \ b -> n), n[a/b] :: a -> c
thus
(return a >>= \ b -> n) p = n[a/b] p
LSE = (return a >>= \ b -> n) p
= (\ x -> (\ b -> n) ((return a) x) x) p (defn (>>=))
= (\ b -> n) ((return a) p) p (application)
= (\ b -> n) ((\ _ -> a) p) p (def return)
= (\ b -> n) a p (application)
= n[a/b] p
= RSE
for right-unit:
m >>= \ a -> return a = m
(m >>= \ a -> return a), m :: a->b
thus
(m >>= \ a -> return a) p = m p
LSE = (m >>= \ a -> return a) p
= (\ x -> (\ a -> return a) (m x) x) p (defn (>>=))
= (\ a -> return a) (m p) p (application)
= return (m p) p (application)
= (\ _ -> m p) p (defn return)
= m p (application)
= RSE
for associative:
m >>= (\ a -> n >>= \ b -> o) = (m >>= \ a -> n) >>= \ b -> o
(m >>= (\ a -> n >>= \ b -> o)),
((m >>= \ a -> n) >>= \ b -> o) :: a -> c
thus
(m >>= (\ a -> n >>= \ b -> o)) p = ((m >>= \ a -> n) >>= \ b -> o) p
iff a does not occur free in o
LSE = (m >>= (\ a -> n >>= \ b -> o)) p
= (\ x -> (\ a -> n >>= \ b -> o) (m x) x) p (defn (>>=))
= (\ a -> n >>= \ b -> o) (m p) p (application)
= (n >>= \ b -> o)[(m p)/a] p (application)
= (\ x -> (\ b -> o) (n x) x)[(m p)/a] p (defn (>>=))
= ((\ b -> o) (n p) p)[(m p)/a] (application)
= (o[(n p)/b] p)[(m p)/a] (application)
= o[(n p)/b][(m p)/a] p (no free a in p)
= o[(n[(m p)/a] p)/b] p (no free a in o)
RSE = ((m >>= \ a -> n) >>= \ b -> o) p
= (\ x -> (\ b -> o) ((m >>= \ a -> n) x) x) p (defn (>>=))
= (\ b -> o) ((m >>= \ a -> n) p) p (application)
= o[((m >>= \ a -> n) p)/b] p (application)
= o[((\ x -> (\ a -> n) (m x) x) p)/b] p (defn (>>=))
= o[((\ a -> n) (m p) p)/b] p (application)
= o[(n[(m p)/a] p)/b] p (application)
= LSE
Since ((->) a) can be used as a monad type constructor, new operators are
available...
(>>) :: M b -> M c -> M c
:: ((->) a) b -> ((->) a) c -> ((->) a) c
:: (a -> b) -> (a -> c) -> (a -> c)
m >> n = m >>= \ _ -> n
join :: M (M b) -> M b
:: ((->) a) (((->) a) b) -> ((->) a) b
:: (a -> (a ->b)) -> (a -> b)
join z = z >>= \ m -> m
etc.
...and our old favourite (finally!) becomes a generic monad type operator.
map :: (b -> c) -> (M b -> (M c)
:: (b -> c) -> (((->) a) b -> ((->) a) c)
:: (b -> c) -> ((a -> b) ->(a -> c))
map f m = m >>= \ a -> return (f a)
Just to be sure:
map f g x = (g >>= \ a -> return (f a)) x
= (\ t -> (\ a -> return (f a)) (g t) t) x (defn (>>=))
= (\ a -> return (f a)) (g x) x (application)
= (return (f (g x))) x (application)
= (\ _ -> f (g x)) x (defn return)
= f (g x) (application)
and just out of curiousity:
join z x = (z >>= \ m -> m) x
= (\ t -> (\ m -> m) (z t) t) x (defn (>>=))
= (\ m -> m) (z x) x (application)
= (z x) x (application)
= z x x
Refs:
[1] Philip Wadler. Monads for functional programming. In J. Jeuring
& E. Meijer, editors, Advanced Functional Programming, no. 925 in
LNCS pages 24-52, Springer Verlag, May 1995. (pages 11, 12)
[2] John Hughes. Generalising Monads to Arrows (draft). November 10
1998. (pages 18, 30)
[3] Philip Wadler. The Essense of Functional Programming. 16th ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1992
(page 14)
--Code for Prelude--
instance Monad ((->) a) where
m >>= f = \ x -> f (m x) x
return x = \ _ -> x
