Re: Sorted structures lose their ordering when mapped

--001a11357dd69a8e37054269eff1
Content-Type: text/plain; charset=UTF-8

It was a pretty nice (counter-)example, but I wonder what is "SortedSet"?
And of course the next question will be - how should map be defined on
"SortedSet"?

It's not a joke, it's a serious question.

Thanks,
-Vlad

On Mon, Nov 28, 2016 at 8:14 PM, Tobin Yehle <[email protected]> wrote:

> Not sure if I'm really posting this in the right place, but:
>
> Calling map on a collection that requires an implicit ordering results in
> some surprising behavior. For example:
>
> scala> val set = SortedSet(1,2,3)(ord=Ordering.Int.reverse)
> set: scala.collection.SortedSet[Int] = TreeSet(3, 2, 1)
>
>
> scala> set.firstKey == set.map(identity).firstKey
> res0: Boolean = false
>
> My feeling is that mapping the identity function over any collection
> should not change anything.
>
> In this case it is clear what is happening. The CanBuildFrom provided by
> SortedSet is pulling an Ordering instance out of predef (Ordering.Int)
> instead of using the ordering from the origin collection.
> scala> set.toList
> res1: List[Int] = List(3, 2, 1)
>
>
> scala> set.map(identity).toList
> res2: List[Int] = List(1, 2, 3)
>
> scala> set.ordering
> res3: Ordering[Int] = scala.math.Ordering$$anon$4@3ff3275b
>
> scala> set.map(identity).ordering
> res4: Ordering[Int] = scala.math.Ordering$Int$@7fa85a55
>
> I think this can be fixed by providing a more specific CanBuildFrom
> instance to be used when mapping between two sorted collections that
> contain the same type.
>
> i.e. Provide a CanBuildFrom[Sorted[K, _], K, Sorted[K, _]] somewhere that
> has precedence over the more generic usual CanBuildFrom[CC[_], A, CC[A]]
>
> I'm not sure how it could be done, but the static overloading resolution
> rules make this possible, I think.
>
> --
> You received this message because you are subscribed to the Google Groups
> "scala-language" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
For more options, visit https://groups.google.com/d/optout.

--001a11357dd69a8e37054269eff1
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">It was a pretty nice (counter-)example, but I wonder what =
is &quot;SortedSet&quot;? And of course the next question will be - how sho=
uld map be defined on &quot;SortedSet&quot;?<div><br></div><div>It&#39;s no=
t a joke, it&#39;s a serious question.</div></div><div class=3D"gmail_extra=
"><br clear=3D"all"><div><div class=3D"gmail_signature" data-smartmail=3D"g=
mail_signature">Thanks,<br>-Vlad</div></div>
<br><div class=3D"gmail_quote">On Mon, Nov 28, 2016 at 8:14 PM, Tobin Yehle=
 <span dir=3D"ltr">&lt;<a href=3D"mailto:[email protected]" target=3D"_b=
lank">[email protected]</a>&gt;</span> wrote:<br><blockquote class=3D"gm=
ail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le=
ft:1ex"><div dir=3D"ltr"><div>Not sure if I&#39;m really posting this in th=
e right place, but:</div><div><br></div>Calling map on a collection that re=
quires an implicit ordering results in some surprising behavior. For exampl=
e:<div><div><br></div><div class=3D"m_3440269965916649927prettyprint" style=
=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,187);border-=
style:solid;border-width:1px;word-wrap:break-word"><code class=3D"m_3440269=
965916649927prettyprint"><div class=3D"m_3440269965916649927subprettyprint"=
><span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prettif=
y">scala</span><span style=3D"color:#660" class=3D"m_3440269965916649927sty=
led-by-prettify">&gt;</span><span style=3D"color:#000" class=3D"m_344026996=
5916649927styled-by-prettify"> val </span><span style=3D"color:#008" class=
=3D"m_3440269965916649927styled-by-prettify">set</span><span style=3D"color=
:#000" class=3D"m_3440269965916649927styled-by-prettify"> </span><span styl=
e=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">=3D</spa=
n><span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-pretti=
fy"> </span><span style=3D"color:#606" class=3D"m_3440269965916649927styled=
-by-prettify">SortedSet</span><span style=3D"color:#660" class=3D"m_3440269=
965916649927styled-by-prettify">(</span><span style=3D"color:#066" class=3D=
"m_3440269965916649927styled-by-prettify">1</span><span style=3D"color:#660=
" class=3D"m_3440269965916649927styled-by-prettify">,</span><span style=3D"=
color:#066" class=3D"m_3440269965916649927styled-by-prettify">2</span><span=
 style=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">,</=
