folding operators

[mscurtescu]

I am working my way through the Scala book and while trying to
understand exactly how the folding operators work (section 14.7) I
don't see why the unit element is needed.

As far as I can tell both folding operators could take only two
arguments, the list and an operator.

Instead of:
(z /: List(a, b, c)) (op) = op(op(op(z, c), b), a)
you would have something like:
(op) /: List(a, b, c) = op(op(b, c), a)

Can anyone give an example where the unit element is needed?

Unless I am missing something obvious, maybe this should be clarified
in the book.

Thanks,
Marius

--
http://marius.scurtescu.com

[Matt Hellige]

I can't comment on the treatment in the book, as I haven't looked at it yet.

In the most general case, the unit value is necessary because the
types needn't all be the same. In other words, instead of an operator
of type (A, A) => A for a List[A], we can use an operator of type (B,
A) => B. In this case it's pretty clear why we must provide a "seed"
value of type B to start things off... Here's an example:
("" /: List(1, 2, 3)) (_ + _)
=> "123"

("123" :\ List[Char]())(_ :: _)
=> List(1, 2, 3)

However, you make a good observation! Indeed there is another
operation which behaves as you describe. It can be used instead of
fold in some cases (when the operation is of type (A, A) => A and has
an obvious unit), and it is traditionally called "reduce". In fact it
is defined in Scala as reduceLeft and reduceRight in trait Iterable.
Comparing the types of fold and reduce is instructive:
  foldLeft  [B](z : B)(op : (B, A) => B) : B
  reduceLeft  [B >: A](op : (B, B) => B) : B

Hope that helps...
Matt

On Jan 4, 2008 7:24 PM, Marius Scurtescu <marius.scurtescu@...> wrote:

> I am working my way through the Scala book and while trying to
> understand exactly how the folding operators work (section 14.7) I
> don't see why the unit element is needed.
>
> As far as I can tell both folding operators could take only two
> arguments, the list and an operator.
>
> Instead of:
> (z /: List(a, b, c)) (op) = op(op(op(z, c), b), a)
> you would have something like:
> (op) /: List(a, b, c) = op(op(b, c), a)
>
> Can anyone give an example where the unit element is needed?
>
> Unless I am missing something obvious, maybe this should be clarified
> in the book.
>
> Thanks,
> Marius
>
> --
> http://marius.scurtescu.com
>

--
Matt Hellige / matt@...
http://matt.immute.net

[Erik Engbrecht]

scala> val xs = 1 :: 2 :: 3 :: 4 :: Nil

xs: List[Int] = List(1, 2, 3, 4)

scala> (0 /: xs) ((a: Int, b: Int) => a + b)

res7: Int = 10

scala> (10 /: xs) ((a: Int, b: Int) => a + b)

res8: Int = 20

scala> 

How is it supposed to know what to start the fold with is there is no initial parameter?

Also, notice that the z parameter doesn't need to be the same type of element as what is contained in the list.

