Re: Sorted structures lose their ordering when mapped
Stephen Compall <[email protected]> Wed, 30 Nov 2016 08:33:35 -0500
| Newsgroups | gmane.comp.lang.scala |
|---|---|
| Message-ID | <[email protected]> |
------KM1OLB8YCJEM458MQI9DSX5UHKN46X Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8 On November 28, 2016 11:14:06 PM EST, Tobin Yehle <[email protected]> wr= ote: >Calling map on a collection that requires an implicit ordering results >in=20 >some surprising behavior. For example: > >scala> val set =3D SortedSet(1,2,3)(ord=3DOrdering.Int.reverse) >set: scala.collection.SortedSet[Int] =3D TreeSet(3, 2, 1) > > >scala> set.firstKey =3D=3D set.map(identity).firstKey >res0: Boolean =3D false > >My feeling is that mapping the identity function over any collection >should=20 >not change anything. > >In this case it is clear what is happening. The CanBuildFrom provided >by=20 >SortedSet is pulling an Ordering instance out of predef (Ordering.Int)=20 >instead of using the ordering from the origin collection. Doing so would introduce an identity law for your type at the expense of a = composition law, namely, set.map(f).map(g) =3D=3D set.map(f andThen g). e.= g. f =3D a =3D> (a, ()) g =3D a =3D> a._1 For the real Functor map, the type abstraction means that identity implies = composition. However, this map function isn't fully polymorphic in element= type, so you need more for that implication. Global typeclass coherence is strong enough to provide the implication, and= indeed, if you use "newtypes" like scalaz's Dual tag (whose ordering is re= versed from the underlying type), both identity and composition just work. = That gives you a SortedSet[Int @@ Dual]. However, this requires the discipline that you do not simply pass in an 'or= d' argument as you do above. Nevertheless, for refactorability sanity and a= fistful of such "obvious" equalities like the one you desire, I recommend = keeping to this "typeclass coherence" discipline. If you are uncomfortable with typeclass coherence, maybe you will be happy = with a path-dependent types approach. http://typelevel.org/blog/2016/11/17/= heaps.html -- Stephen Compall If anyone in the MSA is online, you should watch this flythrough. --=20 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 e= mail to [email protected]. For more options, visit https://groups.google.com/d/optout. ------KM1OLB8YCJEM458MQI9DSX5UHKN46X Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On November 28, 2016 11:14:06 PM EST, Tobin Yehle <[email protected]&= gt; wrote:<br> >Calling map on a collection that requires an implicit ordering results<= br> >in <br> >some surprising behavior. For example:<br> ><br> >scala> val set =3D SortedSet(1,2,3)(ord=3DOrdering.Int.reverse)<br> >set: scala.collection.SortedSet[Int] =3D TreeSet(3, 2, 1)<br> ><br> ><br> >scala> set.firstKey =3D=3D set.map(identity).firstKey<br> >res0: Boolean =3D false<br> ><br> >My feeling is that mapping the identity function over any collection<br= > >should <br> >not change anything.<br> ><br> >In this case it is clear what is happening. The CanBuildFrom provided<b= r> >by <br> >SortedSet is pulling an Ordering instance out of predef (Ordering.Int) = <br> >instead of using the ordering from the origin collection.<br> <br> Doing so would introduce an identity law for your type at the expense of a = composition law, namely, set.map(f).map(g) =3D=3D set.map(f andThen g). e.= g.<br> <br> f =3D a =3D> (a, ())<br> g =3D a =3D> a._1<br> <br> For the real Functor map, the type abstraction means that identity implies = composition. However, this map function isn't fully polymorphic in ele= ment type, so you need more for that implication.<br> <br> Global typeclass coherence is strong enough to provide the implication, and= indeed, if you use "newtypes" like scalaz's Dual tag (whose = ordering is reversed from the underlying type), both identity and compositi= on just work. That gives you a SortedSet[Int @@ Dual].<br> <br> However, this requires the discipline that you do not simply pass in an = 9;ord' argument as you do above. Nevertheless, for refactorability sani= ty and a fistful of such "obvious" equalities like the one you de= sire, I recommend keeping to this "typeclass coherence" disciplin= e.<br> <br> If you are uncomfortable with typeclass coherence, maybe you will be happy = with a path-dependent types approach. <a href=3D"http://typelevel.org/blog/= 2016/11/17/heaps.html">http://typelevel.org/blog/2016/11/17/heaps.html</a><= br> <br> --<br> Stephen Compall<br> If anyone in the MSA is online, you should watch this flythrough. <p></p> -- <br /> You received this message because you are subscribed to the Google Groups &= quot;scala-language" 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 /> ------KM1OLB8YCJEM458MQI9DSX5UHKN46X--