Target audience: Advanced

Estimated reading time: 30'

I assume that the reader is either familiar with the theory behind Categories, Functors & Monads. If not, one of my older posts, Monads & Functors: Theory , should provide some understanding behind those concepts.

In the previous post we introduced a

- A

- A

- A

*Monad*as a structure or triple*M = <T,eta,mu>*on a category X consists of- A

*map*: applicative functor from category X to category Y) T : X->Y- A

*unit*: natural transformation eta: 1 -> T- A

*join*: multiplication or natural transformation mu: T*T -> T

**Note**: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omittedLet's implement these monadic operators in Scala for some collections.

trait Monad[M[_]] { def map[X,Y](f: X=>Y): M[X] => M[Y] def unit[X](x: X): M[X] def join[X](mu: M[M[X]]): M[X] }

The

**map**method implements the natural transformation, phi. The**unit**method create a target category from an element (i.e. Double -> List[Double]). The**join**method enforces the mu natural transformation.

Monads and Collections

Let's use the List<Int> structured introduced in the post related to the theory of Monads ( Monads & Functors: Theory).

flatMap

For-comprehension

or using the

References

Let's use the List<Int> structured introduced in the post related to the theory of Monads ( Monads & Functors: Theory).

val monadList = new Monad[List] { override def map[X,Y](f: X=>Y): List[X] => List[Y]= (xs: List[X]) => xs.map(f) override def unit[X](x: X): List[X] = x :: Nil override def join[X](xs: List[List[X]]): List[X] = xs.flatten }

The class MonadList is a wrapper around the List Monad. Therefore it is easy to implement all those 3 methods using the method of

*scala.collection.immutable.List*class:- map: build a new list by applying the function f to all elements of the orginal list:
*x -> x*x => List(.. x ..) -> List( .. x*x ...)* - :: nill: create a single element list
- flatten: Converts this list of lists into a List formed by concatenating the element of all the contained lists.

Let's consider X, Y be the category (or type) Int. The Monad can be applied to list of Integers

val xs = monadList.map((n: Int) => n * n) xs(List(4, 11, 6)).foreach( println ) val xss : List[List[Int]] = List( List(3,5,6), List(11,34,12,66)) monadList.join[Int](xss).foreach ( println)

In the example above, the execution of the first foreach method will print '16, 121, 36' while the second foreach invocation generate the sequence '3,5,6,11,34,12,66'.

The same methodology is applied to immutable sequences by implementing the generic

The same methodology is applied to immutable sequences by implementing the generic

*Monad*trait.import scala.collection.immutable.Seq class MonadSeq[Y] extends Monad[Seq] { override def map[X,Y](f: X=>Y): Seq[X] => Seq[Y] = (_x: Seq[X]) => _x.map(f) override def unit[X](x: X): Seq[X] = Seq[X](x) override def join[X](__x: Seq[Seq[X]]): Seq[X] = __x.flatten }

The implementation of the monad for immutable sequence is very similar to the monad for immutable lists: the map method relies on the

*Seq.map*method and the join method flattens a 2-dimensional sequence into a single sequenceflatMap

The Scala standard libraries uses monads for collections, options and exceptions handling. The standard library uses a slightly different but equivalent methods to implement the three basic functionality of a monad.

*apply*instead of*unit**flatMap*uses the transformation**f: T -> M[T]**instead of the "flattening"*join*

trait _Monad[M[_]] { def map[T, U](m: M[T])(f: T =>U): M[U] = flatMap(m)((t: T) => apply(f(t))) def apply[T](t: T): M[T] def flatMap[T, U](m: M[T])(f: T =>M[U]): M[U] }

Let's use the Monad template above, to create a monad for time series. A time series of type

The monad can be defined as an implicit class.

*TS*is defined as a sequence of indexed observations (*Obs*. An observation has an index (or sequence ordering) and a value of type T.The monad can be defined as an implicit class.

case class Obs[T](val t: Int, val features: T) case class TS[T](val data: List[Obs[T]]) implicit class TS2Monad[T](ts: TS[T]) { def apply(t: T): TS[T] = TS[T](List[Obs[T]](Obs[T](0, t))) def map[U](f: T => U): TS[U] = TS[U](ts.data.map(obs => Obs[U](obs.t, f(obs.features)))) def flatMap[U](f: T =>TS[U]): TS[U] = TS[U]( (ts.data.map(obs => f(obs.features).data)).flatten) }

The monad is ready for transforming time series by applying the implicit conversion of a time series of type

*TS*to its monadic representation.val obsList = List.tabulate(10)(new Obs(_, Random.nextDouble)) val ts = new TS[Double](obsList) import _Monad._ val newTs = ts.map( _*2.0)

For-comprehension

Like many other functional languages, Scala embellish the syntax (sugar coated) . The Scala language combines join and unit methods to produce the Monad external shape method

*map*and*flatMap*method as defined as*def map(f: A => B): M[B]**def flatMap(f: A => M[B]): M[B]*- map applies a natural transformation of the content structure
- flatMap composes the Monad with an operation f to generate another Monad instance of the same type.

The syntax to implement the following sequence of operations of concatenation of 3 arrays can be expressed using the methods map -> flatMap associated with the Scala collections (List, Array, Map...)

val sum2 = array1 flatMap { x => array2 flatMap { y => array3 map { z => x+y+z } } }

or using the

**For-Yield**idiom, which is easier to write and understand.val sum : Array[Int] = for { x <- array1 y <- array2 z <- array3 } yield x+y+

References

There is absolutely no reason to have ClassTag in the definition. It is an error and should be removed.

ReplyDeleteRight. Corrected. ClassTag would be required for Array[T] which is invariant.

ReplyDelete