Maths - Monad Code

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:

*

*/
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:

* */

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)))
}

metadata block
see also:
Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

flag flag flag flag flag flag The Princeton Companion to Mathematics - This is a big book that attempts to give a wide overview of the whole of mathematics, inevitably there are many things missing, but it gives a good insight into the history, concepts, branches, theorems and wider perspective of mathematics. It is well written and, if you are interested in maths, this is the type of book where you can open a page at random and find something interesting to read. To some extent it can be used as a reference book, although it doesn't have tables of formula for trig functions and so on, but where it is most useful is when you want to read about various topics to find out which topics are interesting and relevant to you.

 

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.