(I hope that's what you where asking)

On Jan 4, 2008 8:24 PM, Marius Scurtescu <marius.scurtescu@...> wrote:

I am working my way through the Scala book and while trying to
understand exactly how the folding operators work (section 14.7) I
don't see why the unit element is needed.

As far as I can tell both folding operators could take only two
arguments, the list and an operator.

Instead of:
(z /: List(a, b, c)) (op) = op(op(op(z, c), b), a)
you would have something like:
(op) /: List(a, b, c) = op(op(b, c), a)

Can anyone give an example where the unit element is needed?

Unless I am missing something obvious, maybe this should be clarified
in the book.

Thanks,
Marius

--
http://marius.scurtescu.com

--
http://erikengbrecht.blogspot.com/

[mscurtescu]

Thanks for the clarifications, it all makes sense now.

From the book it wasn't clear that the types are not all the same, and
reduce is not mentioned at all.

Marius


On 1/4/08, Matt Hellige <matt@...> wrote:

> I can't comment on the treatment in the book, as I haven't looked at it yet.
>
> In the most general case, the unit value is necessary because the
> types needn't all be the same. In other words, instead of an operator
> of type (A, A) => A for a List[A], we can use an operator of type (B,
> A) => B. In this case it's pretty clear why we must provide a "seed"
> value of type B to start things off... Here's an example:
> ("" /: List(1, 2, 3)) (_ + _)
> => "123"
>
> ("123" :\ List[Char]())(_ :: _)
> => List(1, 2, 3)
>
> However, you make a good observation! Indeed there is another
> operation which behaves as you describe. It can be used instead of
> fold in some cases (when the operation is of type (A, A) => A and has
> an obvious unit), and it is traditionally called "reduce". In fact it
> is defined in Scala as reduceLeft and reduceRight in trait Iterable.
> Comparing the types of fold and reduce is instructive:
>   foldLeft  [B](z : B)(op : (B, A) => B) : B
>   reduceLeft  [B >: A](op : (B, B) => B) : B
>
> Hope that helps...
> Matt
>
> On Jan 4, 2008 7:24 PM, Marius Scurtescu <marius.scurtescu@...> wrote:
> > I am working my way through the Scala book and while trying to
> > understand exactly how the folding operators work (section 14.7) I
> > don't see why the unit element is needed.
> >
> > As far as I can tell both folding operators could take only two
> > arguments, the list and an operator.
> >
> > Instead of:
> > (z /: List(a, b, c)) (op) = op(op(op(z, c), b), a)
> > you would have something like:
> > (op) /: List(a, b, c) = op(op(b, c), a)
> >
> > Can anyone give an example where the unit element is needed?
> >
> > Unless I am missing something obvious, maybe this should be clarified
> > in the book.
> >
> > Thanks,
> > Marius
> >
> > --
> > http://marius.scurtescu.com
> >
>
>
>
> --
> Matt Hellige / matt@...
> http://matt.immute.net
>

--
http://marius.scurtescu.com

[mscurtescu]

On 1/4/08, Erik Engbrecht <erik.engbrecht@...> wrote:

> scala> val xs = 1 :: 2 :: 3 :: 4 :: Nil
>  xs: List[Int] = List(1, 2, 3, 4)
>
>  scala> (0 /: xs) ((a: Int, b: Int) => a + b)
> res7: Int = 10
>
> scala> (10 /: xs) ((a: Int, b: Int) => a + b)
>  res8: Int = 20
>
>  scala>
>
> How is it supposed to know what to start the fold with is there is no
> initial parameter?

If all the types are the same then just start with the last element of
the list.


> Also, notice that the z parameter doesn't need to be the same type of
> element as what is contained in the list.

Yes, that's what I was missing.


Thanks,
Marius


--
http://marius.scurtescu.com

[Geoff Reedy]

If you do not supply a starting value what should be returned when
folding an empty sequence? That is one use of the initial value.

The other use is if the type of the result is different from the type of
the elements in the sequence. Look at the type of the fold:

Iterable[A]./:[B](z: B)(op: (B,A)=> B): B

If an initial value were not required the 'op' would have to be of type
(B,B)=>B. For example, it is possible to reverse a list using a fold:

scala> ((Nil: List[Int]) /: List(1,2,3,4)){(xs, x) => x :: xs}
res23: List[Int] = List(4, 3, 2, 1)

It says to start with an empty list and prepend each element on to it.
This would not be possible if both parameters to the operator had to be
the same type.

[Erik Engbrecht]

> How is it supposed to know what to start the fold with is there is no initial parameter? 

If all the types are the same then just start with the last element of the list.

I believe that would be a reduce instead of a fold.  Also, folds will succeed on empty lists:

scala> (10 /: Nil) ((a: Int, b: Int) => a + b)

res9: Int = 10

while reduces require at least one element:

scala> val x1 = 1 :: Nil

x1: List[Int] = List(1)

scala> x1.reduceLeft((a: Int, b: Int) => a + b)

res14: Int = 1

scala> Nil.reduceLeft((a: Int, b: Int) => a + b)

java.lang.UnsupportedOperationException: Nil.reduceLeft

at scala.List.reduceLeft(List.scala:1005)

at .<init>(<console>:5)

at .<clinit>(<console>)

at RequestResult$.<init>(<console>:3)

at RequestResult$.<clinit>(<console>)

at RequestResult$result(<console>)

at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)

