What's Ap with zio-prelude?

What's ZIO Prelude

Recently, ZIO creators, John De Goes and Adam Fraser, presented their latest functional programming library to the world. ZIO Prelude, hereafter referred to as Prelude, is promised as a radical shift in the way functional programming is taught, implemented and used. The event was the online edition of the SF Scala meetup, and the talk is now available on YouTube SF Scala: Reimagining Functional Type Classes. You can also visit the source code on Github zio-prelude.

For those that don't know, Prelude was initially developed, I'm told, as part of John De Goes's "Spartan" training program, so I wasn't able to follow it since its inception. I've been looking forward to the release since I heard about it, especially since John has alluded to a new type class encoding for a few years, for example in this talk at flatMap Oslo 2018 https://www.youtube.com/watch?v=sFGnFKMSmL0&t=1462s

In this post I will give my first impressions, having watched the talk and spent a few hours playing around with the library. At this stage, the nascent library is still undergoing rapid changes, so some of what I write here will likely be outdated fairly soon. I'm also new to the library, so if I make any mistakes feel free to contact me and I will correct them.

What's ap with ZIO Prelude?

Prior to the talk John tweeted:

For a decade, 'ap' from Applicative has infected Scala code:

def ap[A, B](f: F[A => B], fa: F[A]): F[B]

Cryptic & confusing, did you know the raison d'être of 'ap' is Haskell's curried functions, not category theory?

Learn how we can do better! - John De Goes

This also piqued my curiosity as I have talked about Applicative publicly quite a bit this year including at online meetups and the Scala Love conference. I also wrote a lengthy blog post on Applicative Programming with Effects.

What's Ap?

John has pointed out before that Ap is not a great ergonomic fit for Scala (currying is much more natural in Haskell). Ap is hard to teach because of this; a lot of Scala developers find currying tricky. It is, however, an important part of the language, and a useful tool for every Scala programmers toolbox.

Later in the post, I will try to reimplement some of my sample code from the What's Ap post, and see how well Prelude replaces Applicative, both from the developer perspective and in terms of how easy each would be to teach.

From this point of view I will be approaching Prelude in a way that it is not designed for; mapping the Haskell style class hierarchy to Prelude. We shouldn't judge it on that basis, but since John threw down the gauntlet I will accept the challenge to defend my friend the Applicative.

Goals of Prelude

As you'll see in the slide deck, the goals of prelude are to be the following:

Radical
Orthogonal
Principled
Scala-First
Minimal
Pragmatic
Accessible
Opinionated

The goals I find most compelling here are accessible and orthogonal. As a functional programming advocate and educator, I am very interested in any steps towards greater accessibility. The orthogonal part is also key, as I believe that composability is one of the biggest wins of pure functional programs.

Algebras, not Category Theory

With Cats, almost all of the concepts come from category theory. We have Monads, Functors, Monoids, Monoidal Functors and so on. The idea with prelude is that algebra is more familiar to us, as non-mathematician programmers than category theory. Algebras are also more composable, so the idea is to start with a small number of primitive things(?) and combining them into more powerful objects.

The big question that prelude puts out there is this; is Category Theory an obstacle to adoption of pure functional programming, and would abstract algebra be a better way to both introduce newcomers, and provide a better solution overall to the problems and applications that Cats et al already address?

Functor and Monad

Functors (Covariant)

In my original post, I introduce Functor and Monad as the gateway to Applicative. Functor is a simple and beautiful thing, in that it allows us to combine pure functions with "effectful" computations, mapping an F[A] to an F[B]. In prelude Functor and Monad do not exist as first-class entities, although we can see them defined as type aliases. This seems to be more documentation than practical as the type aliases are not used anywhere in the code.

type Functor[F[+_]] = Covariant[F]
type Monad[F[+_]] = Covariant[F] with IdentityFlatten[F]

