memoize.md

What if the siganture of memoize would be def memoize: ZIO[R, E, A] instead of UIO[ZIO[R, E,A]]. Let's keep the intial definition.

**we asume that the first part of an for-comprehension can be a x = xyz, which it can't, but it doesn't change the point of this example. The first part of an for-comprehension has to be an x <- xyz **

Let's look at an example:

for {
    m1 <- putStrLn("hello").memoize
    m2 <- putStrLn("hello").memoize
    _ <- m1
    _ <- m1
    _ <- m2
}

( Should print hellow twice, once for the first m1 and once for the second m2)

Now, since we do have referential, this program has to be equivalent to the following one. And this is all what RT means:

val mem1 = putStrLn("hello").memoize
val mem2 = putStrLn("hello").memoize

for {
    m1 <- mem1
    m2 <- mem2
    _ <- m1
    _ <- m1
    _ <- m2
}

According to RT, this in turn should be same as the following, since mem1 and mem2 are the same expression (putStrLn("hello").memoize)

val mem = putStrLn("hello").memoize
for {
    m1 <- mem
    m2 <- mem
    _ <- m1
    _ <- m1
    _ <- m2
}

So one can factor out the common expression putStrLn("hello").memoize and still get a program that behaves the same way. RT for the win! (Still prints hello twice)

Now, when we want to get to ZIO[R, E, A] (i.e. dropping the UIO), the code would look like this:

(notice the = instead of the arrow in the first two lines )

for {
    m1 = putStrLn("hello").memoize
    m2 = putStrLn("hello").memoize
    _ <- m1
    _ <- m1
    _ <- m2
}

Now the problem is, that creating the cache is an effect. When we want to get to ZIO[R, E, A] instead of UIO[ZIO[R, E, A]], we have two possibilites:

Push the effect of cache-creation into the inner zio. This will fail, because then the effect of cache-creation will be repeated every time.

The above code would actually print "hello" thrice, because the cache gets recreated every time. And since we still have referential transparency, this is the same as:

val mem = putStrLn("hello").memoize
for {
    _ <- mem
    _ <- mem
    _ <- mem
}

And this would still give three "hello"s. It's one hello too many, but at least it is consistent.

Now the other possibilty would be to do an side-effect without wrapping it within an UIO. Now this would break referential transparency.

In pseudocode, memoize would looke like this:

def memoize(zio: ZIO[R, E, A]): ZIO[R, E, A] = {
    val cache = createCache
    zio.withCache(cache)
}

If we write our program this way, everything works:

for {
    m1 = putStrLn("hello").memoize
    m2 = putStrLn("hello").memoize
    _ <- m1
    _ <- m1
    _ <- m2
}

This prints "hello" twice \o/

But according to RT, we should be able to factor out the putStrLn("hello").memoize" part. So this would leave us with:

val mem = putStrLn("hello").memoize
for {
    _ <- mem
    _ <- mem
    _ <- mem
}

But now, this prints "hello" only once, since the cache is only created once, since memoize is only called once. So here we have broken RT. Factoring out the expression resulted in a different program.

To keep RT and to only execute once and then cache, we have to execute an effect (cache-creation) and wrap that.

This is why we need UIO[ZIO[R, E, A]]. Removing the first layer creates the cache in an RT way, "removing" the second layer executes the effect or just retrieves it from the cache.