span><span style=3D"color:#066" class=3D"m_3440269965916649927styled-by-pre=
ttify">3</span><span style=3D"color:#660" class=3D"m_3440269965916649927sty=
led-by-prettify">)(</span><span style=3D"color:#000" class=3D"m_34402699659=
16649927styled-by-prettify">ord</span><span style=3D"color:#660" class=3D"m=
_3440269965916649927styled-by-prettify">=3D</span><span style=3D"color:#606=
" class=3D"m_3440269965916649927styled-by-prettify">Ordering</span><span st=
yle=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">.</spa=
n><span style=3D"color:#606" class=3D"m_3440269965916649927styled-by-pretti=
fy"><wbr>Int</span><span style=3D"color:#660" class=3D"m_344026996591664992=
7styled-by-prettify">.</span><span style=3D"color:#000" class=3D"m_34402699=
65916649927styled-by-prettify">reverse</span><span style=3D"color:#660" cla=
ss=3D"m_3440269965916649927styled-by-prettify">)</span><span style=3D"color=
:#000" class=3D"m_3440269965916649927styled-by-prettify"><br></span><span s=
tyle=3D"color:#008" class=3D"m_3440269965916649927styled-by-prettify">set</=
span><span style=3D"color:#660" class=3D"m_3440269965916649927styled-by-pre=
ttify">:</span><span style=3D"color:#000" class=3D"m_3440269965916649927sty=
led-by-prettify"> scala</span><span style=3D"color:#660" class=3D"m_3440269=
965916649927styled-by-prettify">.</span><span style=3D"color:#000" class=3D=
"m_3440269965916649927styled-by-prettify">collection</span><span style=3D"c=
olor:#660" class=3D"m_3440269965916649927styled-by-prettify">.</span><span =
style=3D"color:#606" class=3D"m_3440269965916649927styled-by-prettify">Sort=
edSet</span><span style=3D"color:#660" class=3D"m_3440269965916649927styled=
-by-prettify">[</span><span style=3D"color:#606" class=3D"m_344026996591664=
9927styled-by-prettify">Int</span><span style=3D"color:#660" class=3D"m_344=
0269965916649927styled-by-prettify"><wbr>]</span><span style=3D"color:#000"=
 class=3D"m_3440269965916649927styled-by-prettify"> </span><span style=3D"c=
olor:#660" class=3D"m_3440269965916649927styled-by-prettify">=3D</span><spa=
n style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prettify"> <=
/span><span style=3D"color:#606" class=3D"m_3440269965916649927styled-by-pr=
ettify">TreeSet</span><span style=3D"color:#660" class=3D"m_344026996591664=
9927styled-by-prettify">(</span><span style=3D"color:#066" class=3D"m_34402=
69965916649927styled-by-prettify">3</span><span style=3D"color:#660" class=
=3D"m_3440269965916649927styled-by-prettify">,</span><span style=3D"color:#=
000" class=3D"m_3440269965916649927styled-by-prettify"> </span><span style=
=3D"color:#066" class=3D"m_3440269965916649927styled-by-prettify">2</span><=
span style=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify"=
>,</span><span style=3D"color:#000" class=3D"m_3440269965916649927styled-by=
-prettify"> </span><span style=3D"color:#066" class=3D"m_344026996591664992=
7styled-by-prettify">1</span><span style=3D"color:#660" class=3D"m_34402699=
65916649927styled-by-prettify">)</span><span style=3D"color:#000" class=3D"=
m_3440269965916649927styled-by-prettify"><br><br><br>scala</span><span styl=
e=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">&gt;</sp=
an><span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prett=
ify"> </span><span style=3D"color:#008" class=3D"m_3440269965916649927style=
d-by-prettify">set</span><span style=3D"color:#660" class=3D"m_344026996591=
6649927styled-by-prettify">.</span><span style=3D"color:#000" class=3D"m_34=
40269965916649927styled-by-prettify">firstKey </span><span style=3D"color:#=
660" class=3D"m_3440269965916649927styled-by-prettify">=3D=3D</span><span s=
tyle=3D"color:#000" class=3D"m_3440269965916649927styled-by-prettify"> </sp=
an><span style=3D"color:#008" class=3D"m_3440269965916649927styled-by-prett=
ify">set</span><span style=3D"color:#660" class=3D"m_3440269965916649927sty=
led-by-prettify">.</span><span style=3D"color:#000" class=3D"m_344026996591=
6649927styled-by-prettify">map</span><span style=3D"color:#660" class=3D"m_=
3440269965916649927styled-by-prettify">(</span><span style=3D"color:#000" c=
lass=3D"m_3440269965916649927styled-by-prettify">identity</span><span style=
=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">).</span>=
<span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prettify=
">firstKey<br>res0</span><span style=3D"color:#660" class=3D"m_344026996591=
6649927styled-by-prettify">:</span><span style=3D"color:#000" class=3D"m_34=
40269965916649927styled-by-prettify"> </span><span style=3D"color:#606" cla=
ss=3D"m_3440269965916649927styled-by-prettify">Boolean</span><span style=3D=
"color:#000" class=3D"m_3440269965916649927styled-by-prettify"> </span><spa=
n style=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">=
=3D</span><span style=3D"color:#000" class=3D"m_3440269965916649927styled-b=
y-prettify"> </span><span style=3D"color:#008" class=3D"m_34402699659166499=
27styled-by-prettify">false</span></div></code></div><div><br></div></div><=
div>My feeling is that mapping the identity function over any collection sh=
ould not change anything.</div><div><br></div><div>In this case it is clear=
 what is happening. The CanBuildFrom provided by SortedSet is pulling an Or=
