Re: Sorted structures lose their ordering when mapped

--94eb2c0483c0c3cfa2054287ad56
Content-Type: text/plain; charset=UTF-8

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.

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

<div dir=3D"ltr">I guess the issue is, which category are we in? Posets, su=
ddenly? Linear orders? Scala is not sophisticated enough to provide suddenl=
y a specialization into such categories, so that map preserves order, or, n=
ext time, preserves monoidal operations, or be continuous, or be linear.<di=
v><br></div><div>Would be nice though. Probably not in this century.</div><=
/div><div class=3D"gmail_extra"><br clear=3D"all"><div><div class=3D"gmail_=
signature" data-smartmail=3D"gmail_signature">Thanks,<br>-Vlad</div></div>
<br><div class=3D"gmail_quote">On Wed, Nov 30, 2016 at 5:33 AM, Stephen Com=
pall <span dir=3D"ltr">&lt;<a href=3D"mailto:[email protected]" target=3D"=
_blank">[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"><span class=3D"">On November 28, 2016 11:14:06 PM EST, Tobin Yehle =
&lt;<a href=3D"mailto:[email protected]" target=3D"_blank">tobinyehle@gm=
ail.com</a>&gt; wrote:<br>
&gt;Calling map on a collection that requires an implicit ordering results<=
br>
&gt;in <br>
&gt;some surprising behavior. For example:<br>
&gt;<br>
&gt;scala&gt; val set =3D SortedSet(1,2,3)(ord=3DOrdering.<wbr>Int.reverse)=
<br>
&gt;set: scala.collection.SortedSet[<wbr>Int] =3D TreeSet(3, 2, 1)<br>
&gt;<br>
&gt;<br>
&gt;scala&gt; set.firstKey =3D=3D set.map(identity).firstKey<br>
&gt;res0: Boolean =3D false<br>
&gt;<br>
&gt;My feeling is that mapping the identity function over any collection<br=
>
&gt;should <br>
&gt;not change anything.<br>
&gt;<br>
&gt;In this case it is clear what is happening. The CanBuildFrom provided<b=
r>
&gt;by <br>
&gt;SortedSet is pulling an Ordering instance out of predef (Ordering.Int) =
<br>
&gt;instead of using the ordering from the origin collection.<br>
<br></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>
<br>
f =3D a =3D&gt; (a, ())<br>
g =3D a =3D&gt; a._1<br>
<br>
For the real Functor map, the type abstraction means that identity implies =
composition.  However, this map function isn&#39;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 &quot;newtypes&quot; like scalaz&#39;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 &#3=
9;ord&#39; argument as you do above. Nevertheless, for refactorability sani=
ty and a fistful of such &quot;obvious&quot; equalities like the one you de=
sire, I recommend keeping to this &quot;typeclass coherence&quot; 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" target=3D"_blank">http://typelevel.org/blog/<wbr>201=
6/11/17/heaps.html</a><br>
<br>
--<br>
Stephen Compall<br>
If anyone in the MSA is online, you should watch this flythrough.

<div class=3D"HOEnZb"><div class=3D"h5"><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>
</div></div></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 />

--94eb2c0483c0c3cfa2054287ad56--