EXERCISE 6.7 sequence answer explanation

[shay shimony]

Hi!

Can you help me understand what specifically is returned by by a call to sequence implementation in the answers?

def sequence[A](fs: List[Rand[A]]): Rand[List[A]] =
  fs.foldRight(unit(List[A]()))((f, acc) => map2(f, acc)(_ :: _))

I mean a call like sequence(fs), not a call to sequence(fs)(rng).

If I add prints I can see it goes over the list and construct some Rand[List[A]] function, but how this function looks like internally? How should I imagine it?

I made lazier tailrec answer: it does not do anything until it gets the RNG (and only then traverses the functions list). This implementation is much easier for me to perceive.
I think its because in this implementation I assume that I already got the RNG (so in the returned function body I have both fs and r) - and then I do simple accumulation to a list of As, while you do the accumulation on a function that fuses together somehow all the given fs. Its beautiful - but so abstract - I am straggling here to perceive it.

def sequence[A](fs: List[Rand[A]]): Rand[List[A]] = {
  r => {
    val lb = new ListBuffer[A]
    @annotation.tailrec
    def go(fs: List[Rand[A]], r: RNG): (List[A], RNG) = fs match {
      case Nil => (lb.toList, r)
      case hf::tf =>
        val (h, rt) = hf(r)
        lb += h
        go(tf, rt)
    }
    go(fs, r)
  }
}

Thanks!
Shay

[shay shimony]

Hi,
I made the following trace to help myself:

If we have a list of functions such as:
f1, f2, f3, Nil

For easy reference, foldRight can be:

def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =
  as match {
    case Nil => z
    case Cons(x, xs) => frf(x, foldRight(xs, z)(f)) // frf for foldRight function  
}

Our function sequence uses foldRight this way:

def sequence[A](fs: List[Rand[A]]): Rand[List[A]] =
  fs.foldRight(unit(List[A]()))((f, acc) => map2(f, acc)(_ :: _))

So in our case frf is:
frf = (f, acc) => map2(f, acc)(_ :: _)

Because its foldRight we do the accumulation work from the right, which for Nil returns z:
z = rng => (Nil, rng)   // what's returned by the unit function

Now foldRight is in:

case Cons(f3, Nil) => frf(f3, z)

frf is evaluated for f3 and z and returns what map2 returns, which is the function acc3:
acc3 = rng => {
  (a3, r3) = f3(rng)
  (Nil, r3) = z(r3) // returns z3 untouched
  (a3::Nil, r3)
}

acc3 is what returned by the foldRight call we where in, so now we are in:

case Cons(f2, f3:Nil) => frf(f2, acc3)
frf returns now the function acc2:
acc2 = rng => {
  (a2, r2) = f2(rng)
  (a3::Nil, r3) = acc3(r2) // returns r3
  (a2::a3::Nil, r3)
}

acc2 is what returned by the foldRight call we where in, so now we are in:

case Cons(f1, f2::f3:Nil) => frf(f1, acc2)
frf returns now the function acc1:
acc1 = rng => {
  (a1, r1) = f1(rng)
  (a2::a3::Nil, r3) = acc2(r1) // returns r3
  (a1::a2::a3::Nil, r3)
}

So finally foldRight returns acc1.
Now if we apply acc1 on some rng we will see it calls acc2 and then combines its answer to a final answer. calling acc2 itself called acc3 which finally called z.
So foldRight transformed each function fX to another function accX and returned that function to the previous foldRight call, which captured a call to it in the body of the acc function it constructed, and so on.
And we got series of functions (correspond to the received functions list) which refer each to the next in its body by a call.

[Babatunde Ekemode]

Hi,

I think the two form of solutions appeal to different people. For me the first appeals more, and it's very similar to the solution I derived at. My only concern is wrapping my head around the code at a glance, but I believe this is a pattern that will emerge multiple times in my codebase. Once I wrap my head around it I can always move on when next I come across it. But the second solution would always require me to read the code every time I come across it, though at first instance, it's simpler to understand which is its essence.