<div dir="ltr">On Fri, Sep 13, 2013 at 12:48 AM, Michael Snoyman <span dir="ltr"><<a href="mailto:michael@snoyman.com" target="_blank">michael@snoyman.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote"><div class="im">On Thu, Sep 12, 2013 at 2:37 AM, John Lato <span dir="ltr"><<a href="mailto:jwlato@gmail.com" target="_blank">jwlato@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">I didn't see this message and replied privately to Michael earlier, so I'm replicating my comments here.<br>
<br></div></blockquote><div><br></div></div><div>Sorry about that, I wrote to you privately first and then thought this might be a good discussion for the cafe.</div><div class="im"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div>1. Sooner or later I expect you'll want something like this:<br><pre><div><span>class</span> <span>LooseMap</span> <span>c</span> <span>el</span> <span>el'</span> <span>where</span></div>
<div> <span>lMap</span> <span>::</span> <span>(</span><span>el</span> <span>-></span> <span>el'</span><span>)</span> <span>-></span> <span>c</span> <span>el</span> <span>-></span> <span>c</span> <span>el'<br>
</span></div></pre></div><div>
It covers the case of things like hashmaps/unboxed vectors that have
class constraints on elements. Although maybe LooseFunctor or LFunctor
is a better name.<br></div><div><br></div><div>Probably something similar for Traversable would be good also, as would a default instance in terms of Functor.<br>
</div><div><br></div></div></blockquote><div><br></div></div><div>That's interesting. It's quite similar to the CanMap[1] class in classy-prelude or Each from lens, except it can drop a type parameter and the fundeps by requiring the container to be polymorphic. If we're willing to use more exotic extensions, ConstraintKinds could be useful as well:</div>
<div><br></div><div><div>class ConstrainedMap t where</div><div> type MapConstraint t e :: Constraint</div><div> cMap :: (MapConstraint t e1, MapConstraint t e2) => (e1 -> e2) -> t e1 -> t e2</div><div>
instance ConstrainedMap Set.Set where</div>
<div> type MapConstraint Set.Set e = Ord e</div><div> cMap = Set.map</div></div><div><br></div><div>One reason I'd definitely not want to call this anything with the name Functor in it is because Set.map can violate the Functor laws, in particular:</div>
<div><br></div><div> Set.map (f . g) /= Set.map f . Set.map g</div><div><br></div><div>I believe the only law that could be applied to Set.map would be:</div><div><br></div><div> Set.map f = Set.fromList . List.map f . Set.toList</div>
<div><br></div><div>I would presume this would generalize to any other possible instance.</div></div></div></div></blockquote><div><br></div>Would it make more sense to just say that all instances must obey the Functor laws, thereby not allowing the Set instance? That might make it easier to reason about using the class. Although I've never needed that when I've used it in the past, so I guess whichever you think is more useful is fine by me.<br>
</div><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div>
<div>One final idea would be to take your LooseMap and apply the same kind of monomorphic conversion the rest of the library uses:</div>
<div><br></div><div><div>class MonoLooseMap c1 c2 | c1 -> c2, c2 -> c1 where</div><div> mlMap :: (Element c1 -> Element c2) -> c1 -> c2</div><div>instance (Ord e1, Ord e2) => MonoLooseMap (Set.Set e1) (Set.Set e2) where</div>
<div> mlMap = Set.map</div></div><div><br></div><div>Of all of them, ConstrainedMap seems like it would be the most user-friendly, as error messages would just have a single type parameter. But I don't have any strong leanings.</div>
</div></div></div></blockquote><div><br></div><div>I agree that ConstrainedMap would likely be the most user-friendly. It also seems to best express the actual relationship between the various components, so it would be my preferred choice. <br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">
<div><br></div><div>[1] <a href="http://haddocks.fpcomplete.com/fp/7.4.2/20130829-168/classy-prelude/ClassyPrelude-Classes.html#t:CanMap" target="_blank">http://haddocks.fpcomplete.com/fp/7.4.2/20130829-168/classy-prelude/ClassyPrelude-Classes.html#t:CanMap</a></div>
<div class="im">
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>
</div><div>2. IMHO cMapM_ (and related) should be part of the Foldable class. This is entirely for performance reasons,
but there's no downside since you can just provide a default instance.<br>
<br></div></div></blockquote><div><br></div></div><div>Makes sense to me, done. By the way, this can't be done for sum/product, because those require a constraint on the Element.</div><div class="im"><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div></div><div>3. I'm not entirely sure that the length* functions
belong here. I understand why, and I think it's sensible
reasoning, and I don't have a good argument against it, but I just don't
like it. With those, and mapM_-like functions, it seems that the
foldable class is halfway to being another monolithic ListLike. But I
don't have any better ideas either.<br>
</div><div><br></div></div></blockquote><div><br></div></div><div>I agree here, but like you said in (2), it's a performance concern. The distinction I'd make from ListLike is that you only have to define foldr/foldl to get a valid instance (and even that could be dropped to just foldr, except for conflicts with the default signatures extension).<br>
</div></div></div></div></blockquote><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div class="im">
<div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div></div>As to the bikeshed color, I would
prefer to just call the classes Foldable/Traversable. People can use
qualified imports to disambiguate when writing instances, and at call
sites client code would never need Data.{Foldable|Traversable} and can
just use these versions instead. I'd still want a separate name for
Functor though, since it's in the Prelude, so maybe it's better to be
consistent. My $.02.<br></div><div><div><div class="gmail_extra"><br></div></div></div></blockquote><div><br></div></div><div>I prefer avoiding the name conflict, for a few reasons:</div><div><div><ul><li>In something like ClassyPrelude, we can export both typeclasses without a proper if they have separate names.</li>
<li>Error messages and documentation will be clearer. Consider how the type signature `ByteString -> foo` doesn't let you know whether it's a strict or lazy bytestring.</li><li>I got specific feedback from Edward that it would be easier to include instances for these classes if the names didn't clash with standard terminology.</li>
<li>It leaves the door open for including this concept upstream in the future, even if that's not the goal for now.<br></li></ul></div></div></div></div></div></blockquote>Sounds reasonable.<br></div><div class="gmail_quote">
<div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div class="h5"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><div><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Sep 11, 2013 at 3:25 PM, Michael Snoyman <span dir="ltr"><<a href="mailto:michael@snoyman.com" target="_blank">michael@snoyman.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">That's really funny timing. I started work on a very similar project just this week:<div>
<br></div>
<div>
<a href="https://github.com/snoyberg/mono-traversable" target="_blank">https://github.com/snoyberg/mono-traversable</a><br>
</div><div><br></div><div>It's not refined yet, which is why I haven't discussed it too publicly, but it's probably at the point where some review would make sense. There's been a bit of a discussion on a separate Github issue[1] about it.</div>
<div><br></div><div>A few caveats:</div><div><ul><li>The names are completely up for debate, many of them could be improved.<br></li><li>The laws aren't documented yet, but they mirror the laws for the polymorphic classes these classes are based on.</li>
<li>The Data.MonoTraversable module is the main module to look at. The other two are far more nascent (though I'd definitely appreciate feedback people have on them).</li></ul><div>I think this and mono-foldable have a lot of overlap, I'd be interested to hear what you think in particular John.</div>
</div><div><br></div><div>Michael</div><div><br></div><div>[1] <a href="https://github.com/snoyberg/classy-prelude/issues/18" target="_blank">https://github.com/snoyberg/classy-prelude/issues/18</a></div>
<div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Sep 11, 2013 at 11:05 PM, John Lato <span dir="ltr"><<a href="mailto:jwlato@gmail.com" target="_blank">jwlato@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr"><div><div>I agree with everything Edward has said already. I went through a
similar chain of reasoning a few years ago when I started using
ListLike, which provides a FoldableLL class (although it uses fundeps as
ListLike predates type families). ByteString can't be a Foldable instance, nor do I think most people would want it to be.<br><br></div><div>Even though I would also like to see mapM_ in bytestring, it's probably faster to have a library with a separate monomorphic Foldable class. So I just wrote one:<br>
<br><a href="https://github.com/JohnLato/mono-foldable" target="_blank">https://github.com/JohnLato/mono-foldable</a><br><a href="http://hackage.haskell.org/package/mono-foldable" target="_blank">http://hackage.haskell.org/package/mono-foldable</a><br>
</div>
<div><br></div>Petr Pudlak has done some work in this area. A big problem is that foldM/mapM_ are typically implemented in terms of Foldable.foldr (or FoldableLL), but this isn't always optimal for performance. They really need to be part of the type class so that different container types can have specialized implementations. I did that in mono-foldable, using Artyom's map implementation (Artyom, please let me know if you object to this!)<br>
<br></div><div>pull requests, forks, etc all welcome.<br></div><div><br></div><div>John L.<br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote"><div><div>On Wed, Sep 11, 2013 at 1:29 PM, Edward Kmett <span dir="ltr"><<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>></span> wrote:<br>
</div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div><div dir="ltr">mapM_ is actually implemented in terms of Foldable, not Traversable, and its implementation in terms of folding a ByteString is actually rather slow in my experience doing so inside lens and isn't much faster than the naive version that was suggested at the start of this discussion.<div>
<br></div><div>But as we're not monomorphizing Foldable/Traversable, this isn't a think that is able to happen anyways.<span><font color="#888888"><br><div><br></div><div>-Edward</div></font></span></div>
</div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Wed, Sep 11, 2013 at 2:25 PM, Henning Thielemann <span dir="ltr"><<a href="mailto:lemming@henning-thielemann.de" target="_blank">lemming@henning-thielemann.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div><br>
On Wed, 11 Sep 2013, Duncan Coutts wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
For mapM etc, personally I think a better solution would be if<br>
ByteString and Text and other specialised containers could be an<br>
instance of Foldable/Traversable. Those classes define mapM etc but<br>
currently they only work for containers that are polymorphic in their<br>
elements, so all specialised containers are excluded. I'm sure there<br>
must be a solution to that (I'd guess with type families) and that would<br>
be much nicer than adding mapM etc to bytestring itself. We would then<br>
just provide efficient instances for Foldable/Traversable.<br>
</blockquote>
<br></div>
I'd prefer to keep bytestring simple with respect to the number of type extensions. Since you must implement ByteString.mapM anyway, you can plug this into an instance definition of Traversable ByteString.<br>
</blockquote></div><br></div>
</div></div><br></div></div><div>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
<br></div></blockquote></div><br></div>
<br>_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank">Libraries@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/libraries" target="_blank">http://www.haskell.org/mailman/listinfo/libraries</a><br>
<br></blockquote></div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div></div></div><br></div></div>
</blockquote></div><br></div></div>