Monday, December 13, 2010

Monads, Applicative Functors and sequencing of effects

Monads and applicative functors are both used to model computations - yet it's interesting to note the subtle differences in the way they handle sequencing of effects. Both of them support an applicative style of effectful programming that lets you write code in pointfree style (in Haskell) making your code look so expressive.

Applicative functors are more general than monads and hence have a broader area of application in computation. Haskell does not define monads to be a derivative of applicative functors, possibly for some historical reasons. Scalaz does it and does it correctly and conveniently for you to reduce the number of abstractions that you need to have.

In Haskell we have sequence and sequenceA implemented for monads and applicatives separately ..

-- in Control.Monad
sequence  :: Monad m => [m a] -> m [a]

-- in Data.Traversable
class (Functor t, Foldable t) => Traversable t where
  sequenceA :: Applicative f => t (f a) -> f (t a)

In scalaz we have the following ..

// defined as pimped types on type constructors
def sequence[N[_], B](implicit a: A <:< N[B], t: Traverse[M], n: Applicative[N]): N[M[B]] =
    traverse((z: A) => (z: N[B]))

sequence is defined on applicatives that works for monadic structures as well ..

Monads are more restrictive than applicatives. But there are quite a few use cases where you need to have a monad and NOT an applicative. One such use case is when you would like to change the sequence of an effectful computation depending on a previous outcome.

A use case for monads

Have a look at the function ifM (monadic if) defined in scalaz ..

// executes the true branch of ifM
scala> true.some ifM(none[Int], 4.some)
res8: Option[Int] = None

Here's how ifM is defined ..

def ifM[B](t: => M[B], f: => M[B])(implicit a: Monad[M], b: A <:< Boolean): M[B] = 
  >>= ((x: A) => if (x) t else f)

It uses the monadic bind that can influence a subsequent computation depending on the outcome of a previous computation.

(>>=) :: m a -> (-> m b) -> m b

Now consider the same computation implemented using an applicative ..

scala> val ifA = (b: Boolean) => (t: Int) => (f: Int) => (if (b) t else f)            
ifA: (Boolean) => (Int) => (Int) => Int = <function1>

// good!
scala> none <*> (some(12) <*> (some(false) map ifA)) 
res41: Option[Int] = None

// bad!
scala> none <*> (some(12) <*> (some(true) map ifA)) 
res42: Option[Int] = None

<*> just sequences the effects through all computation structures - hence we get the last effect as the return value which is the one for the else branch. Have a look at the last snippet where even though the condition is true, we have the else branch returned.

(<*>) :: f(-> b) -> f a -> f b

So <*> cannot change the structure of the computation which remains fixed - it just sequences the effects through the chain.

Monads are the correct way to model your effectful computation when you would like to control the structure of computation depending on the context.

A use case for applicatives

scalaz implements Validation as an applicative functor. This is because here we need to accumulate all the effects that the validation can produce. As I noted in my last post on composing abstractions in scalaz, the following snippet will accumulate all validation errors before bailing out .. quite unlike a monadic API ..

def makeTrade(account: Account, instrument: Instrument, refNo: String, market: Market, 
  unitPrice: BigDecimal, quantity: BigDecimal) =
  (validUnitPrice(unitPrice).liftFailNel |@| 
    validQuantity(quantity).liftFailNel) { (u, q) => Trade(account, instrument, refNo, market, u, q) }

Let's look into it in a bit more detail ..

sealed trait Validation[+E, +A] {

final case class Success[E, A](a: A) extends Validation[E, A]
final case class Failure[E, A](e: E) extends Validation[E, A]

Note in case of success only the actual computation value gets propagated, as in the following ..

trait Validations {
  def success[E, A](a: A): Validation[E, A] = Success(a)
  def failure[E, A](e: E): Validation[E, A] = Failure(e)

With a monadic bind, the computation will be aborted on the first error as we don't have the computation value to be passed to the second argument of >>=. Applicatives allow us to sequence through the computation chain nicely and accumulate all the effects. Hence we can get effects like ..

// failure case
scala> makeTrade("a-123", "google", "ref-12", Singapore, -10, 600)
res2: scalaz.Validation[scalaz.NonEmptyList[String],] = 
  Failure(NonEmptyList(price must be > 0, qty must be <= 500))

One other interesting abstraction to manipulate computation structures is an Arrow, which makes an interesting comparison with Applicative Functors. But that's for some other day, some other post ..

No comments: