Friday, November 28, 2008

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.

4 comments:

  1. Nicely done except for a minor error in your foldLeft implementation: the recursive call to foldLeft should have the list as its first argument.

    I.e.,

    case x :: xs => foldLeft( xs, f(z, x) )( f )

    ReplyDelete
  2. Thanks. I think I realized this the other day and was going to fix it, but then forgot :(

    Will fix today.

    ReplyDelete
  3. I guess I had switched the arguments everywhere and just missed that one spot. Fixed. Thanks.

    ReplyDelete
  4. Are you looking for high quality and louis vuitton name products? Do you want to pay by louis vuitton bags price? Now you have come to the right place. At favorluxury.com, which louis vuitton handbags in selling discounted authentic lv handbags, wallets, purses and any other accessories, you may fulfill your dream easily.Favorluxury is for those who don't want to settle for anything less than authentic. It offers only authentic replica louis vuitton handbags, purses, wallets and so on. We will help you get your hands on authentic pre-owned Louis Vuitton handbags, wallets and purses. You'll have a preliminary taste for the sense of luxury our Louis Vuitton products brings for you. You can choose and pick your most desirable ones here, either our lv handbag
    , wallets and purses, or any other classical accessories.

    ReplyDelete