λ Tony’s blog λ

Monad exercises in Scala

A result of discussion in the #scala IRC channel.

A colleague has asked me to convert this to Haskell, which I have done below.

The trait Monad answers the question “What does monad mean?”
The object Monad answers the question “What are some examples?”
The object MonadicFunctions answers the question “What are the practical implications?”

If there are any questions or you get stuck, the #scala or #scalaz channel on Freenode could help out.

// 1. Start here. Observe this trait
trait Monad[M[_]] {
  def flatMap[A, B](a: M[A], f: A => M[B]): M[B]
  def unital[A](a: A): M[A]
}
 
// A simple data type, which turns out to satisfy the above trait
case class Inter[A](f: Int => A)
 
// So does this.
case class Identity[A](a: A)
 
// Monad implementations
object Monad {
  // 2. Replace error("todo") with an implementation
  def ListMonad: Monad[List] = error("todo")
 
  // 3. Replace error("todo") with an implementation
  def OptionMonad: Monad[Option] = error("todo")
 
  // 4. Replace error("todo") with an implementation
  def InterMonad: Monad[Inter] = error("todo")
 
  // 5. Replace error("todo") with an implementation
  def IdentityMonad: Monad[Identity] = error("todo")
}
 
object MonadicFunctions {
  // 6. Replace error("todo") with an implementation
  def sequence[M[_], A](as: List[M[A]], m: Monad[M]): M[List[A]] =
    error("todo")
 
  // 7. Replace error("todo") with an implementation
  def fmap[M[_], A, B](a: M[A], f: A => B, m: Monad[M]): M[B] =
    error("todo")
 
  // 8. Replace error("todo") with an implementation
  def flatten[M[_], A](a: M[M[A]], m: Monad[M]): M[A] =
    error("todo")
 
  // 9. Replace error("todo") with an implementation
  def apply[M[_], A, B](f: M[A => B], a: M[A], m: Monad[M]): M[B] =
    error("todo")
 
  // 10. Replace error("todo") with an implementation
  def filterM[M[_], A](f: A => M[Boolean], as: List[A]
    , m: Monad[M]): M[List[A]] =
    error("todo")
 
  // 11. Replace error("todo") with an implementation
  def replicateM[M[_], A](n: Int, a: M[A], m: Monad[M]): M[List[A]] =
    error("todo: flatMap n times to produce a list")
 
  // 12. Replace error("todo") with an implementation
  def lift2[M[_], A, B, C](f: (A, B) => C, a: M[A], b: M[B]
    , m: Monad[M]): M[C] =
    error("todo")
 
  // lift3, lift4, etc. Interesting question: Can we have liftN?
}

Haskell

The data Monad' answers the question “What does monad mean?”
The functions under *** Monad implementations *** answers the question “What are some examples?”
The functions under *** Monadic Functions *** answers the question “What are the practical implications?”

