Surprising behavior when performing flatmap on Maps whose values are Lists of 2-tuples

Am Dienstag, 10. Januar 2012 10:00:13 UTC+1 schrieb Tom Dong:

Hi, I found the following behavior of the flat-map operation
confusing:

scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
22,2 -> 222))
m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))

scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
tuples are missing(overwritten)
res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)

What you see here is Do What I Mean breaking down in the face of two possible options: the current implementation tries to preserve Map types if possible, so if some pairs fall out of the transformation it creates a map, otherwise you get an Iterable of whatever your function produces. If you want to take away surprises, the second half-sentence would have to be changed to “compile error if no pairs are produced”, which would break tons of existing code and probably the expectations of lots of people. In the end your confusion (which, I gather, is cured now) will be weighed against the consequences of changing the behavior.

To propose a different (also mental) approach: relying completely on type inference can be confusing, especially to someone reading your code, so in these cases I generally add a type ascription to the result of the transformation to document and enforce my intention. If the compiler barfs, add a (scala.collection.breakOut) to the last transformation.

Regards,

Roland

On Tue, Jan 10, 2012 at 10:00 AM, Tom Dong wrote:
> Hi, I found the following behavior of the flat-map operation
> confusing:
>
> scala> val m = Map("a" -> List(11,111), "b" -> List(22,222))
> m: scala.collection.immutable.Map[java.lang.String,List[Int]] = Map(a -
>> List(11, 111), b -> List(22, 222))
>
> scala> m.flatMap(_._2) // Expected behavior
> res: scala.collection.immutable.Iterable[Int] = List(11, 111, 22, 222)

As Paul wrote, you will get that if you

> scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
> 22,2 -> 222))
> m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
> Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))
>
> scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
> tuples are missing(overwritten)
> res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)
>
> Paul discussed with me a little bit in this ticket:
> https://issues.scala-lang.org/browse/SI-5364
>
> Is it possible to change this in the future? I spent quite some time
> on debugging this and someone else may encounter the same problem.
>
> I thought it were just an implementation issue of the flatMap
> operation. I wonder why this is "fundamental to the design of the
> collections"? Should all collection operations abide to the "operate
> on a collection, and get a new collection of the same type" rule?
>
I think that's by far the simplest rule to remember, yes. Everything
here is as expected. If you start with a map and produce a collection
of pairs, the result will be assembled in another map. If you want
something else, use m.toList.

Cheers

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

On 01/10/2012 07:00 PM, Tom Dong wrote:
> Hi, I found the following behavior of the flat-map operation
> confusing:
>
> scala> val m = Map("a" -> List(11,111), "b" -> List(22,222))
> m: scala.collection.immutable.Map[java.lang.String,List[Int]] = Map(a -
>> List(11, 111), b -> List(22, 222))
>
> scala> m.flatMap(_._2) // Expected behavior
> res: scala.collection.immutable.Iterable[Int] = List(11, 111, 22, 222)
>
> scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
> 22,2 -> 222))
> m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
> Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))
>
> scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
> tuples are missing(overwritten)
> res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)
>
> Paul discussed with me a little bit in this ticket:
> https://issues.scala-lang.org/browse/SI-5364
>
> Is it possible to change this in the future? I spent quite some time
> on debugging this and someone else may encounter the same problem.
>
> I thought it were just an implementation issue of the flatMap
> operation. I wonder why this is "fundamental to the design of the
> collections"? Should all collection operations abide to the "operate
> on a collection, and get a new collection of the same type" rule?
>
> Thanks:)

This is because flatMap is not type-safe. It is not type-safe because it
has been conflated with sequencing, which is a more appropriate function
for your use-case. Your use-case should not have compiled as-is. See The
Essence of the Iterator Pattern for more.