dering instance out of predef (Ordering.Int) instead of using the ordering =
from the origin collection.</div><div class=3D"m_3440269965916649927prettyp=
rint" style=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,1=
87);border-style:solid;border-width:1px;word-wrap:break-word"><code class=
=3D"m_3440269965916649927prettyprint"><div class=3D"m_3440269965916649927su=
bprettyprint"><span style=3D"color:#000" class=3D"m_3440269965916649927styl=
ed-by-prettify">scala</span><span style=3D"color:#660" class=3D"m_344026996=
5916649927styled-by-prettify">&gt;</span><span style=3D"color:#000" class=
=3D"m_3440269965916649927styled-by-prettify"> </span><span style=3D"color:#=
008" class=3D"m_3440269965916649927styled-by-prettify">set</span><span styl=
e=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">.</span>=
<span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prettify=
">toList<br>res1</span><span style=3D"color:#660" class=3D"m_34402699659166=
49927styled-by-prettify">:</span><span style=3D"color:#000" class=3D"m_3440=
269965916649927styled-by-prettify"> </span><span style=3D"color:#606" class=
=3D"m_3440269965916649927styled-by-prettify">List</span><span style=3D"colo=
r:#660" class=3D"m_3440269965916649927styled-by-prettify">[</span><span sty=
le=3D"color:#606" class=3D"m_3440269965916649927styled-by-prettify">Int</sp=
an><span style=3D"color:#660" class=3D"m_3440269965916649927styled-by-prett=
ify">]</span><span style=3D"color:#000" class=3D"m_3440269965916649927style=
d-by-prettify"> </span><span style=3D"color:#660" class=3D"m_34402699659166=
49927styled-by-prettify">=3D</span><span style=3D"color:#000" class=3D"m_34=
40269965916649927styled-by-prettify"> </span><span style=3D"color:#606" cla=
ss=3D"m_3440269965916649927styled-by-prettify">List</span><span style=3D"co=
lor:#660" class=3D"m_3440269965916649927styled-by-prettify">(</span><span s=
tyle=3D"color:#066" class=3D"m_3440269965916649927styled-by-prettify">3</sp=
an><span style=3D"color:#660" class=3D"m_3440269965916649927styled-by-prett=
ify">,</span><span style=3D"color:#000" class=3D"m_3440269965916649927style=
d-by-prettify"> </span><span style=3D"color:#066" class=3D"m_34402699659166=
49927styled-by-prettify">2</span><span style=3D"color:#660" class=3D"m_3440=
269965916649927styled-by-prettify">,</span><span style=3D"color:#000" class=
=3D"m_3440269965916649927styled-by-prettify"> </span><span style=3D"color:#=
066" class=3D"m_3440269965916649927styled-by-prettify">1</span><span style=
=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">)</span><=
span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prettify"=
><br><br><br>scala</span><span style=3D"color:#660" class=3D"m_344026996591=
6649927styled-by-prettify">&gt;</span><span style=3D"color:#000" class=3D"m=
_3440269965916649927styled-by-prettify"> </span><span style=3D"color:#008" =
class=3D"m_3440269965916649927styled-by-prettify">set</span><span style=3D"=
color:#660" class=3D"m_3440269965916649927styled-by-prettify">.</span><span=
 style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prettify">map=