{-# LANGUAGE RankNTypes #-}
 
-- 1. Start here. Observe this data type
data Monad' m = Monad' {
  unital :: forall a. a -> m a,
  flatMap :: forall a b. m a -> (a -> m b) -> m b
}
 
-- A simple data type, which turns out to satisfy the above trait
newtype Inter a = Inter { f :: Int -> a }
 
-- So does this.
newtype Identity a = Identity { a :: a }
  deriving Show
 
-- *** Monad implementations ***
 
-- 2. Replace error "todo" with an implementation
listMonad :: Monad' []
listMonad = error "todo"
 
-- 3. Replace error "todo" with an implementation
maybeMonad :: Monad' Maybe
maybeMonad = error "todo"
 
-- 4. Replace error "todo" with an implementation
interMonad :: Monad' Inter
interMonad = error "todo"
 
-- 5. Replace error "todo" with an implementation
identityMonad :: Monad' Identity
identityMonad = error "todo"
 
-- *** Monadic functions ***
 
-- 6. Replace error "todo" with an implementation
sequence' :: [m a] -> Monad' m -> m [a]
sequence' = error "todo"
 
-- 7. Replace error "todo" with an implementation
fmap' :: m a -> (a -> b) -> Monad' m -> m b
fmap' = error "todo"
 
-- 8. Replace error "todo" with an implementation
flatten :: m (m a) -> Monad' m -> m a
flatten = error "todo"
 
-- 9. Replace error "todo" with an implementation
apply :: m (a -> b) -> m a -> Monad' m -> m b
apply = error "todo"
 
-- 10. Replace error "todo" with an implementation
filterM' :: (a -> m Bool) -> [a] -> Monad' m -> m [a]
filterM' = error "todo"
 
-- 11. Replace error "todo" with an implementation
replicateM' :: Int -> m a -> Monad' m -> m [a]
replicateM' = error "todo: flatMap n times to produce a list"
 
-- 12. Replace error "todo" with an implementation
lift2 :: (a -> b -> c) -> m a -> m b -> Monad' m -> m c
lift2 = error "todo"
 
-- lift3, lift4, etc. Interesting question: Can we have liftN?

This entry was posted on Thursday, March 25th, 2010 at 11:42 am and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

17 Responses to “Monad exercises in Scala”

Joshua Suereth Says:
March 26th, 2010 at 3:07 am
How are these different then the intermediate scala excercises? Regardless, great work in engaging folks! You should also hint that scalaz may hold solutions to these and more problems folks may run into with Monads…
Tony Morris Says:
March 26th, 2010 at 6:52 am
Hi Joshua,
These exercises aren’t all that different.

Scalaz includes a comprehensive library of all these functions and many more. How’s that?
sanj Says:
March 26th, 2010 at 11:46 am
Hey Tony,

Thanks for a great post! I’m working through the problems and am getting a much better understanding of Monads.
oxbow Says:
March 26th, 2010 at 10:41 pm
For those monadic functions which have List in them, I presume the objective is to *not* use any methods on List? For example, I assume that to implement filterM I should not being using List.filter? Or am I wrong and is that allowed?

This is making me feel deeply stupid; I just can’t figure out the implementation of sequence. None of the monadic operations let you transform one monad into another so I just don’t understand how one can “flip” M and List (i.e. how can any of the operations remove List as the “outer” monad?)
Tony Morris Says:
March 27th, 2010 at 10:52 am
Hello oxbow, you can use whichever available functions you like. This includes core library functions, any utility functions that you write or those that are specified in the exercises.

Don’t feel stupid. Trust in the fact that you can look back at what you have learned, then help others.

As for “flipping M and List”, I think you’re referring to the sequence function. Try this instead: List[Option[A]] => Option[List[A]]

After you’ve done that, then the sequence function may be a little easier.
uberlazy Says:
March 29th, 2010 at 12:00 am
Think I got them all. I’m not just a FP beginner, but also a Scala beginner, so my solution is bound to be clumsier than it ought to. Still, it was a great learning experience - Tony, thanks for the exercise!

http://paste.pocoo.org/show/194815/
uberlazy Says:
March 29th, 2010 at 12:53 am
PS The obvious mistake is that replicateM should go:

def replicateM[M[_], A](n: Int, a: M[A], m: Monad[M]): M[List[A]] =
sequence((for(_ <- 1 to n) yield a).toList, m)

rather than using for(_ g} can be written as a.f

I’m getting there slowly…
oxbow Says:
March 29th, 2010 at 10:23 pm
Thanks Tony - my current “Friday project” is to understand the Scalaz library. Think I’ve got these in the end, with some help from the mailing List. Didn’t realize I could do stuff like *create* new lists (d’oh!)

Also watched the Nick Partridge video which you posted - very good. I’m not alone in failing to make the leap between some of the scalaz examples and what this looks like in real code. The best “a ha” moment so far was Nick’s explanation of using validation with the methods.

I also watched your “Monad” presentation and you urge people to play around as then they will discover the usages for themselves. I think a worked example of the introduction of some of these concepts to how a “standard Java guy” might write a small program would be really beneficial in this. But keep up the good work
Mark Harris Says:
March 30th, 2010 at 8:17 am
I worked on the Haskell version of this challenge off and on over the weekend, and after losing most of it trying to make head or tail of Inter, finally ploughed through 4-11 in an hour or so tonight. Thank you for an interesting couple of days.

12, however, has me in a bit of a quandry. Hopefully, the type signature should be:

lift2 :: Monad’ m -> (a -> b -> c) -> m a -> m b -> m c

Otherwise, any hints would be gratefully received.
Tony Morris Says:
March 30th, 2010 at 9:16 am
Hi Mark, You’re right. Thanks for the correction.
λ Tony’s blog λ » Blog Archive » Monad Exercises in Scala (addendum) Says:
April 3rd, 2010 at 3:45 pm
[...] harness that should print a series of PASS when executed against a correct solution to the original Monad Exercises in Scala. These exercises include a Haskell version and a test harness for this is also found [...]
Tom Says:
April 7th, 2010 at 5:57 pm
My answers:

http://paste.pocoo.org/show/198673/
Marius Danciu Says:
June 18th, 2010 at 7:55 pm
Hi Tony,

One thing I’m puzzled about

trait Monad[M[_]] {
def flatMap[A, B](a: M[A], f: A => M[B]): M[B]
def unital[A](a: A): M[A]
}

afaik a Monad is a tripple of (endo)functor and two natural transformations (unit and mult). These natural transformations are morphisms between functors (regardless if we represent them as in category theory or as Haskell does) but M[_] is not necessarily a functor. Therefore a call to Monad.flatMap or unital doesn’t really bring us back automatically into the functors space, unless we wrap them again by other monad.

Of course List, Option etc are monadic but for the purpose of generalization I’d appreciate if you could clarify this for me.

I wonder about this form:

trait M[A] {

def map[B](f: A => B) : M[B]
def flatMap[B]( f: A => M[B]): M[B] = mult ( map ( f ) )

def unit(a: A): M[A]
def mult(m: M[M[a]]); M[a]

protected def A get
}

Any thoughts?

Br’s,
Marius
Tony Morris Says:
June 20th, 2010 at 3:27 pm
Hi Marius,
You are right that a Monad can also be represented as:
```
trait Monad[M[_]] extends Functor[M] {
  def unit[A](a: A): M[A]
  def mult(m: M[M[A]]): M[A]
}
```
This would allow you derive flatMap as you have written.

Alternatively, mult can be derived: m => m.flatMap(x => x). I have no particular preference for either representation, though I suspect there are ultimately practical implications. I’d be interested in knowing if this intuition is correct.
Marius Says:
July 1st, 2010 at 12:29 am
Dear Tony,

Thank you very much for your reply! … however my puzzling thing (regardless of representation) is not really about category theory or Haskell representation but rather that M[_] is not necessarily a functor or a monad for that matter. It is just a higher kinded type thus when we compose things we’re not back in the monad’s space that allows us to do further composition unless we wrap it int a Monad either explicitly or using implicit conversions.

In my second example all transformations return an M[T] which must be an Monad M trait refinement thus being easy to see further composition.

Appreciate your thoughts.

Br’s,
Marius
Dominic Bou-Samra Says:
December 18th, 2011 at 9:58 am
This was such a useful exercise for someone super fresh to FP and Scala. I struggled with the InterMonad though.
James Says:
January 7th, 2012 at 3:03 pm
Tardily concurring with Dominic — nice set of exercises, but it may’ve been a touch too frustrating figuring out how to interpret flatMap for InterMonad. It wasn’t clear to me that the integer argument to the “wrapped” function should be repeated … although in retrospect I suppose it seems obvious.

Monad exercises in Scala

17 Responses to “Monad exercises in Scala”

Leave a Reply