On Tue, Jan 10, 2012 at 12:46 PM, Tony Morris wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 01/10/2012 07:00 PM, Tom Dong wrote:
>> Hi, I found the following behavior of the flat-map operation
>> confusing:
>>
>> scala> val m = Map("a" -> List(11,111), "b" -> List(22,222))
>> m: scala.collection.immutable.Map[java.lang.String,List[Int]] = Map(a -
>>> List(11, 111), b -> List(22, 222))
>>
>> scala> m.flatMap(_._2) // Expected behavior
>> res: scala.collection.immutable.Iterable[Int] = List(11, 111, 22, 222)
>>
>> scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
>> 22,2 -> 222))
>> m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
>> Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))
>>
>> scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
>> tuples are missing(overwritten)
>> res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)
>>
>> Paul discussed with me a little bit in this ticket:
>> https://issues.scala-lang.org/browse/SI-5364
>>
>> Is it possible to change this in the future? I spent quite some time
>> on debugging this and someone else may encounter the same problem.
>>
>> I thought it were just an implementation issue of the flatMap
>> operation. I wonder why this is "fundamental to the design of the
>> collections"? Should all collection operations abide to the "operate
>> on a collection, and get a new collection of the same type" rule?
>>
>> Thanks:)
>
> This is because flatMap is not type-safe. It is not type-safe because it
> has been conflated with sequencing, which is a more appropriate function
> for your use-case. Your use-case should not have compiled as-is. See The
> Essence of the Iterator Pattern for more.
>
Flatmap is perfectly type safe. If you argue otherwise, please point
me to the cast that should fail.

You argue for another collection universe which has nothing to do with
Scala's. Let's not confuse the issues here.

There's a big error here, Tony.   Map *is* typesafe, but it *does not
abide by scalaz's interface for a Monad*.

The flatMap operation, on the Monad interface (derived from Haskell),
is far more restrictive than how flatMap works on Scala collections
(which are monads in the 'software pattern' sense, not a direct
implementation of an interface sense.  As Martin and Roland state,
Scala has gone to great lengths to give collections an OO feel, and
ensure type safety and nice return type.

I gave a talk on this kind of abstraction
(http://days2010.scala-lang.org/node/138/152).  It's an interesting
design decision and I personally feel is much nicer to users,
especially in collections.

You can always use Scalaz's type traits for Monad to gain a different
flatMap method, but it still won't be what you want.

- Josh

On Tue, Jan 10, 2012 at 6:46 AM, Tony Morris wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 01/10/2012 07:00 PM, Tom Dong wrote:
> > Hi, I found the following behavior of the flat-map operation
> > confusing:
> >
> > scala> val m = Map("a" -> List(11,111), "b" -> List(22,222))
> > m: scala.collection.immutable.Map[java.lang.String,List[Int]] = Map(a -
> >> List(11, 111), b -> List(22, 222))
> >
> > scala> m.flatMap(_._2) // Expected behavior
> > res: scala.collection.immutable.Iterable[Int] = List(11, 111, 22, 222)
> >
> > scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
> > 22,2 -> 222))
> > m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
> > Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))
> >
> > scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
> > tuples are missing(overwritten)
> > res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)
> >
> > Paul discussed with me a little bit in this ticket:
> > https://issues.scala-lang.org/browse/SI-5364
> >
> > Is it possible to change this in the future? I spent quite some time
> > on debugging this and someone else may encounter the same problem.
> >
> > I thought it were just an implementation issue of the flatMap
> > operation. I wonder why this is "fundamental to the design of the
> > collections"? Should all collection operations abide to the "operate
> > on a collection, and get a new collection of the same type" rule?
> >
> > Thanks:)
>
> This is because flatMap is not type-safe. It is not type-safe because it
> has been conflated with sequencing, which is a more appropriate function
> for your use-case. Your use-case should not have compiled as-is. See The
> Essence of the Iterator Pattern for more.
>
> - --
> Tony Morris
> http://tmorris.net/
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJPDCUPAAoJEPxHMY3rBz0PEeYIAKSxa1WY93V5+FtiOV4tFOzV
> r/wFVsHI1cKqIXFLpolSG1x0gLocAeoI7ZzlWK53F6Owg4P5cbxWEXUonVBkMjiO
> q16YNOODQU4KlPWqnoEovFNZXprhodAYEXI7GesfA5YWKIdk1AQT2r4WbQjiFccD
> /001DT6OvC27dSRG5HxoqLdotRbD2LfKW4gsyJL5rNhp2AomW6kGDMWZFVAvGQmS
> 7uUkBS6EnzKIU7EQ6f8auzJ5ItowKB9GUDfZycg9ZSjtvmXp6QI/vUeJAn7PJPO/
> DWv+E3S7J0JgPcpAuuZHPKvA19/YOxFj08vObUUu3AKUZi5d57vDsFGEjIqW5mk=
> =g+5O
> -----END PGP SIGNATURE-----

> I thought it were just an implementation issue of the flatMap
> operation. I wonder why this is "fundamental to the design of the
> collections"? Should all collection operations abide to the "operate
> on a collection, and get a new collection of the same type" rule?
>

And, it should be noted, that this is not really true.
If one starts with a Synchronized Map

class MyMap extends mutable.HashMap with mutable.SynchronizedMap ...

one does not get a Synchronized Map back from such operations
but, rather, a HashMap.
See: https://issues.scala-lang.org/browse/SI-5001

Richard

Trait decorations of types are broken under the 2.8 collections scheme.  It simply doesn't work, and it can't work without a significant language change (most likely to appear in the form of macros, I suppose).

If it's not going to be fixed soon, I think the traits should be deprecated.  If you want a particular type of behavior, you shouldn't decorate with a trait, you should use the collection that has that behavior.

  --Rex

On Tue, Jan 10, 2012 at 11:18 AM, richard emberson <richard.emberson@gmail.com> wrote:

I thought it were just an implementation issue of the flatMap
operation. I wonder why this is "fundamental to the design of the
collections"? Should all collection operations abide to the "operate
on a collection, and get a new collection of the same type" rule?

And, it should be noted, that this is not really true.
If one starts with a Synchronized Map

class MyMap extends mutable.HashMap with mutable.SynchronizedMap ...

one does not get a Synchronized Map back from such operations
but, rather, a HashMap.
See: https://issues.scala-lang.org/browse/SI-5001

Richard

Thanks for the explanation. I have just carefully read though the
documents about collection architecture and got a better
understanding. I haven't realized the intricate implication of
"uniform return value principle" until it bought me a bug recently. I
think people coming from other languages like C# might need to be
warned about this, rather than simply accept this as just some magical
feature.

There's one more thing that confuses me. Should flatten and flatMap
conform to the "uniform return value principle", too? Which collection
operations should conform to this principle? For instance, reduceLeft
don't need to follow this principle, even if it returns a collection:

scala> Set(List(1,2,3), List(2,3,4), List(3,4,5)).reduceLeft(_ ++ _)
res: List[Int] = List(1, 2, 3, 2, 3, 4, 3, 4, 5)

But:

scala> Set(List(1,2,3), List(2,3,4), List(3,4,5)).flatten
res: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)

scala> Set(List(1,2,3), List(2,3,4), List(3,4,5)).flatMap(x=>x)
res: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)

So the rule seems to be: each method that specializes in producing a
new collection by transforming its owner should have uniform return
values (except for conversions).

But I wonder if this rule should always be held. "flatten" is
documented as "Converts this collection of traversable collections
into a collection in which all element collections are concatenated.",
which actually seems to describe "_.reduceLeft(_ ++ _)". Concatenating
some Lists to get a Set seems quite counter-intuitive.

And it seems even more counter-intuitive in the case of flatMap, which
is described as "The collection obtained from applying the collection-
valued function f to every element in xs and concatenating the
results.". I found it hard to rationalize this behavior:
scala> Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 -> 22,2 ->
222)).flatMap(_._2)
res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)