</span><span style=3D"color:#660" class=3D"m_3440269965916649927styled-by-p=
rettify">(</span><span style=3D"color:#000" class=3D"m_3440269965916649927s=
tyled-by-prettify">identity</span><span style=3D"color:#660" class=3D"m_344=
0269965916649927styled-by-prettify">).</span><span style=3D"color:#000" cla=
ss=3D"m_3440269965916649927styled-by-prettify">toList<br>res2</span><span s=
tyle=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">:</sp=
an><span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-prett=
ify"> </span><span style=3D"color:#606" class=3D"m_3440269965916649927style=
d-by-prettify">List</span><span style=3D"color:#660" class=3D"m_34402699659=
16649927styled-by-prettify">[</span><span style=3D"color:#606" class=3D"m_3=
440269965916649927styled-by-prettify">Int</span><span style=3D"color:#660" =
class=3D"m_3440269965916649927styled-by-prettify">]</span><span style=3D"co=
lor:#000" class=3D"m_3440269965916649927styled-by-prettify"> </span><span s=
tyle=3D"color:#660" class=3D"m_3440269965916649927styled-by-prettify">=3D</=
span><span style=3D"color:#000" class=3D"m_3440269965916649927styled-by-pre=
ttify"> </span><span style=3D"color:#606" class=3D"m_3440269965916649927sty=
led-by-prettify">List</span><span style=3D"color:#660" class=3D"m_344026996=
5916649927styled-by-prettify">(</span><span style=3D"color:#066" class=3D"m=
_3440269965916649927styled-by-prettify">1</span><span style=3D"color:#660" =
class=3D"m_3440269965916649927styled-by-prettify">,</span><span style=3D"co=
lor:#000" class=3D"m_3440269965916649927styled-by-prettify"> </span><span s=
tyle=3D"color:#066" class=3D"m_3440269965916649927styled-by-prettify">2</sp=
an><span style=3D"color:#660" class=3D"m_3440269965916649927styled-by-prett=
ify">,</span><span style=3D"color:#000" class=3D"m_3440269965916649927style=
d-by-prettify"> </span><span style=3D"color:#066" class=3D"m_34402699659166=
49927styled-by-prettify">3</span><span style=3D"color:#660" class=3D"m_3440=
269965916649927styled-by-prettify">)</span><span style=3D"color:#000" class=
=3D"m_3440269965916649927styled-by-prettify"><br><br></span><span class=3D"=
m_3440269965916649927styled-by-prettify"><font color=3D"#000000"><div class=
=3D"m_3440269965916649927subprettyprint">scala&gt; set.ordering</div><div c=
lass=3D"m_3440269965916649927subprettyprint">res3: Ordering[Int] =3D scala.=
math.Ordering$$anon$4@<wbr>3ff3275b</div><div class=3D"m_344026996591664992=
7subprettyprint"><br></div><div class=3D"m_3440269965916649927subprettyprin=
t">scala&gt; set.map(identity).ordering</div><div class=3D"m_34402699659166=
49927subprettyprint">res4: Ordering[Int] =3D scala.math.Ordering$Int$@<wbr>=
7fa85a55</div></font></span></div></code></div><div><div><br></div><div>I t=
hink this can be fixed by providing a more specific CanBuildFrom instance t=
o be used when mapping between two sorted collections that contain the same=
 type.</div></div><div><br></div><div>i.e. Provide a CanBuildFrom[Sorted[K,=
 _], K, Sorted[K, _]] somewhere that has precedence over the more generic u=
sual CanBuildFrom[CC[_], A, CC[A]]</div><div><br></div><div>I&#39;m not sur=
e how it could be done, but the static overloading resolution rules make th=
is possible, I think.</div></div><span class=3D"HOEnZb"><font color=3D"#888=
888">

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;scala-language&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:[email protected]" targ=
et=3D"_blank">scala-language+unsubscribe@<wbr>googlegroups.com</a>.<br>
For more options, visit <a href=3D"https://groups.google.com/d/optout" targ=
et=3D"_blank">https://groups.google.com/d/<wbr>optout</a>.<br>
</font></span></blockquote></div><br></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;scala-language&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:[email protected]">scal=
[email protected]</a>.<br />
For more options, visit <a href=3D"https://groups.google.com/d/optout">http=
s://groups.google.com/d/optout</a>.<br />

--001a11357dd69a8e37054269eff1--