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.
Nicely done except for a minor error in your foldLeft implementation: the recursive call to foldLeft should have the list as its first argument.
ReplyDeleteI.e.,
case x :: xs => foldLeft( xs, f(z, x) )( f )
Thanks. I think I realized this the other day and was going to fix it, but then forgot :(
ReplyDeleteWill fix today.
I guess I had switched the arguments everywhere and just missed that one spot. Fixed. Thanks.
ReplyDelete