In Cats the Functor type class is short for Covariant Functor. What does that mean? First of all one of the best discussions of covariance in Scala I know can be found here on the scala-lang.org site:

https://docs.scala-lang.org/tour/variances.html

In essence, a covariant type parameter, for example with List[+A], means that you if B is a subtype of A, then List[B] is a subtype of List[A].

The Cats Functor is also covariant in that if you have a function that can map an A to a B, you can map a higher-kinded type F[A] to F[B] too using the Covariant Functor.

In Cats a Functor is defined as a higher-kinded type with a map function. In Prelude a Functor is just something that implements the Covariant type and follows its laws.

Functor has essentially changed names in Prelude, it is on the surface the same as the Cats Functor.

List(1,2,3).map(a => a + 1)
// List[Int] = List(2, 3, 4)
Option(1).map(a => a + 1)
// Option[Int] = Some(2)

There is an excellent post about variance and functors on the Typelevel site:

https://typelevel.org/blog/2016/02/04/variance-and-functors.html

You can take a look at the implementation of Covariant here:

https://github.com/zio/zio-prelude/blob/master/src/main/scala/zio/prelude/Covariant.scala

It's nice that each abstraction, or algebra, has it's own file, and in that file you'll find the following.

A trait defining the interface to the algebra. For example, Covariant defines map and a couple of other functions. In this respect it is similar to Cats.
Laws. The companion object contains the laws to test the algebra directly. Each object has a laws member that can be checked with the package objects checkAllLaws method.
Instances. Rather than have instances in a separate file or package, they are also embedded in the companion. It's nice to have them all easily listed in the same place. Most algebras have instances for some appropriate standard library types, as well as some "ZIO" types like ZIO itself and Chunk and new Prelude types like ZPure which we will get into in a later post. Another thing I like is the code documentation is laid out like this `Covariant` instance for `Chunk` so that if you want to find, say, all the instances for ZIO you can do do a global text search for instance for `ZIO` and you'll find them. This kind of thoughtful ergonomics is much appreciated.
Finally, at the end of the object implememtation you will find some syntax. If you ever struggled with imports in Scalaz and Cats, you may appreciate this one file per algebra layout.

Monads

In Cats we extend Functor with Applicative and add the flatMap operation to get Monad. Applicative brings us both ap and pure. Leaving ap aside for the moment, pure is the important ability to lift a pure value into the context of some effect, represented as a higher-kinded type.

Let's take a look at sequencing two Futures together using prelude. In order to do that with Cats we would use the Monad flatmap operation.

def getUser(email: String): Future[User] = ???

def getAccountStatus(id: String): Future[AccountStatus] = ???

val accountStatus = getUser("bob@google.com")
  .flatMap(user => getAccountStatus(user.accountId))

In prelude you would do the same, since nothing overrides flatMap from ZIO or the standard library, you can simply call flatMap, but you wouldn't be exercising the new algebraic components that make up prelude, stay tuned.

