foldLeft in Scala, Little Schemer style

I'm going to write up a Scala version of foldLeft in the style of The Little Schemer.

What is 0 + (1 + 2 + 3)?

>6

What is 0 + (1 + 2 + 3)?

>0 + 1 + (2 + 3)

What is 0 + 1?

>1

What is 1 + (2 + 3) ?

>1 + 2 + (3)

What is 1 + 2?

>3

What is 3 + (3)?

>3 + 3

What is 3 + 3?

>6

Are we done?

>No, we still haven't found out what foldLeft is.

What is foldLeft?

def foldLeft[A, B](as: List[A], z: B)(f: (B, A) => B): B = {
    as match {
      case Nil => z
      case x :: xs => foldLeft( xs, f(z, x) )( f )
    }
  }

But that doesn't tell us much does it? Let's walk through an example.

What is List( 1, 2, 3 )?

>List( 1, 2, 3 )

What is foldLeft(a, 0){ (x,y) => x + y } when a is List( 1, 2, 3 )

>6 ... but why? Let's step through it together.

What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>No, it's List( 1, 2, 3 ), so we ask the next question.

What is the next question?

>case x :: xs

What is the value of case x :: xs?

>true, because the list is not Nil, it contains one element x which is 1, followed by a list xs which is List(2,3).

So what is the next step?

> foldLeft( xs, f(z, x) )( f )

What is f( z, x )?

> Well, remember, we called foldLeft like so: foldLeft(a, 0){ (x,y) => x + y }

And what is f?

> { (x,y) => x + y }

Again, what is f( z, x )?

> f( 0, 1 )
> (0,1) => 0 + 1
> 1

So what has foldLeft( xs, f(z, x) )( f ) become?

> foldLeft( List(2,3), 1 )( f )

Now we recur into foldLeft. What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>No, it's List( 2, 3 ), so we ask the next question.

What is the next question?

>case x :: xs

What is the value of case x :: xs?

>true, because the list is not Nil, it contains one element x which is 2, followed by a list xs which is List(3).

So what is the next step?

> foldLeft( xs, f(z, x) )( f )

What is f( z, x )? Remember that z is now 1.

> f( 1, 2 )
> (1,2) => 1 + 3
> 3

So what has foldLeft( xs, f(z, x) )( f ) become?

> foldLeft( List(3), 3 )( f )

Now we recur into foldLeft. What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>No, it's List(3), so we ask the next question.

What is the next question?

>case x :: xs

What is the value of case x :: xs?

>true, because the list is not Nil, it contains one element x which is 3, followed by a list xs which is Nil.

So what is the next step?

> foldLeft( xs, f(z, x) )( f )

What is f( z, x )? Remember that z is now 3.

> f( 3, 3 )
> (3,3) => 3 + 3
> 6

So what has foldLeft( xs, f(z, x) )( f ) become?

> foldLeft( Nil, 6 )( f )

Now we recur into foldLeft. What is the first question foldLeft asks about the list?

>case Nil

Is a Nil?

>Yes

So what do we do?

> case Nil => z

And what is z?

6!

So what is foldLeft(a, 0){ (x,y) => x + y } when a is List( 1, 2, 3 )

6!

Are we done?

Yes! Now foldLeft a taco right into your mouth.