Implementing monads in computer code.

## Haskell Code

Code from here.

The 'monad' type class is an endofunctor so it can derive from Functor, its mathematical form would be somthing like this (where return represents unit and join represents mult):

class Functor m => Monad m where return :: a -> m a join :: m (m a) -> m a

The above is what might be expected from the mathematical definition of a monad but it is not the form that we normally see in Haskell. The first step to what is provided in haskell is to take the Kleisli algebra from our Monad:

class Functor m => KleisliMonad m where return :: a -> m a -- | Left-to-right Kleisli composition of monads. (>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)

But even this is not what we usually see, to get there we change >=> (Kleisli composition) to bind (>>=) as here:

class Monad m where -- | Sequentially compose two actions, passing any value produced -- by the first as an argument to the second. (>>=) :: forall a b. m a -> (a -> m b) -> m b -- | Sequentially compose two actions, discarding any value produced -- by the first, like sequencing operators (such as the semicolon) -- in imperative languages. (>>) :: forall a b. m a -> m b -> m b -- Explicit for-alls so that we know what order to -- give type arguments when desugaring -- | Inject a value into the monadic type. return :: a -> m a -- | Fail with a message. This operation is not part of the -- mathematical definition of a monad, but is invoked on pattern-match -- failure in a @do@ expression. fail :: String -> m a {-# INLINE (>>) #-} m >> k = m >>= \_ -> k fail s = error s

Note that monad does not usually derive from Functor although, mathematically speaking, we might expect it to.

#### Some Instances

instance Monad ((->) r) where return = const f >>= k = \ r -> k (f r) r

List monad:

instance Monad [] where m >>= k = foldr ((++) . k) [] m m >> k = foldr ((++) . (\ _ -> k)) [] m return x = [x] fail _ = []

x

instance Monad IO where {-# INLINE return #-} {-# INLINE (>>) #-} {-# INLINE (>>=) #-} m >> k = m >>= \ _ -> k return = returnIO (>>=) = bindIO fail s = failIO s

x

x

## Scala Code

Code from here. package scalaz

trait Pure[P[_]] { def pure[A](a: => A): P[A] }

x

trait Pointed[P[_]] extends Functor[P] with Pure[P]

x

trait Apply[Z[_]] { def apply[A, B](f: Z[A => B], a: Z[A]): Z[B] }

x

trait Bind[Z[_]] { def bind[A, B](a: Z[A], f: A => Z[B]): Z[B] }

x

/** * Defines an applicative functor as described by McBride and Paterson in * Applicative Programming with Effects. * ** All instances must satisfy 4 laws:

**identity**

`forall a. a == apply(a, pure(identity))`

**composition**

`forall af ag a. apply(apply(a, ag), af) == apply(a, apply(ag, apply(af, pure(compose))))`

**homomorphism**

`forall f a. apply(pure(a), pure(f)) == pure(f(a))`

**interchange**

`forall af a. apply(pure(a), af) == apply(af, pure(f => f(x)))`

trait Applicative[Z[_]] extends Pointed[Z] with Apply[Z] { override def fmap[A, B](fa: Z[A], f: A => B): Z[B] = this(pure(f), fa) override def apply[A, B](f: Z[A => B], a: Z[A]): Z[B] = liftA2(f, a, (_:A => B)(_: A)) def liftA2[A, B, C](a: Z[A], b: Z[B], f: (A, B) => C): Z[C] = apply(fmap(a, f.curried), b) }

/** * Abstract a model that sequences computation through an environment. * *

* All monad instances must satisfy 3 laws:

**left identity**

`forall a f. f(a) == bind(pure(a), f)`

**right identity**

`forall a. a == bind(a, x => pure(x))`

**associativity**

`forall a f g. bind(a, x => bind(f(x), g)) == bind(bind(a, f), g)`

* */

trait Monad[M[_]] extends Applicative[M] with Bind[M] with Pointed[M] { override def fmap[A, B](fa: M[A], f: A => B) = bind(fa, (a: A) => pure(f(a))) override def apply[A, B](f: M[A => B], a: M[A]): M[B] = { lazy val fv = f lazy val av = a bind(fv, (k: A => B) => fmap(av, k(_: A))) } }

x

sealed trait Kleisli[M[_], A, B] { def apply(a: A): M[B] import Scalaz._ def >=>[C](k: Kleisli[M, B, C])(implicit b: Bind[M]): Kleisli[M, A, C] = ☆((a: A) => b.bind(this(a), k(_: B))) def >=>[C](k: B => M[C])(implicit b: Bind[M]): Kleisli[M, A, C] = >=>(☆(k)) def <=<[C](k: Kleisli[M, C, A])(implicit b: Bind[M]): Kleisli[M, C, B] = k >=> this def <=<[C](k: C => M[A])(implicit b: Bind[M]): Kleisli[M, C, B] = ☆(k) >=> this def compose[N[_]](f: M[B] => N[B]): Kleisli[N, A, B] = ☆((a: A) => f(this(a))) def traverse[F[_], AA <: A](f: F[AA])(implicit a: Applicative[M], t: Traverse[F]): M[F[B]] = f ↦ (Kleisli.this(_)) def =<<[AA <: A](a: M[AA])(implicit m: Bind[M]): M[B] = m.bind(a, apply _) def map[C](f: B => C)(implicit m: Functor[M]): Kleisli[M, A, C] = kleisli(a => m.fmap(apply(a), f)) def bind[C](f: B => M[C])(implicit m: Monad[M]): Kleisli[M, A, C] = kleisli(a => m.bind(apply(a), f)) def flatMap[C](f: B => Kleisli[M, A, C])(implicit m: Monad[M]): Kleisli[M, A, C] = kleisli(a => m.bind(apply(a), (x: B) => f(x)(a))) }