On Jan 10, 8:54 pm, martin odersky wrote:
> On Tue, Jan 10, 2012 at 10:00 AM, Tom Dong wrote:
> > Hi, I found the following behavior of the flat-map operation
> > confusing:
>
> > scala> val m = Map("a" -> List(11,111), "b" -> List(22,222))
> > m: scala.collection.immutable.Map[java.lang.String,List[Int]] = Map(a -
> >> List(11, 111), b -> List(22, 222))
>
> > scala> m.flatMap(_._2) // Expected behavior
> > res: scala.collection.immutable.Iterable[Int] = List(11, 111, 22, 222)
>
> As Paul wrote, you will get that if you
>
>
>
>
>
>
>
>
>
> > scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
> > 22,2 -> 222))
> > m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
> > Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))
>
> > scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
> > tuples are missing(overwritten)
> > res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)
>
> > Paul discussed with me a little bit in this ticket:
> >https://issues.scala-lang.org/browse/SI-5364
>
> > Is it possible to change this in the future? I spent quite some time
> > on debugging this and someone else may encounter the same problem.
>
> > I thought it were just an implementation issue of the flatMap
> > operation. I wonder why this is "fundamental to the design of the
> > collections"? Should all collection operations abide to the "operate
> > on a collection, and get a new collection of the same type" rule?
>
> I think that's by far the simplest rule to remember, yes. Everything
> here is as expected. If you start with a map and produce a collection
> of pairs, the result will be assembled in another map. If you want
> something else, use m.toList.
>
> Cheers
>
>  -- Martin

On Fri, Jan 13, 2012 at 06:59, Tom Dong wrote:
> Thanks for the explanation. I have just carefully read though the
> documents about collection architecture and got a better
> understanding. I haven't realized the intricate implication of
> "uniform return value principle" until it bought me a bug recently. I
> think people coming from other languages like C# might need to be
> warned about this, rather than simply accept this as just some magical
> feature.

As someone who spends a lot of time helping Scala beginners, I must
say dealing with the warped preconceptions(*) that programming in any
language produces is very, very hard. You can repeat something to a
person dozens of times, and he will nod, say he understood, *think* he
understood, and then go and blunder into a problem because he didn't
really understand it.

It is truly a case of the burnt hand teaching best, unfortunately.
Yet, it is always helpful when others point out things that led one to
believe something, as you do below.

> There's one more thing that confuses me. Should flatten and flatMap
> conform to the "uniform return value principle", too? Which collection
> operations should conform to this principle? For instance, reduceLeft
> don't need to follow this principle, even if it returns a collection:
>
> scala> Set(List(1,2,3), List(2,3,4), List(3,4,5)).reduceLeft(_ ++ _)
> res: List[Int] = List(1, 2, 3, 2, 3, 4, 3, 4, 5)

That's because reduceLeft doesn't return a collection -- necessarily,
at any rate. Traversable[A].reduceLeft will return A. Similarly,
Traversable[A].foldLeft[B] will return B. The fact that A was a
colletion in your example is just a coincidence.

Compare that to map, flatten or flatMap -- it will *always* return a
collection, and the basis for that collection is the (static) type of
the collection it is being called on

>
> But:
>
> scala> Set(List(1,2,3), List(2,3,4), List(3,4,5)).flatten
> res: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)
>
> scala> Set(List(1,2,3), List(2,3,4), List(3,4,5)).flatMap(x=>x)
> res: scala.collection.immutable.Set[Int] = Set(5, 1, 2, 3, 4)
>
> So the rule seems to be: each method that specializes in producing a
> new collection by transforming its owner should have uniform return
> values (except for conversions).
>
> But I wonder if this rule should always be held. "flatten" is
> documented as "Converts this collection of traversable collections
> into a collection in which all element collections are concatenated.",
> which actually seems to describe "_.reduceLeft(_ ++ _)". Concatenating
> some Lists to get a Set seems quite counter-intuitive.
>
> And it seems even more counter-intuitive in the case of flatMap, which
> is described as "The collection obtained from applying the collection-
> valued function f to every element in xs and concatenating the
> results.". I found it hard to rationalize this behavior:
> scala> Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 -> 22,2 ->
> 222)).flatMap(_._2)
> res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)

Both these descriptions are seriously misleading, and I'll do
something about them. Thanks for pointing it out.

