Re: Sorted structures lose their ordering when mapped
Tobin Yehle <[email protected]> Wed, 30 Nov 2016 21:30:04 +0000
| Newsgroups | gmane.comp.lang.scala |
|---|---|
| Message-ID | <CABx_kgT-xHU5KhqKhybd3wJNGC5qxz2DkFPyYCTMuToeRxWBgw@mail.gmail.com> |
--94eb2c0647fc249cad05428b694a Content-Type: text/plain; charset=UTF-8 Haha, clearly copying the ordering doesn't solve any problems. Thanks for the responses everyone. Thanks for the examples Stephen, that makes a lot of sense. If not having typeclass coherence causes such problems would it be possible to give a compiler warning if someone like me breaks it? In this case manually specifying an implicit parameter that is being used as a a typeclass? It looks like for all the examples I gave it would be better to just put an implicit reversed order in the local scope. eg: implicit val revOrd = Ordering.Int.reverse val set = SortedSet(1,2,3) set.map(_*2) // TreeSet(6,4,2) set.map(i => i -> "a"*i)(breakOut):SortedMap[Int, String] // TreeMap(3 -> aaa, 2 -> aa, 1 -> a) Is this style considered best practice? On Wed, Nov 30, 2016 at 10:03 AM Vlad Patryshev <[email protected]> wrote: > I guess the issue is, which category are we in? Posets, suddenly? Linear > orders? Scala is not sophisticated enough to provide suddenly a > specialization into such categories, so that map preserves order, or, next > time, preserves monoidal operations, or be continuous, or be linear. > > Would be nice though. Probably not in this century. > > Thanks, > -Vlad > > On Wed, Nov 30, 2016 at 5:33 AM, Stephen Compall <[email protected]> > wrote: > > On November 28, 2016 11:14:06 PM EST, Tobin Yehle <[email protected]> > wrote: > >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. > > Doing so would introduce an identity law for your type at the expense of a > composition law, namely, set.map(f).map(g) == set.map(f andThen g). e.g. > > f = a => (a, ()) > g = a => 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 > reversed 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 > 'ord' 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. > > -- > > 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. --94eb2c0647fc249cad05428b694a Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Haha, clearly copying the ordering doesn't solve any p= roblems. Thanks for the responses everyone.<div><br></div><div>Thanks for t= he examples Stephen, that makes a lot of sense. If not having typeclass coh= erence causes such problems would it be possible to give a compiler warning= if someone like me breaks it? In this case manually specifying an implicit= parameter that is being used as a a typeclass? It looks like for all the e= xamples I gave it would be better to just put an implicit reversed order in= the local scope. eg:<div>implicit val revOrd =3D Ordering.Int.reverse</div= ><div>val set =3D SortedSet(1,2,3)</div><div>set.map(_*2) // TreeSet(6,4,2)= </div><div>set.map(i =3D> i -> "a"*i)(breakOut):SortedMap[I= nt, String] // TreeMap(3 -> aaa, 2 -> aa, 1 -> a)</div><div><br></= div><div>Is this style considered best practice?</div></div></div><br><div = class=3D"gmail_quote"><div dir=3D"ltr">On Wed, Nov 30, 2016 at 10:03 AM Vla= d Patryshev <<a href=3D"mailto:[email protected]">[email protected]= m</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin= :0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr" c= lass=3D"gmail_msg">I guess the issue is, which category are we in? Posets, = suddenly? Linear orders? Scala is not sophisticated enough to provide sudde= nly a specialization into such categories, so that map preserves order, or,= next time, preserves monoidal operations, or be continuous, or be linear.<= div class=3D"gmail_msg"><br class=3D"gmail_msg"></div><div class=3D"gmail_m= sg">Would be nice though. Probably not in this century.</div></div><div cla= ss=3D"gmail_extra gmail_msg"><br clear=3D"all" class=3D"gmail_msg"><div cla= ss=3D"gmail_msg"><div class=3D"m_-5010915488430390527gmail_signature gmail_= msg" data-smartmail=3D"gmail_signature">Thanks,<br class=3D"gmail_msg">-Vla= d</div></div> <br class=3D"gmail_msg"><div class=3D"gmail_quote gmail_msg"></div></div><d= iv class=3D"gmail_extra gmail_msg"><div class=3D"gmail_quote gmail_msg">On = Wed, Nov 30, 2016 at 5:33 AM, Stephen Compall <span dir=3D"ltr" class=3D"gm= ail_msg"><<a href=3D"mailto:[email protected]" class=3D"gmail_msg" targ= et=3D"_blank">[email protected]</a>></span> wrote:<br class=3D"gmail_ms= g"></div></div><div class=3D"gmail_extra gmail_msg"><div class=3D"gmail_quo= te gmail_msg"><blockquote class=3D"gmail_quote gmail_msg" style=3D"margin:0= 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=3D"gmail= _msg">On November 28, 2016 11:14:06 PM EST, Tobin Yehle <<a href=3D"mail= to:[email protected]" class=3D"gmail_msg" target=3D"_blank">tobinyehle@g= mail.com</a>> wrote:<br class=3D"gmail_msg"> >Calling map on a collection that requires an implicit ordering results<= br class=3D"gmail_msg"> >in <br class=3D"gmail_msg"> >some surprising behavior. For example:<br class=3D"gmail_msg"> ><br class=3D"gmail_msg"> >scala> val set =3D SortedSet(1,2,3)(ord=3DOrdering.Int.reverse)<br c= lass=3D"gmail_msg"> >set: scala.collection.SortedSet[Int] =3D TreeSet(3, 2, 1)<br class=3D"g= mail_msg"> ><br class=3D"gmail_msg"> ><br class=3D"gmail_msg"> >scala> set.firstKey =3D=3D set.map(identity).firstKey<br class=3D"gm= ail_msg"> >res0: Boolean =3D false<br class=3D"gmail_msg"> ><br class=3D"gmail_msg"> >My feeling is that mapping the identity function over any collection<br= class=3D"gmail_msg"> >should <br class=3D"gmail_msg"> >not change anything.<br class=3D"gmail_msg"> ><br class=3D"gmail_msg"> >In this case it is clear what is happening. The CanBuildFrom provided<b= r class=3D"gmail_msg"> >by <br class=3D"gmail_msg"> >SortedSet is pulling an Ordering instance out of predef (Ordering.Int) = <br class=3D"gmail_msg"> >instead of using the ordering from the origin collection.<br class=3D"g= mail_msg"> <br class=3D"gmail_msg"></span> 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 class=3D"gmail_msg"> <br class=3D"gmail_msg"> f =3D a =3D> (a, ())<br class=3D"gmail_msg"> g =3D a =3D> a._1<br class=3D"gmail_msg"> <br class=3D"gmail_msg"> 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 class=3D"gmail_msg"> <br class=3D"gmail_msg"> 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 class=3D"gmail_ms= g"> <br class=3D"gmail_msg"> 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 class=3D"gmail_msg"> <br class=3D"gmail_msg"> 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" class=3D"gmail_msg" target=3D"_blank">http://typelev= el.org/blog/2016/11/17/heaps.html</a><br class=3D"gmail_msg"> <br class=3D"gmail_msg"> --<br class=3D"gmail_msg"> Stephen Compall<br class=3D"gmail_msg"> If anyone in the MSA is online, you should watch this flythrough. </blockquote></div></div><div class=3D"gmail_extra gmail_msg"><div class=3D= "gmail_quote gmail_msg"><blockquote class=3D"gmail_quote gmail_msg" style= =3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div cla= ss=3D"m_-5010915488430390527HOEnZb gmail_msg"><div class=3D"m_-501091548843= 0390527h5 gmail_msg"><p class=3D"gmail_msg"></p> -- <br class=3D"gmail_msg"></div></div></blockquote></div></div><div class= =3D"gmail_extra gmail_msg"><div class=3D"gmail_quote gmail_msg"><blockquote= class=3D"gmail_quote gmail_msg" style=3D"margin:0 0 0 .8ex;border-left:1px= #ccc solid;padding-left:1ex"><div class=3D"m_-5010915488430390527HOEnZb gm= ail_msg"><div class=3D"m_-5010915488430390527h5 gmail_msg"> You received this message because you are subscribed to the Google Groups &= quot;scala-language" group.<br class=3D"gmail_msg"></div></div></block= quote></div></div><div class=3D"gmail_extra gmail_msg"><div class=3D"gmail_= quote gmail_msg"><blockquote class=3D"gmail_quote gmail_msg" style=3D"margi= n:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class=3D"m_-= 5010915488430390527HOEnZb gmail_msg"><div class=3D"m_-5010915488430390527h5= gmail_msg"> To unsubscribe from this group and stop receiving emails from it, send an e= mail to <a href=3D"mailto:[email protected]" clas= s=3D"gmail_msg" target=3D"_blank">[email protected]= om</a>.</div></div></blockquote></div></div><div class=3D"gmail_extra gmail= _msg"><div class=3D"gmail_quote gmail_msg"><blockquote class=3D"gmail_quote= gmail_msg" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-l= eft:1ex"><div class=3D"m_-5010915488430390527HOEnZb gmail_msg"><div class= =3D"m_-5010915488430390527h5 gmail_msg"><br class=3D"gmail_msg"> For more options, visit <a href=3D"https://groups.google.com/d/optout" clas= s=3D"gmail_msg" target=3D"_blank">https://groups.google.com/d/optout</a>.<b= r class=3D"gmail_msg"> </div></div></blockquote></div></div></blockquote></div> <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 /> --94eb2c0647fc249cad05428b694a--