I'm quite in favor of the 'toTrav' flavor of the Foldable law, but I'm pretty strongly against the suggestion that Functor + Foldable must be Traversable. There are reasonable instances that lie in the middle that satisfy the injectivity law and can also be functors. The LZ78 compressed stream stuff that can decompress in any target monoid, the newtype Replicate a = Replicate !Int a for run-length encoding. You can build meaningful Foldable instances for all sorts of graph types that have lots of sharing in them. This law would rule out any Foldable that exploited its nature to improve sharing on the intermediate results. These are in many ways the most interesting and under-exploited points in the Foldable design space. That functionality and the ability to know something about your argument are the two tools offered to you as an author of an instance of Foldable that aren't offered to you with Traversable. fold = foldMap id, states the behavior of fold in terms of foldMap.The other direction defining foldMap in terms of fold and fmap is a free theorem. Hence all of the current interoperability of Foldable and Functor comes for free. No interactions need actually be written as extra laws. But Traversable is not the pushout of the theory of Functor and Traversable. Anything that lies in that middle ground would be needlessly unable to be expressed in exchange for a shiny new "law" that doesn't let you write any new code. I think there is a pretty real distinction between Foldable instances that avoid some of the 'a's like the hinky instance for the Machine type in machines, and ones that can reuse intermediate monoidal results multiple times and gain significant performance dividends for many monoids. The toTrav law at least captures the intuition that "you visit all the 'a's, and rules out the common argument that foldMap _ = mempty is always valid but useless, but adding this law would replace lots of potential O(log n) performance bounds with mandatory O(n) performance bounds, and not offer a single extra line of compiling code to compensate for this loss: Remember you'd have to incur a stronger constraint to actually be able to `traverse` anyways, it can't be written with just the parts of Foldable and Traversable, so nothing is gained and informative cases are definitely lost. (Foldable f, Functor f) is strictly weaker than Traversable f. -Edward On Sun, May 6, 2018 at 12:40 AM, David Feuer <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by David Feuer
You can get stuck with contravariance in some fashion on the backswing, though, just from holding onto instance constraints about the type 'a'. e.g. If your Foldable data type captures a Num instance for 'a', it could build fresh 'a's out of the ones you have lying around. There isn't a huge difference between that and just capturing the member of Num that you use. -Edward On Sun, May 6, 2018 at 3:37 PM, David Feuer <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Edward Kmett-2
No objection to leaving that out if it's a problem, but I'm curious about the details of your example. On Sun, May 6, 2018, 6:01 PM Edward Kmett <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
In reply to this post by Edward Kmett-2
I don't understand. Something like
data Foo a where Foo :: Num a => a -> Foo a has a perfectly good "forgetful" injection: toTrav (Foo a) = Identity a This is injective because of class coherence. On Sun, May 6, 2018, 6:04 PM Edward Kmett <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Fair point. I was more thinking about the fact that you don't necessarily visit all of the a's because you can use the combinators you have there to generate an unbounded number of combination of them than the injectivity concern. On Sun, May 6, 2018 at 7:28 PM, David Feuer <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Still not sure I understand what you mean. The injectivity condition makes it hard to ignore almost anything (unless it's hidden by an abstraction barrier, existential type, etc.). I don't think Num is strong enough for funny business. Integral is, though: data Bar a where Bar :: Integral a => a -> Bar a instance Foldable Bar where foldMap _ _ = mempty type Trav Bar = Const Integer toTrav (Bar a) = Const (toInteger a) On Sun, May 6, 2018, 7:39 PM Edward Kmett <[hidden email]> wrote:
_______________________________________________ Libraries mailing list [hidden email] http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries |
Free forum by Nabble | Edit this page |