Remember above that Monad is defined as the composition of IdentityFlatten and Covariant. We already saw that Covariant is Functor and provides map (remember that all Monad's are functors).

IdentityFlatten is the composition of prelude types Associative, Identity and Flatten. Flatten is easy it just gives us the ability to flatten an effect from an F[F[A]] to an F[A]. For example, the somewhat contrived code below executes a ZIO that is nested inside another, resulting in a ZIO[ZIO[A]]. We can use the ZIO Flatten instance to flatten and run the effects.

import zio._
val runtime = Runtime.default
val effect = ZIO{putStrLn("Hello!"); ZIO.succeed(10)}
runtime.unsafeRun(effect.flatten)
// Hello!
// Int = 10

Whilst most types, including ZIO effects, Future, Option and List all have flatMap, we could define it in terms of Covariant and IdentityFlatten as follows.

def flatMap[F[+_]: Covariant : IdentityFlatten, A, B](fa: F[A])(fab: A => F[B]): F[B] = {
  fa.map(a => fab(a)).flatten
}

Monad also traditionally defines pure, a way to lift pure values into an effect context. We can do that with Covariant's map and IdentityFlatten's any. any summons an effect out of thin air for us, and we can then use map to sneak our pure value into that effect. Whilst this seems a little tricky, it gives a bit more flexibility. As Adam Fraser puts it, this "also allows you to express constraints on the types of values that can be injected through implementing CovariantSubset instead of Covariant". Subsets were not featured in the talk and I'll talk about those more in a future post once my understanding is more solidified.

def pure[F[+_] : Covariant : IdentityFlatten, A](a: A)(implicit i : IdentityFlatten[F]): F[A] = {
  i.any.map(_ => a)
}
pure[Option,Int](12)
// Option[Int] = Some(12)
pure[List,String]("Hello")
// List[String] = List(Hello)

Applicatives in Prelude

In my original post we used the ap function to apply a function to an option using the ap function. Whilst the purpose of this was to go to explain currying so we can apply a function to multiple effects, as parameters, here let's just replicated it with prelude.

In prelude the equivalent to Applicative is defined as follows.

type Applicative[F[+_]] = Covariant[F] with IdentityBoth[F]

Covariant should be familiar, it is Functor and gives us map. IdentityBoth is Identity with AssociativeBoth.

Associative both is product from Cats. (product can be implemented with the ap function from Applicative)

override def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
  ap(map(fa)(a => (b: B) => (a, b)))(fb)

Applicative[Option].product(Option(10), Option(12)).map{case (a,b) => a + b}
// Option[Int] = Some(22)

In prelude product is essentialy defined directly as AssociativeBoth which implements a binary associative operator to combine two effects into an effect containing a tuple, in other words product.

AssociativeBoth[Option].both(Option(10), Option(12)).map{case (a,b) => a + b}
// Option[Int] = Some(22)

Applicative requires map, ap and pure. We have map from Covariant, the equivalent of ap using both from AssociativeBoth and pure uses Identity just like with our Monad example.

def pure[F[+_] : Covariant : IdentityBoth, A](a: A)(implicit i : IdentityBoth[F]): F[A] = {
  i.any.map(_ => a)
}
pure[Option,Int](12)
// res1: Option[Int] = Some(12)
pure[List,String]("Hello")
// res2: List[String] = List(Hello)

Sequence and Traverse

In the seminal paper Applicative programming with Effects, the first motivating example for applicative programming is the sequence function. You have a list of effects, specifically Haskell IO effects, and you would like to turn them into an IO[List[A]]. You might recognise this as having the same shape and purpose as Future.sequence from the Scala standard library. sequence is built with its more powerful friend traverse.

Future.sequence is a function IterableOnce[Future[A]] => Future[IterableOnce[A]]
Future.traverse is a function IterableOnce[A], A => Future[B] => Future[IterableOnce[B]]

In Typelevel Cats, the Traverse typeclass makes this more flexible by allows us to traverse over any type that is a functor (you can map over it) and foldable (you can fold it with foldLeft, foldRight and fold).

trait Traverse[F[_]] extends Functor[F] with Foldable[F] {
 def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
}

What's interesting about Traverse is that it relies on a number of type classes to build its expressive power. Ultimately our little friend ap is the king pin of the whole thing, allowing us to combine the effects together as we fold in a way that is "idiomatic" to the effect type. When we traverse a list of Id for example (the identity monad) we get map, and when we traverse a list of Const, we get fold. In other words changing the data type is all we need to make drastically different programs.

To demonstrate this in my applicative post, I wrote an implementation of a silly algorithm called Sleep Sort. Sleep Sort works by waiting an amount of time-based on the value of the number. Emitting the numbers in this way sorts them (assuming your scheduler is accurate enough). Let's be clear, this is a stupid way to sort numbers, but it does represent some real-world needs we have like being able to run effects in parallel.

import zio._
import zio.prelude._
import zio.console._
import zio.clock._
def delayedPrintNumber(s: Int): ZIO[Console with Clock,String,Int] = {
    putStrLn(s"Preparing to say number in $s seconds") *>
    putStrLn(s"$s").delay(s.seconds) *>
    ZIO.succeed(s)
}
val ios = List(6,5,2,1,3,8,4,7).map(delayedPrintNumber)
// ios: List[ZIO[Console with Clock,String,Int]]

Using Cats we can use Traverse.sequence to flip the List[Zio] to ZIO[List] and then execute it.

import cats.__
import cats.Traverse
val runtime = Runtime.default
val program = Traverse[List].traverse(ios)
runtime.unsafeRun(program)

Sadly we find this does not work because wanted all the effects to start at once and then complete at their alloted times, making the sort work. Instead we'll see each executed in sequence.

Monadic version

Preparing to say number in 6 seconds
6
Preparing to say number in 5 seconds
5
// ... and so on for a while

Happily thanks to the joys of Applicative we can fix this by changing the data type. If we rewrite using Cats Effect we wrap our IO into a different type called Par.IO which has a different implementation of applicative that does NOT sequence the IOs together but allows them to run in parallel, we can get the sleep sort behaviour. We didn't change the structure of our code, just the data type!

Now all of the effects started at the same time and ran in parallel.

Preparing to say number in 6 seconds
Preparing to say number in 2 seconds
Preparing to say number in 1 seconds
Preparing to say number in 3 seconds
Preparing to say number in 8 seconds
Preparing to say number in 4 seconds
Preparing to say number in 7 seconds
Preparing to say number in 5 seconds
1
2
3
4
5
6
7
8

ZIO Effects and Prelude

Let's visit the same problem using our ZIO effects above. One thing I really like about prelude is how combinations of its algebras are mapped to ZIO effects. In this table we have two ZIO effects fa : ZIO[R, E, A] and fb : ZIO[R, E, B] that are combined in different ways just by changing the algebra.

Algebra	ZIO instance implementation	Description
AssociativeBoth	fa zip fb	fa first then fb iff fa succeeds, returning ZIO[R,E,(A,B)]
AssociativeEither	fa.orElseEither(fb)	fa first then if it fails fb, returning ZIO[R,E,Either[A,B]]
CommutativeBoth	fa zipPar fb	fa and fb at the same time, returning ZIO[R,E,(A,B)]

This is really nice and similar in spirit to what we did with Cats Traverse.

ZIO's implementation of Traverse has eschewed conventional names for some functions in favour or more common words, so for example sequence is just flip, which describes the flipping of the F[G[A]] to a G[F[A]]. We should be able to just flip our list of ZIOs and execute them using traverse.

However, when we come back to Traverable prelude's (version of Traverse) there are two difficulties.

Problem 1. Traversable doesn't handle empty structures

Perhaps by design, you cannot just take a list of ZIO effects and Traverse them, because the flip function requires the G parameter to have the IdentityBoth algebra. That algebra lets us combine two effects to a tuple, and there is an identity element. ZIO effects do not have an instance of the IdentityBoth algebra and as such cannot be used with Traverable.

We can get around this by using the NonEmptyTraversable which implements the Traversable type class for non-empty structures. Its functions are postfixed with a 1 to indicate they require at least one element to work with, and use AssociativeBoth algebra which ZIO has as you can see above.

Problem 2. We don't have a way to change from sequenced to parallel execution

When we were dealing with Applicatives we can change the data type to select a different applicative and get a different combining method. This is a crucial part of Traverse IMHO. This functionality is missing because the algebra is hardcoded. We can't used the Algebra of choice from the table above (we would need to use CommutativeBoth to get the parallel execution the sleep sort needs).

Running the code

val runtime = Runtime.default
runtime.unsafeRun(NonEmptyTraversable[NonEmptyList].flip1(ios))

Sadly the best we can do at the moment is to use flip1 but we are limited to sequential execution.

Possible Solutions

I talked to Adam Fraser about this and the probable solution will be a forthcoming newtype called Parallel which can wrap your effects with. This would work but feels a bit strange because we already had algebras that change behaviours but we can't freely use them in this context, and having additional newtypes seems like it violates the don't repeat yourself (DRY) principle.

Another possible solution would be to have additional Traverse types with different algebras. Neither solution seems as clean as the Applicative one at this point.

One advantage of Applicatives is that you can compose any two with each other. As an advanced example from one of my talks I compose Const, IO and Parallel together, and take advantage of Monoidal composition, to execute a list of IO operations and gather statistics on the results as well as collecting the values.

val program = Traverse[List].traverse(List(1,2,3,4,8)) {
  n =>
  Nested[IO.Par,Const[(Long, Int, List[String], List[Long]),?], String](
    Par(time(exampleIO(n)).map{
      case _ =>  (time, a) =>
         Const((time, 1, List(a), List(time)))
        })
  )
}

https://youtu.be/T_0IE8PF1sY https://docs.google.com/presentation/d/1MvPBfmUIOuvM-vjjYz6lrhQNQ7hPLzKkTR9I73uoTak/edit?usp=sharing

In theory Prelude should be able to bring the same level of composition; maybe even surpass it.

Some final defense for ap

Whilst ap is certainly not a perfect for Scala, what it does have going for it from a pedagogical point of view is that you can teach Functor, Monad and Applicative as being three ways to map a F[A] => F[B]. The only difference between them is the "shape" of the function you use to do the mapping. With functor the pure function A => B defines the Functor as letting us run a pure function on an effect. With flatMap the function A => F[B] lets us compose two effects together, with the result of one passed to the second. And finally, with Applicative, the F[A => B] function is the building block for running two independent effects together.

With that out of the way, and with the student sufficiently guided through the process of currying and the implementation of map2, map3 etc, we can move on from ap and maybe never look at it again. Applicative is still applicative whether you formulate it with pure and ap, with product, or with map2. You can enjoy the benefits of Applicative without adopting the red-headed stepchild we call ap.

Things I missed

I intend to write more on Prelude soon, but until I do here the bits I didn't mention that are nevertheless very interesting features.

Variance. If you tend to ignore variance in your Scala that will likely change in Prelude. I tend to stick to invariant types a lot of the time, but Prelude's design encourages call site variance, and we should start to see interesting examples of what that empowers us to do more of. In the talk John's example was that he wanted to map an A to B but have more control over what the B is; perhaps it is a Spark serializable type…

ZPure. When ZIO came along it brought the idea of getting rid of stacks of Monad transformers by putting all that functionality (error channels, read-only environments) into an effect. With ZPure we get to do a similar thing for none IO effects. ZPure gives you a State monad, a read only environment. I expect ZPure will be an important building block for ZIO and Prelude code, and I'm looking forward to playing with it some more.

Newtypes. Prelude comes With a nice newtype implementation. I haven't looked into it much, but it seems to work quite well with minimal effort.

Wrapping things up

As zio-prelude evolves I expect it will at first grow, then shed some features into modules or libraries, before shrinking to a smaller but coherent core.

At this point I believe Prelude is a very interesting new addition to the Scala functional programming library ecosystem. Those experienced with the Haskell-like way of doing things will probably find its way of doing things pretty strange at first, and I don't know how long that feeling will last.

Another question is whether functional programming in Scala will further bifurcate. As Prelude and ZIO become more closely intertwined (they already depend on each other), I expect that some people will be put off by the novelty of Prelude and stick with the Cats ecosystem, while others will avoid things built on Cats in order to stay in the ZIO and Prelude world.

Ultimately time will tell whether Prelude's approach will make a big impact on Scala functional programming. In any event the best ideas will live on.