at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethod...

scala> 

On Jan 4, 2008 9:01 PM, Marius Scurtescu <marius.scurtescu@...> wrote:

On 1/4/08, Erik Engbrecht <erik.engbrecht@...> wrote:

> scala> val xs = 1 :: 2 :: 3 :: 4 :: Nil
>  xs: List[Int] = List(1, 2, 3, 4)
>
>  scala> (0 /: xs) ((a: Int, b: Int) => a + b)
> res7: Int = 10
>
> scala> (10 /: xs) ((a: Int, b: Int) => a + b)
>  res8: Int = 20
>
>  scala>
>
> How is it supposed to know what to start the fold with is there is no
> initial parameter?

If all the types are the same then just start with the last element of
the list.

> Also, notice that the z parameter doesn't need to be the same type of
> element as what is contained in the list.

Yes, that's what I was missing.

Thanks,
Marius


--
http://marius.scurtescu.com

--
http://erikengbrecht.blogspot.com/

[tmorris]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Marius Scurtescu wrote:

> On 1/4/08, Erik Engbrecht <erik.engbrecht@...> wrote:
>> scala> val xs = 1 :: 2 :: 3 :: 4 :: Nil
>>  xs: List[Int] = List(1, 2, 3, 4)
>>
>>  scala> (0 /: xs) ((a: Int, b: Int) => a + b)
>> res7: Int = 10
>>
>> scala> (10 /: xs) ((a: Int, b: Int) => a + b)
>>  res8: Int = 20
>>
>>  scala>
>>
>> How is it supposed to know what to start the fold with is there is no
>> initial parameter?
>
> If all the types are the same then just start with the last element of
> the list.
>
>
>> Also, notice that the z parameter doesn't need to be the same type of
>> element as what is contained in the list.
>
> Yes, that's what I was missing.
>
>
> Thanks,
> Marius
>
>

A helpful exercise might be to write reduce(Left/Right) in terms of
fold(Left/Right). Notice that reduce is a partial function (undefined
for empty lists). Also notice that trying to go the other way around is
not possible. This should imply that reduce is a specialisation of fold.
Therefore, to answer your question, fold is more general than reduce so
you'd need fold for those more general cases.

- --
Tony Morris
http://tmorris.net/

Hey! We had 40,000 lines of C# here yesterday, but now there are 40
lines of... Dear God, what is a catamorphism?"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHfuqumnpgrYe6r60RAj3EAKCtYGbuTFyLALSJlLsIgIpf4toKfwCgk2Sn
qvh1D2Sj5WvcJJ7EBVc2Wcc=
=zJmP
-----END PGP SIGNATURE-----

[Michael Campbell]

On Jan 4, 2008 8:50 PM, Erik Engbrecht <erik.engbrecht@...> wrote:

> scala> val xs = 1 :: 2 :: 3 :: 4 :: Nil
>  xs: List[Int] = List(1, 2, 3, 4)
>
>  scala> (0 /: xs) ((a: Int, b: Int) => a + b)
> res7: Int = 10
>
> scala> (10 /: xs) ((a: Int, b: Int) => a + b)
>  res8: Int = 20
>
>  scala>
>
> How is it supposed to know what to start the fold with is there is no
> initial parameter?

Perhaps I'm being naive here, but perhaps ... the first element?  (or
last, depending on foldL or foldR)

[Stanislas Klimoff-3]

Hi Marius,

On 1/5/08, Marius Scurtescu <marius.scurtescu@...> wrote:

Can anyone give an example where the unit element is needed?

I'm used to fold a list of strings into an empty StringBuilder (I'm not talking about Scala in particular in the moment).

HTH

--
Best wishes,
  Stan Klimoff
  Grid Dynamics Consulting