tag:blogger.com,1999:blog-19767743413927064202024-02-20T02:15:39.726-08:00Lambdas And StuffFunctional programming and related topics. If you see code, it's most likely Scala.Anonymoushttp://www.blogger.com/profile/03938130182886729096noreply@blogger.comBlogger1125tag:blogger.com,1999:blog-1976774341392706420.post-16474699495085080902017-04-25T03:58:00.002-07:002017-08-30T03:38:44.878-07:00Monads as Applicatives<div style="line-height: normal; min-height: 14px;">
<br />
Applicative functor (or just "applicative" in short) is a more general abstraction than a monad; in other words, monad is an applicative with some extra functionality. However, despite being conceptually present, applicative's functions are rarely explicitly exposed in a monad. Let's try to do that manually.<br />
<br />
Applicative can be expressed as: </div>
<ul>
<li><i>unit + apply </i></li>
<li><i>unit + map2 </i></li>
<li><i>unit + map + product </i></li>
</ul>
<div style="margin-top: 20px;">
with <i>apply</i> and <i>product</i> being the popular ones (in scalaz library they are known as <span style="font-family: "courier new" , "courier" , monospace;"><*></span> and <span style="font-family: "courier new" , "courier" , monospace;">|@|</span>). By using an applicative functor instead of the non-applicative one, we can map by using multi-parameter curried functions (either by applying curried parameters one by one with <i>apply</i> or by lifting everything into a <i>product</i> and mapping on that).</div>
<br />
So now we want to see how can both <i>apply</i> and <i>product</i> be implemented by using monad's operations <i>map</i> and <i>flatten</i> (we won't be needing <i>unit</i>; also, note that other than <i>unit + map + flatten</i>, monad can also be expressed as <i>unit + flatMap</i> and <i>unit + compose</i>).<br />
<br />
Let's say we have the following definition of a monad in Scala (as announced, unit was omitted for brevity):<br />
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; hyphens: none; line-height: 1.5; margin-bottom: 20px; margin-top: 20px; overflow: auto; padding: 1em; tab-size: 4; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: x-small;"><span style="background-color: transparent;">trait </span><span style="background-color: transparent;">Monad[</span><span style="background-color: transparent;">F</span><span style="background-color: transparent;">[_]] {
</span><span style="background-color: transparent;"> def </span><span style="background-color: transparent;">map[</span><span style="background-color: transparent;">A</span><span style="background-color: transparent;">, </span><span style="background-color: transparent;">B</span><span style="background-color: transparent;">](fa: </span><span style="background-color: transparent;">F</span><span style="background-color: transparent;">[</span><span style="background-color: transparent;">A</span><span style="background-color: transparent;">], f: </span><span style="background-color: transparent;">A </span><span style="background-color: transparent;">=> </span><span style="background-color: transparent;">B</span><span style="background-color: transparent;">): </span><span style="background-color: transparent;">F</span><span style="background-color: transparent;">[</span><span style="background-color: transparent;">B</span><span style="background-color: transparent;">] = </span><span style="background-color: transparent;">???</span><span style="background-color: transparent;">
</span><span style="background-color: transparent;"> def </span><span style="background-color: transparent;">flatten[</span><span style="background-color: transparent;">A</span><span style="background-color: transparent;">](fa: </span><span style="background-color: transparent;">F</span><span style="background-color: transparent;">[</span><span style="background-color: transparent;">F</span><span style="background-color: transparent;">[</span><span style="background-color: transparent;">A</span><span style="background-color: transparent;">]]): </span><span style="background-color: transparent;">F</span><span style="background-color: transparent;">[</span><span style="background-color: transparent;">A</span><span style="background-color: transparent;">] = </span><span style="background-color: transparent;">???
}</span></span></pre>
<div style="line-height: normal; min-height: 14px;">
Applicative's methods can then be implemented as:<br />
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; line-height: 1.5; margin-bottom: 20px; margin-top: 20px; overflow: auto; padding: 1em; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: x-small;">trait Monad2[F[_]] extends Monad[F] {
def apply[A, B](fa: F[A], fab: F[A => B]): F[B] =<span style="background-color: transparent;">
</span> flatten(map(fab, (f: A => B) => map(fa, f)))
def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
flatten(map(fa, (a: A) => map(fb, (b: B) => (a,b))))
}</span></pre>
</div>
<span style="font-family: inherit;">Here's an example of using apply with a curried function. I will provide a concrete implementation of apply for List just for simplicity.</span><br />
<div style="line-height: normal; min-height: 14px;">
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; line-height: 1.5; margin-bottom: 20px; margin-top: 20px; overflow: auto; padding: 1em; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="font-family: "courier new" , "courier" , monospace; font-size: x-small;">def apply[A, B](list: List[A], f: List[A => B]): List[B] = f.flatMap(f => list.map(f))
val curriedF = (a: Int) => (b: Int) => (c: Int) => a + b + c
val list1 = List(1)
val list2 = List(2)
val list3 = List(3)
val result1 = apply(list1, List(curriedF))
val result2 = apply(list2, result1)
val result3 = apply(list3, result2)
result3 // List(6)</span></pre>
</div>
<span style="font-family: inherit;"></span>
<span style="font-family: inherit;">The usage is the same as in applicative case. However, there's a significant difference - if <i>apply</i> is implemented using a <i>flatMap</i>, we are taking advantage of monad's power to chain things into series. Standard <i>apply</i> and <i>product</i> from applicative lack this ability.<br /><br />Let's show this difference in practice. Since we were working with <i>apply</i> in the previous example, let's take <i>product</i> now. We can provide two different implementations: one using monadic functions and another one in standard applicative fashion (we can use standard Scala's <i>zip</i>):</span>
<br />
<div style="line-height: normal;">
<div style="-webkit-text-stroke-width: 0px; font-style: normal; font-variant-caps: normal; font-variant-ligatures: normal; font-weight: normal; letter-spacing: normal; line-height: normal; min-height: 14px; orphans: 2; text-align: start; text-decoration-color: initial; text-decoration-style: initial; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">
<div style="font-family: menlo;">
<div style="line-height: normal; min-height: 14px;">
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; line-height: 1.5; margin: 20px 0px 20px; overflow: auto; padding: 1em; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: x-small;">// we'll need these throughout the example
import scala.concurrent.{Await, Future}
import scala.concurrent.duration._
import scala.concurrent.ExecutionContext.Implicits.global
// monad version
def product1[A, B](f1: => Future[A], f2: => Future[B]): Future[(A, B)] = f1.flatMap(a => f2.map(b => (a, b)))
// applicative version
def product2[A, B](f1: => Future[A], f2: => Future[B]): Future[(A, B)] = f1 zip f2</span></pre>
</div>
</div>
</div>
Note that both are taking their parameters by-name instead of by-value in order to prevent futures from executing as soon as they are passed.<br />
<br />
Let's now create the futures:</div>
<div style="line-height: normal;">
<div>
<div style="line-height: normal; min-height: 14px;">
<div style="font-family: menlo;">
<div style="line-height: normal; min-height: 14px;">
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; line-height: 1.5; margin-bottom: 20px; margin-top: 20px; overflow: auto; padding: 1em; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: x-small;">def first = Future { println("first"); Thread.sleep(2000); 1 }
def second = Future { println("second"); Thread.sleep(2000); 2 }</span></pre>
</div>
</div>
</div>
</div>
Using serial product, we get:<br />
<div style="line-height: normal; min-height: 14px;">
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; line-height: 1.5; margin-bottom: 20px; margin-top: 20px; overflow: auto; padding: 1em; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="font-family: "courier new" , "courier" , monospace;"><span style="font-size: x-small;"><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: xx-small;">/</span><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: xx-small;">/ prints "first", then two seconds later "second"
val result1 = product1(first, second).map { case (a, b) => a + b }
</span></span><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: x-small;">Await.result(result1, 10 seconds)</span></span></pre>
</div>
</div>
<span style="font-family: inherit;">Using parallel product, we get:</span>
<br />
<div style="line-height: normal; min-height: 14px;">
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; line-height: 1.5; margin: 20px 0px 20px; overflow: auto; padding: 1em; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: x-small;">// performs in parallel; order of printing is indeterministic
val result2 = product2(first, second).map { case (a, b) => a + b }
Await.result(result2, 10 seconds)</span></pre>
</div>
Finally, the scalaz version:<br />
<pre class=" language-java" style="background: rgb(249, 249, 250); border: 1px solid rgba(51, 51, 51, 0.0980392); box-sizing: border-box; direction: ltr; line-height: 1.5; margin-bottom: 20px; margin-top: 20px; overflow: auto; padding: 1em; text-shadow: rgb(255, 255, 255) 0px 1px; word-break: normal; word-wrap: normal;"><span style="color: #666666; font-family: "courier new" , "courier" , monospace; font-size: x-small;">import scalaz._, Scalaz._
// "first" and "second" are printed simultaneously
val result3 = (first |@| second) { case (a, b) => a + b }
Await.result(result3, 10 seconds)</span></pre>
While monad as a generic data structure could have methods such as apply or product exposed in its API, it probably doesn't make a lot of sen<span style="font-family: inherit;">se. Still, if one needs them, we have seen here that they can be easily implemented in terms of existing monad functions. Note that even if their signatures are the same as applicative's, we have also seen that monad's power - ability to chain computations in series - is still present and at disposal, if desired. In this particular example we could force the product implemented with <i>flatMap</i> to behave the same as the parallel one by simply going from by-name to by-value invocation (by removing the => from each parameter type). This way each future is evaluated as soon as it is passed to <i>product</i>.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">As tempting as it may feel to implement a single "swiss army" abstraction and equip it with <i>unit, map, map2, flatMap, apply, product, compos</i>e etc. it's important to remember that best practice is to always use the least powerful abstraction that does the job. If you need <i>apply</i> or <i>product</i> (meaning you have more than one operation, which is a stronger requirement than what a non-applicative functor can give you, but they don't depend on each other, which is a weaker requirement than what a monad would give you) your abstraction of choice should be the applicative functor.</span><br />
<span style="font-family: inherit;"><br /></span>
<br />
<div>
<span style="font-family: inherit;"><br /></span>
<br />
<div style="line-height: normal; min-height: 14px;">
<br /></div>
</div>
Anonymoushttp://www.blogger.com/profile/03938130182886729096noreply@blogger.com0