>
> On Jan 10, 8:54 pm, martin odersky wrote:
>> On Tue, Jan 10, 2012 at 10:00 AM, Tom Dong wrote:
>> > Hi, I found the following behavior of the flat-map operation
>> > confusing:
>>
>> > scala> val m = Map("a" -> List(11,111), "b" -> List(22,222))
>> > m: scala.collection.immutable.Map[java.lang.String,List[Int]] = Map(a -
>> >> List(11, 111), b -> List(22, 222))
>>
>> > scala> m.flatMap(_._2) // Expected behavior
>> > res: scala.collection.immutable.Iterable[Int] = List(11, 111, 22, 222)
>>
>> As Paul wrote, you will get that if you
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> > scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
>> > 22,2 -> 222))
>> > m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
>> > Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))
>>
>> > scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
>> > tuples are missing(overwritten)
>> > res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)
>>
>> > Paul discussed with me a little bit in this ticket:
>> >https://issues.scala-lang.org/browse/SI-5364
>>
>> > Is it possible to change this in the future? I spent quite some time
>> > on debugging this and someone else may encounter the same problem.
>>
>> > I thought it were just an implementation issue of the flatMap
>> > operation. I wonder why this is "fundamental to the design of the
>> > collections"? Should all collection operations abide to the "operate
>> > on a collection, and get a new collection of the same type" rule?
>>
>> I think that's by far the simplest rule to remember, yes. Everything
>> here is as expected. If you start with a map and produce a collection
>> of pairs, the result will be assembled in another map. If you want
>> something else, use m.toList.
>>
>> Cheers
>>
>>  -- Martin

On 01/10/2012 11:17 PM, martin odersky wrote:
> On Tue, Jan 10, 2012 at 12:46 PM, Tony Morris wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> On 01/10/2012 07:00 PM, Tom Dong wrote:
>>> Hi, I found the following behavior of the flat-map operation
>>> confusing:
>>>
>>> scala> val m = Map("a" -> List(11,111), "b" -> List(22,222))
>>> m: scala.collection.immutable.Map[java.lang.String,List[Int]] = Map(a -
>>>> List(11, 111), b -> List(22, 222))
>>> scala> m.flatMap(_._2) // Expected behavior
>>> res: scala.collection.immutable.Iterable[Int] = List(11, 111, 22, 222)
>>>
>>> scala> val m = Map("a" -> List(1 -> 11,1 -> 111), "b" -> List(2 ->
>>> 22,2 -> 222))
>>> m: scala.collection.immutable.Map[java.lang.String,List[(Int, Int)]] =
>>> Map(a -> List((1,11), (1,111)), b -> List((2,22), (2,222)))
>>>
>>> scala> m.flatMap(_._2) // Surprising behavior, a map is created and 2
>>> tuples are missing(overwritten)
>>> res: scala.collection.immutable.Map[Int,Int] = Map(1 -> 111, 2 -> 222)
>>>
>>> Paul discussed with me a little bit in this ticket:
>>> https://issues.scala-lang.org/browse/SI-5364
>>>
>>> Is it possible to change this in the future? I spent quite some time
>>> on debugging this and someone else may encounter the same problem.
>>>
>>> I thought it were just an implementation issue of the flatMap
>>> operation. I wonder why this is "fundamental to the design of the
>>> collections"? Should all collection operations abide to the "operate
>>> on a collection, and get a new collection of the same type" rule?
>>>
>>> Thanks:)
>> This is because flatMap is not type-safe. It is not type-safe because it
>> has been conflated with sequencing, which is a more appropriate function
>> for your use-case. Your use-case should not have compiled as-is. See The
>> Essence of the Iterator Pattern for more.
>>
> Flatmap is perfectly type safe. If you argue otherwise, please point
> me to the cast that should fail.

To be clear, the type of flatMap is not consistent with the monad
interface, to the extent that it no longer represents the interface,
even approximately. Instead, this particular instance of flatMap
conflates monadic joining with the sequence of effects. This has
practical consequences.

> You argue for another collection universe which has nothing to do with
> Scala's. Let's not confuse the issues here.

No I don't. I argue against inflexibility for zero gain in the same
universe as everyone else.