Monday, November 22, 2010

Exploring scalaz

I have been playing around with Scalaz for a couple of weekends now. Scalaz brings to Scala some generic functions and abstractions that are not there in the current Scala API. These are mostly *functional* higher order structures that Haskell boasts as being part of their standard distribution. Using Scalaz you can write Scala code in applicative style that often come out as being more expressive than the imperative one.

Functors, applicatives, arrows, monads and many such abstractions form part of the Scalaz repertoire. It’s no wonder that using Scalaz needs a new way of thinking on your part than is with standard Scala. You need to think more like as if you’re modeling in Haskell rather than in any object-oriented language.

Typeclasses are the cornerstone of Scalaz distribution. Instead of thinking polymorphically in inheritance hierarchies, think in terms of designing APIs for the open world using typeclasses. Scalaz implements the Haskell hierarchy of typeclasses - Functors, Pointed, Applicative, Monad and the associated operations that come with them.

How is this different from the normal way of thinking ? Let’s consider an example from the current Scala point of view.

We say that with Scala we can design monadic abstractions. flatMap is the bind which helps us glue abstractions just like you would do with >>= of Haskell. But does the Scala standard library really have a monad abstraction ? No! If it had a monad then we would have been able to abstract over it as a separate type and implement APIs like sequence in Haskell ..

sequence :: Monad m => [m a] -> m [a]

We don’t have this in the Scala standard library. Consider another example of a typeclass, Applicative, which is defined in Haskell as

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (-> b) -> f a -> f b

Here pure lifts a into the effectful environment of the functor, while (<*>) takes a function from within the functor and applies it over the values of the functor. Scalaz implements Applicative in Scala, so that you can write the following:

scala> import scalaz._
import scalaz._

scala> import Scalaz._
import Scalaz._

scala> List(10, 20, 30) <*> (List(1, 2, 3) map ((_: Int) * (_: Int)).curried)
res14: List[Int] = List(10, 20, 30, 20, 40, 60, 30, 60, 90)

Here we have a pure function that multiplies 2 Ints. We curry the function and partially apply to the members of the List(1, 2, 3). Note List is an instance of Applicative Functor. Then we get a List of partial applications. Finally <*> takes that List and applies to every member of List(10, 20, 30) as a cartesian product. Of course the Haskell variant is much less verbose ..

(*) <$> [1, 2, 3] <*> [10, 20, 30]

and this is due to better type inference and curry by default strategy of function application.

You can get a more succinct variant in Scalaz using the |@| combinator ..

scala> List(10, 20, 30) |@| List(1, 2, 3) apply (* _)
res17: List[Int] = List(10, 20, 30, 20, 40, 60, 30, 60, 90)

You can have many instances of Applicatives so long you implement the contract that the above definition mandates. Typeclasses give you the option to define abstractions for the open world. Like List, there are many other applicatives implemented in Scalaz like options, tuples, function applications etc. The beauty of this implementation is that you can abstract over them in a uniform way through the power of the Scala type system. Just like List, you can apply <*> over options as well ..

scala> some(10) <*> (some(20) map ((_: Int) * (_: Int)).curried)
res18: Option[Int] = Some(200)

And since all Applicatives can be abstracted over without looking at the exact concrete type, here’s one that mixes an option with a function application through <*> ..

scala> some(9) <*> some((_: Int) + 3)
res19: Option[Int] = Some(12)

The Haskell equivalent of this one is ..

Just (+3) <*> Just 9

Scalaz uses two features of Scala to the fullest extent - higher kinds and implicits. The entire design of Scalaz is quite unlike the usual Scala based design that you would encounter elsewhere. Sometimes you will find these implementations quite opaque and verbose. But most of the verbosity comes from the way we encode typeclasses in Scala using implicits. Consider the following definition of map, which is available as a pimp defined in the trait MA ..

