<div dir="ltr"><div><span style="font-size:12.8000001907349px">I think I can now float an amended law that is a further step in the right direction. First I will give the law, and then I will attempt to both motivate why the amended treatment is needed, and why the weakening of the initial proposal is a legitimate approach. Finally, I will discuss some remaining issues that it would be nice to examine, including some sketches of related but alternate approaches.</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">So, the new law:</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">===</span></div><div><div style="font-size:12.8000001907349px">for a lawful Foldable f, and</div><div style="font-size:12.8000001907349px"><br></div><div style="font-size:12.8000001907349px"><div><span style="font-size:12.8000001907349px">given a fresh newtype GenericSet = GenericSet Integer deriving (Eq, Ord), and mkGenericSet = GenericSet, where GenericSet is otherwise fully abstract</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div><span style="font-size:12.8000001907349px">then</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><span style="font-size:12.8000001907349px">forall (g :: forall a. f a -> Maybe a), (x :: f GenericSet). maybe True (`Foldable.elem` x) (g x) === True</span></div></div><div><span style="font-size:12.8000001907349px">==</span></div><div><span style="font-size:12.8000001907349px"><br></span></div><div>You may recall that the prior formulation asked that this condition hold for all a., (x :: f a), and so required an external notion of equality. Here, we ask that it only hold at a _specified type_ -- i.e. "GenericSet".</div><div><br></div><div>So, in what sense was the older formulation "too strong"? Here is a minimal case.</div><div><br></div><div>data TBox a where</div><div>   TAny :: a -> TBox a</div><div>   TString :: String -> TBox String</div><div><br></div><div>TBox is just a box with some optional type information, and it should be able to be equipped with the obvious Foldable instance. However, we can now write a function such as</div><div><br></div><div>discrim :: forall a. TBox a -> Maybe a</div><div>discrim (TAny x) = Just x</div><div>discrim (TString _) = "zoinks"</div><div><br></div><div>This is to say that if we _know_ that TBox contains a string, we can now take _any_ string out of it. Clearly, the existence of such functions means that the obvious Foldable instance cannot satisfy the stronger law.</div><div><br></div><div>By contrast, the straightforward Foldable instance for TBox still satisfies the weaker law, as we only test the action on "GenericSet" -- and since we have defined GenericSet as a fresh newtype, we know that it cannot have a tag to be matched on within a GADT we have already defined. Hence, our law, though it gives a universal property, does not give this property itself "universally" _at every type a_ but rather at a "generic type". This is by analogy with the technique of using "generic points" in algebraic geometry [1] to give properties that are not "everywhere true" but instead are true "almost everywhere", with a precise meaning given to "almost" -- i.e. that the space for which they do not hold _vanishes_.</div><div><br></div><div>This is to say, a Foldable satisfying the proposed law will not have the property hold "at all types," but rather at "almost all types" for an analogously precise meaning of "almost". I believe that a statement of why GenericSet is indeed "generic" in some topological sense is possible, although I have not fully fleshed this out.</div><div><br></div><div>To my knowledge, the introduction of this sort of approach in an FP context is new, but I would welcome any references showing prior art.</div><div><br></div><div>Aside from dealing with GADTs in some fashion, the new approach has a few other useful features. First, by formulating things directly in terms of "Foldable.elem" we omit the need for some sort of notion of equality in the metalogic -- instead we can use the "Eq" typeclass directly. Furthermore, this happens to sidestep the "toList" problem in the initial approach -- it directly allows search of potentially infinite structures.</div><div><br></div><div>There are still a few things that could potentially be better.</div><div><br></div><div>1) The "fully internal" approach means that we are now subject to the "bias" of "||" -- that is to say that _|_ || True -> _|_, but True || _|_ -> True. So we do not fully capture the searchability of infinite structures. This may indicate that a retreat to a metalogical description of "elem" with unbiased "or" is in order.</div><div><br></div><div>2) While we can generically characterize a Foldable instance on some f "almost everywhere" this is at the cost of giving it _no_ characterization at the points where our generic characterization fails. It would be nice to establish some sort of relation between the generic characterization and the action at specified points. However, I am not quite sure how to present this. An alternate approach could be to specify a Foldable law for any `f` that first takes `f` (which may be a GADT) to a related type `f1` (which must be an ordinary ADT) that squashes or omits dictionaries and equality constraints, and likewise takes the Foldable instance to a related instance on f1, and then provides a condition on f1. So rather that retreating from universal to generic properties, we instead take hold of the machinery of logical relations directly to establish a law. I would be interested in being pointed to related work along these lines as well.</div><div><br></div><div>3) An additional drawback of the "Generic Point" approach as given is that we chose to derive only two particular typeclasses -- Eq and Ord. An alternate approach would be to quantify over all a, but then give the property in terms of say "newtype Generify a = Generify a deriving (...)" which derives all classes on "a" that do not feature "a" in a positive position. Doing this would also mean a retreat from a fully internal notion of equality, of course...</div><div><br></div><div>Anyway, this is clearly still work in progress, but I would appreciate any feedback on the direction this is going, or references that may seem useful.</div><div><br></div><div>Cheers,</div><div>Gershom</div><div><br></div><div>[1] <a href="https://en.wikipedia.org/wiki/Generic_point">https://en.wikipedia.org/wiki/Generic_point</a></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 12, 2015 at 6:33 PM, Edward Kmett <span dir="ltr"><<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">With Foldable we <b>do</b> have a very nice law around foldMap.<div><br></div><div>A monoid homomorphism g is a combinator such that</div><div><br></div><div><font face="monospace, monospace">g mempty = mempty</font></div><div><font face="monospace, monospace">g (mappend a b) = mappend (g a) (mappend (g b)</font></div><div><br></div><div>For any monoid homomorphism g,</div><div><br></div><div><font face="monospace, monospace">foldMap (g . f) = g . foldMap f</font></div><div><br></div><div>We can use that to construct proofs of an analogue to "the banana split theorem" for foldr, but rephrased in terms of foldMap:</div><div><br></div><div><font face="monospace, monospace">foldMap f &&& foldMap g = foldMap (f &&& g)</font></div><div><br></div><div>Getting there uses the fact that fst and snd are both monoid homomorphisms.</div><div><br></div><div>There are also laws relating the behavior of all of the other combinators in Foldable to foldMap.</div><div><br></div><div>Ultimately the reasons for the other members of the class are a sop to efficiency concerns: asymptotic factors in terms of time or stack usage matter.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>-Edward</div><div><br></div></font></span></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Feb 12, 2015 at 5:22 PM, Kim-Ee Yeoh <span dir="ltr"><<a href="mailto:ky3@atamo.com" target="_blank">ky3@atamo.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>(removing Libraries, since not everyone on HC is on that list)<br><br></div><div>I do not know all of the context of Foldable, but one I do know that's not been mentioned is the implicit rule-of-thumb that every type class should have a law.<br><br></div><div>So the undercurrent is that if Foldable doesn't have a law, should it even be a type class? This has led to efforts to uncover laws for Foldable.<br><br></div><div>Worth discussing in a separate thread is the criterion itself of "if it doesn't have a law, it's not a type class". Useful sometimes, but that's not the sine qua non of type classes.<span><font color="#888888"><br><br><br></font></span></div></div><div class="gmail_extra"><span><font color="#888888"><br clear="all"><div><div>-- Kim-Ee</div></div>
<br></font></span><div class="gmail_quote"><div><div>On Fri, Feb 13, 2015 at 2:47 AM, Gershom B <span dir="ltr"><<a href="mailto:gershomb@gmail.com" target="_blank">gershomb@gmail.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><div dir="ltr">For a long time, many people, including me, have said that "Foldable has no laws" (or Foldable only has free laws) -- this is true, as it stands, with the exception that Foldable has a non-free law in interaction with Traversable (namely that it act as a proper specialization of Traversable methods). However, I believe that there is a good law we can give for Foldable. <div><br></div><div>I earlier explored this in a paper presented at IFL 2014 but (rightfully) rejected from the IFL post-proceedings. (<a href="http://gbaz.github.io/slides/buildable2014.pdf" target="_blank">http://gbaz.github.io/slides/buildable2014.pdf</a>). That paper got part of the way there, but I believe now have a better approach on the question of a Foldable law -- as sketched below.<div><br><div>I think I now (unlike in the paper) can state a succinct law for Foldable that has desired properties: 1) It is not "free" -- it can be violated, and thus stating it adds semantic content. 2) We typically expect it to be true. 3) There are no places where I can see an argument for violating it.</div><div><br></div><div>If it pans out, I intend to pursue this and write it up more formally, but given the current FTP discussion I thought it was worth documenting this earlier rather than later. For simplicity, I will state this property in terms of `toList` although that does not properly capture the infinite cases. Apologies for what may be nonstandard notation.</div><div><br></div><div>Here is the law I think we should discuss requiring:</div><div><br></div><div>* * *</div><div>Given Foldable f, then</div><div>forall (g :: forall a. f a -> Maybe a), (x :: f a). case g x of Just a --> a `elem` toList x</div><div>* * *</div><div><br></div><div>Since we do not require `a` to be of type `Eq`, note that the `elem` function given here is not internal to Haskell, but in the metalogic.</div><div><br></div><div>Furthermore, note that the use of parametricity here lets us make an "end run" around the usual problem of giving laws to Foldable -- rather than providing an interaction with another class, we provide a claim about _all_ functions of a particular type.</div><div><br></div><div>Also note that the functions `g` we intend to quantify over are functions that _can be written_ -- so we can respect the property of data structures to abstract over information. Consider</div><div><br></div><div>data Funny a = Funny {hidden :: a, public :: [a]}</div><div><br></div><div>instance Foldable Funny where</div><div>    foldMap f x = foldMap f (public x)</div><div><br></div><div>Now, if it is truly impossible to ever "see" hidden (i.e. it is not exported, or only exported through a semantics-breaking "Internal" module), then the Foldable instance is legitimate. Otherwise, the Foldable instance is illegitimate by the law given above.</div><div><br></div><div>I would suggest the law given is "morally" the right thing for Foldable -- a Foldable instance for `f` should suggest that it gives us "all the as in any `f a`", and so it is, in some particular restricted sense, initial among functions that extract as.</div><div><br></div><div>I do not suggest we add this law right away. However, I would like to suggest considering it, and I believe it (or a cleaned-up variant) would help us to see Foldable as a more legitimately lawful class that not only provides conveniences but can be used to aid reasoning.</div><div><br></div><div>Relating this to adjointness, as I do in the IFL preprint, remains future work.</div><div><br></div><div>Cheers,</div><div>Gershom</div></div></div></div>
<br></div></div><span>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></span></blockquote></div><br></div>
<br>_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
<br></blockquote></div><br></div>
</div></div></blockquote></div><br></div>