sealed trait MA[M[_], A] extends PimpedType[M[A]] {
  import Scalaz._
  def map[B](f: A => B)(implicit t: Functor[M]): M[B] = //..

map takes a pure function (f: A => B) and can be applied on any type constructor M so long it gets an instance of a Functor[M] in its implicit context. Using the trait we pimp the specific type constructor with the map function.

Here are some examples of using applicatives and functors in Scalaz. For fun I had translated a few examples from Learn You a Haskell for Great Good. I also mention the corresponding Haskell version for each of them ..

// pure (+3) <*> Just 10 << from lyah
10.pure[Option] <*> some((_: Int) + 3) should equal(Some(13))

// pure (+) <*> Just 3 <*> Just 5 << lyah
// Note how pure lifts the function into Option applicative
// scala> p2c.pure[Option]
// res6: Option[(Int) => (Int) => Int] = Some(<function1>)

// scala> p2c
// res7: (Int) => (Int) => Int = <function1>
val p2c = ((_: Int) * (_: Int)).curried
some(5) <*> (some(3) <*> p2c.pure[Option]) should equal(Some(15))

// none if any one is none
some(9) <*> none should equal(none)

// (++) <$> Just "johntra" <*> Just "volta" << lyah
some("volta") <*> (some("johntra") map (((_: String) ++ (_: String)).curried)) 
  should equal(Some("johntravolta"))

// more succinct
some("johntra") |@| (some("volta") apply (++ _) should equal(Some("johntravolta"))

Scalaz is mind bending. It makes you think differently. In this post I have only scratched the surface and talked about a couple of typeclasses. But the only way to learn Scalaz is to run through the codebase. It's dense but if you like functional programming you will get lots of aha! moments going through it.

In the next post I will discuss how I translated part of a domain model of a financial trade system which I wrote in Haskell (Part 1, Part 2 and Part 3) into Scalaz. It has been a fun exercise for me and shows how you can write your Scala code in an applicative style.

Monday, November 01, 2010

Domain Modeling in Haskell - Applicative Functors for Expressive Business Rules

In my last post on domain modeling in Haskell, we had seen how to create a factory for creation of trades that creates Trade from an association list. We used monadic lifts (liftM) and monadic apply (ap) to chain our builder that builds up the Trade data. Here's what we did ..

makeTrade :: [(String, Maybe String)] -> Maybe Trade
makeTrade alist =
    Trade `liftM` lookup1 "account"                      alist
             `ap` lookup1 "instrument"                   alist
             `ap` (read `liftM` (lookup1 "market"        alist))
             `ap` lookup1 "ref_no"                       alist
             `ap` (read `liftM` (lookup1 "unit_price"    alist))
             `ap` (read `liftM` (lookup1 "quantity"      alist))

lookup1 key alist = case lookup key alist of
                      Just (Just s@(_:_)) -> Just s
                      _ -> Nothing

Immediately after the post, I got some useful feedback on Twitter suggesting the use of applicatives instead of monads. A Haskell newbie, that I am, this needed some serious explorations into the wonderful world of functors and applicatives. In this post let's explore some of the goodness that applicatives offer, how using applicative style of programming encourages a more functional feel and why you should always use applicatives unless you need the special power that monads offer.

Functors and Applicatives

In Haskell a functor is a typeclass defined as

class Functor f where
  fmap :: (-> b) -> f a -> f b

fmap lifts a pure function into a computational context. For more details on functors, applicatives and all of typeclasses, refer to the Typeclassopedia that Brent Yorgey has written. In the following text, I will be using examples from our domain model of securities trading. After all, I am trying to explore how Haskell can be used to build expressive domain models with a very popular domain at hand.

Consider the association list rates from our domain model in my last post, which stores pairs of tax/fee and the applicable rates as percentage on the principal.

*Main> rates

We would like to increase all rates by 10%. fmap is our friend here ..

*Main> fmap (\(tax, amount) -> (tax, amount * 1.1)) rates

This works since List is an instance of the Functor typeclass. The anonymous function gets lifted into the computational context of the List data type. But the code looks too verbose, since we have to destructure the tuple within the anonymous function and thread the increment logic manually within it. We can increase the level of abstraction by making the tuple itself a functor. In fact it's so in Haskell and the function gets applied to the second component of the tuple. Here's the more idiomatic version ..

*Main> ((1.1*) <$>) <$> rates

Note how we lift the function across 2 levels of functors - a list and within that, a tuple. fmap does the magic! The domain model becomes expressive through the power of Haskell's higher level of abstractions.

Applicatives add more power to functors. While functors lift pure functions, with applicatives you can lift functions from one context into another. Here's how you define the Applicative typeclass.

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (-> b) -> f a -> f b

Note pure is the equivalent of a return in monads, while <*> equals ap.

Control.Applicative also defines a helper function <$>, which is basically an infix version of fmap. The idea is to help write functions in applicative style.

(<$>) :: Applicative f => (-> b) -> f a -> f b

Follow the types and see that f <$> u is the same as pure f <*> u.

Note also the following equivalence of fmap and <$> ..

*Main> fmap (+3) [1,2,3,4]

*Main> (+3) <$> [1,2,3,4]

Using the applicative style our makeTrade function becomes the following ..

makeTrade :: [(String, Maybe String)] -> Maybe Trade
makeTrade alist =
    Trade <$> lookup1 "account"                   alist
             <*> lookup1 "instrument"             alist
             <*> (read <$> (lookup1 "market"      alist))
             <*> lookup1 "ref_no"                 alist
             <*> (read <$> (lookup1 "unit_price"  alist))
             <*> (read <$> (lookup1 "quantity"    alist))

Can you figure out how the above invocation works ? As I said before, follow the types ..

Trade is a pure function and <$> lifts Trade onto the first invocation of lookup1, which is a Maybe functor. The result is another Maybe, which BTW is an Applicative functor as well. Then the rest of the chain continues through partial application and an applicative lifting from one context to another.

Why choose Applicatives over Monads ?

One reason is that there are more applicatives than monads. Monads are more powerful - using (>>=) :: (Monad m) => m a -> (a -> m b) -> m b you can influence the structure of your overall computation, while with applicatives your structure remains fixed. You only get sequencing of effects with an applicative functor. As an exercise try exploring the differences in the behavior of makeTrade function implemented using monadic lifts and applicatives when lookup1 has some side-effecting operations. Conor McBride and Ross Paterson has a great explanation in their functional pearl paper Applicative Programming with Effects. Applicatives being more in number, you have more options of abstracting your domain model.

In our example domain model, suppose we have the list of tax/fees and the list of rates for each of them. And we would like to build our rates data structure. ZipList applicative comes in handy here .. ZipList is an applicative defined as follows ..

instance Applicative ZipList where  
  pure x = ZipList (repeat x)  
  ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)  

*Main> getZipList $ (,) <$> ZipList [TradeTax, Commission, VAT] <*> ZipList [0.2, 0.15, 0.1]

ZipList is an applicative and NOT a monad.

Another important reason to choose applicatives over monads (but only when possible) is that applicatives compose, monads don't (except for certain pairs). The McBride and Paterson paper has lots of discussions on this.

Finally programs written with applicatives often have a more functional feel than some of the monads with the do notation (that has an intrinsically imperative feel). Have a look at the following snippet which does the classical do-style first and then follows it up with the applicative style using applicative functors.

-- classical imperative IO
notice = do
  trade <- getTradeStr
  forClient <- getClientStr
  putStrLn $ "Trade " ++ trade ++ forClient

-- using applicative style
notice = do
  details <- (++) <$> getTradeStr <*> getClientStr
  putStrLn $ "Trade " ++ details

McBride and Paterson has the final say on how to choose monads or applicatives in your design .. "The moral is this: if you’ve got an Applicative functor, that’s good; if you’ve also got a Monad, that’s even better! And the dual of the moral is this: if you want a Monad, that’s good; if you only want an Applicative functor, that’s even better!"

Applicative Functors for Expressive Business Rules

As an example from our domain model, we can write the following applicative snippet for calculating the net amount of a trade created using makeTrade ..

*Main> let trd = makeTrade [("account", Just "a-123"), ("instrument", Just "IBM"), 
                   ("market", Just "Singapore"), ("ref_no", Just "r-123"), 
                   ("unit_price", Just "12.50"), ("quantity", Just "200" )]
*Main> netAmount <$> enrichWith . taxFees . forTrade <$> trd
Just 3625.0

Note how the chain of functions get lifted into trd (Maybe Trade) that's created by makeTrade. This is possible since Maybe is an applicative functor. The beauty of applicative functors is that you can abstract this lifting into any of them. Let's lift the chain of invocation into a list of trades generating a list of net amount values for each of them. Remember List is also another applicative functor in Haskell. For a great introduction to applicatives and functors, go read Learn Yourself a Haskell for Great Good.

*Main> (netAmount <$> enrichWith . taxFees . forTrade <$>) <$> [trd2, trd3]
[Just 3625.0,Just 3375.0]

Look how we have the minimum of syntax with this applicative style. This makes business rules very expressive and not entangled into a maze of accidental complexity.