Re: [Haskell-cafe] Restricted type classes
On 9/10/10 12:47 AM, David Menendez wrote: It seems like you could use a similar argument to show that fmap id /= id. Specifically, xs and map id xs are equivalent lists, but they occupy different locations in memory. By replacing xs with map id xs, you can come arbitrarily close to doubling a program's memory requirements. (You can also use pointer comparison to distinguish them, but I assume that doesn't count.) That doesn't really follow. The Haskell values and types do not capture heap transformations, so those don't count for the same reason that pointer equality doesn't count. The fmap id = id law only needs to apply at each use site, not necessarily when doing whole-program analysis. Given any list xs, it is indeed true that the result of (fmap id xs) is equal to the result of (id xs). They even take up the same amount of space after full evaluation. The only difference is that the latter avoids some extra allocation and garbage collection and preserves sharing, none of which is captured by the type system. Indeed, that's why we'd like to know the laws hold, so that we can rewrite occurences of (fmap id) with id; just as we'd like to replace (fmap f . fmap g) by fmap(f.g) since it improves time performance by only performing a single traversal. Time is also not captured by the type system. Technically we could rewrite programs in the other direction and introduce new fmaps, we just have no reason to do so. However, in the example I gave, the actual values (E (f a) a) and (E (f a) (f a)) are not equal even when ignoring time, space, and sharing. They may be *isomorphic* because they have the same observable behavior within the language (assuming no polymorphic seq or heap-size reflection), but they are not *equal*. Your comments about increasing total-program allocation just points out that (fmap id) and id are not *identical*--- which we know already. But even if they cannot be identical, they must be equal if the fmap instance is lawfully a functor. The notions of being identical, equal, isomorphic, and equivalent are all quite different. I was only using the size of their heap representation as evidence for the non-equality of these two terms in spite of their isomorphism. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Wednesday 08 September 2010 11:17:43 pm wren ng thornton wrote: -- | Proof that impure is not p...@e fmap f (impure a) == fmap f (E a a) == E (f a) a /= E (f a) (f a) == impure (f a) I don't believe your proof. The type of E is as follows: E :: a - b - E a The free theorem given by that type is: forall f g x y. map f (E x y) = E (f x) (g y) Setting y = x and g = f, we get: forall f x. map f (E x x) = E (f x) (f x) So your above proof simply assumes that parametricity can be refuted. seq may cause that, but without seq, one would expect parametricity to hold, or at least not be refutable (unless there are other notorious examples I'm failing to remember; existential types aren't one). I think the core of this is your ensuing discussion about equality versus equivalence. You seem to be advancing the notion that equality can only be used to refer to intensional equality. But intensional equality doesn't work very well for existential types, and up to extensional equality, the above should hold. Further, even with intensional equality, one wouldn't expect to be able to prove that E (f a) a /= E (f a) (f a). We should merely not be able to prove that E (f a) a = E (f a) (f a). Going back to free theorems, the theorem for: pure :: a - T a is map f . pure = pure . f so any proposed counter example to that must be a refutation of parametricity for the language in question. I can believe that seq will produce refutations. Any proposal in which existential types do the same parametricity seems to me like it should be rethought. -- Dan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/9/10 1:04 AM, David Menendez wrote: Fascinating. I figured there might be a counter-example involving seq, but this is pretty subtle. In particular, would it be fair to say that in Haskell-without-seq, E (f a) a and E (f a) (f a) are indistinguishable? Yes, I think that without polymorphic seq (or within a strict language) they are observationally equivalent. But, observational equivalence is not the same as equality. And the category theoretic laws really do mean equality. To pick an example: consider the case where 'a' is an enormous data structure and (f a) returns some small value. Even though (E (f a) a) and (E (f a) (f a)) are observationally equivalent within Haskell, they're still observationally distinct from outside of the language because they have very different memory profiles. (We may need to make E strict in the second argument, or NOINLINE impure, in order to guarantee this behavior.) Thus, the equality still fails, though this may go undetected for a long time until someone notices the memory leak. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Thu, Sep 9, 2010 at 11:33 PM, wren ng thornton w...@freegeek.org wrote: On 9/9/10 1:04 AM, David Menendez wrote: Fascinating. I figured there might be a counter-example involving seq, but this is pretty subtle. In particular, would it be fair to say that in Haskell-without-seq, E (f a) a and E (f a) (f a) are indistinguishable? Yes, I think that without polymorphic seq (or within a strict language) they are observationally equivalent. But, observational equivalence is not the same as equality. And the category theoretic laws really do mean equality. To pick an example: consider the case where 'a' is an enormous data structure and (f a) returns some small value. Even though (E (f a) a) and (E (f a) (f a)) are observationally equivalent within Haskell, they're still observationally distinct from outside of the language because they have very different memory profiles. (We may need to make E strict in the second argument, or NOINLINE impure, in order to guarantee this behavior.) Thus, the equality still fails, though this may go undetected for a long time until someone notices the memory leak. It seems like you could use a similar argument to show that fmap id /= id. Specifically, xs and map id xs are equivalent lists, but they occupy different locations in memory. By replacing xs with map id xs, you can come arbitrarily close to doubling a program's memory requirements. (You can also use pointer comparison to distinguish them, but I assume that doesn't count.) What about Set.map? We have forall s. Set.map id s == s, but the actual structure may not be identical. In principle, there's no way to observe the difference, but in practice you can do it by breaking the precondition on foldMap. Does that mean we can't consider Set.Set/Set.map a functor over the subcategory of ordered Haskell types? -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/7/10 12:33 AM, Ivan Lazar Miljenovic wrote: On 7 September 2010 14:24, wren ng thorntonw...@freegeek.org wrote: On 9/7/10 12:04 AM, Ivan Lazar Miljenovic wrote: Not quite sure what you mean by a mis-match Just that they're not the same thing. For example, ZipList supports pure but it has no meaningful instance of singleton since every ZipList is infinite. Huh; didn't know that ZipList did that. OK, so there's a definite mis-match between what we'd want a singleton function to do and what pure appears to do. How can we specify such a hierarchy given that for the majority of containers they will be the same? The way I'd probably do it is to have one class for pointed functors which obeys the pointed law and interacts with Applicative and Monad in the expected way; and then have a separate class for singletons which has laws about how singleton, insert/cons, coinsert/snoc, and union/concat interact. Thus, we'd have two separate functions pure/return/unit and singleton, pulling in the class constraints as appropriate. For most containers it would just happen that they could define pure=singleton, though the class structure doesn't _require_ that. This would allow us to avoid excluding containers like ZipList (pure, but no singleton) and bloomfilters (singleton, but no pure). I think the shape of the classes for singletons, insert, coinsert, and union still needs some work. For instance, the definitions I've given earlier were assuming a (multi)set-like or sequence-like container, but we can also reasonably extend it to include map-like containers. The only trick is that set/seq-like containers have a single type parameter and a single element argument, whereas map-like containers have a pair of type parameters and a key--value pair of elements. So we'd need to do something with MPTCs in order to unify them. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/7/10 7:26 AM, Neil Brown wrote: On 07/09/10 05:24, wren ng thornton wrote: Just that they're not the same thing. For example, ZipList supports pure but it has no meaningful instance of singleton since every ZipList is infinite. I don't believe that every ZipList is infinite (if this should be the case, the constructor shouldn't be exposed!), just that ZipLists created by pure are infinite Just so. I misremembered the data constructor as not being exported. So ZipList does have a meaningful definition of singleton (singleton x = ZipList [x]; Though we still have singleton /= pure, which is all I was arguing. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9 September 2010 12:10, wren ng thornton w...@freegeek.org wrote: I think the shape of the classes for singletons, insert, coinsert, and union still needs some work. For instance, the definitions I've given earlier were assuming a (multi)set-like or sequence-like container, but we can also reasonably extend it to include map-like containers. The only trick is that set/seq-like containers have a single type parameter and a single element argument, whereas map-like containers have a pair of type parameters and a key--value pair of elements. So we'd need to do something with MPTCs in order to unify them. Yes, I'm not sure if Map-like types of kind * - * - * should have a value of type (a,b) or then have BiFunctor, BiBuildable, etc. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/7/10 4:21 AM, Daniel Fischer wrote: On Tuesday 07 September 2010 05:22:55, David Menendez wrote: In fact, I think *every* appropriately-typed function satisfies that law. Does anyone know of a counter-example? -- | Multiply the *Hask* category by its number of objects. data E a where E :: a - b - E a -- | Maintain all the morphisms of *Hask* in each *E*-copy of -- it, but keep the tag for which *E*-copy we were in. instance Functor E where fmap f (E a b) = E (f a) b -- | Proof that f...@e maintains identities fmap id _|_ == _|_ == id _|_ fmap id (E a b) == E (id a) b == E a b == id (E a b) -- | Proof that f...@e maintains compositions fmap f (fmap g _|_) == fmap f _|_ == _|_ == fmap (f . g) _|_ fmap f (fmap g (E a b)) == fmap f (E (g a) b) == E (f (g a)) b == E ((f.g) a) b == fmap (f . g) (E a b) -- | The object part of a functor to enter *E* along the diagonal. impure :: a - E a impure a = E a a -- | Proof that impure is not p...@e fmap f (impure a) == fmap f (E a a) == E (f a) a /= E (f a) (f a) == impure (f a) And yet, impure has the correct type. Of course, it is possible to define functions of type (a - E a) which do satisfy the law. Namely, choose any function where the second argument to E does not depend on the parameter. But the problem is that there are a whole bunch of them! And none of them is intrinsically any more natural or correct than any other. Unfortunately, impure is the most natural function in that type, but it breaks the laws. Functors like this happen to be helpful too, not just as oddities. They're functors for tracking the evolution of a value through a computation (e.g., tracking the initial value passed to a function). In this example, the existential tag is restricted by observational equivalence to only allow us to distinguish bottom from non-bottom initial values. But we can add context constraints on the data constructor in order to extract more information; at the cost of restricting impure to only working for types in those classes. class Functor f = Pointed f where point :: a - f a -- satisfying fmap f . point = point . f notQuitePure :: Pointed f = a - f a notQuitePure _ = point undefined fmap (const True) . notQuitePure = point . const True But I don't see how to violate that law without introducing undefined on the RHS. You can also break the law by defining a strictness functor[*]: pure=id; fmap=($!) ---or any newtype equivalent. It breaks the pointed law for the same kind of reason, namely by strictifying functions that ignore their parameters but doing so in different places. [*] Unfortunately, that's not actually a functor, since it does not preserve bottom-eating compositions. I.e., ($!)(const 42 . const undefined) /= ($!)(const 42) . ($!)(const undefined) We only get a monotonic relationship, not an equality. I tried playing around with it a bit, but I'm pretty sure there's no way to define any (non-trivial, full,... i.e., interesting) functor from *Hask* into *StrictHask* from within Haskell. The only functor that seems to work is the CBV functor which reinterprets Haskell terms via call-by-value semantics, which I don't think we can define from within Haskell. Of course, defining an embedding from *StrictHask* to *Hask* is trivial. These two points together seem like a compelling argument for laziness-by-default in language design. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Wed, Sep 8, 2010 at 11:17 PM, wren ng thornton w...@freegeek.org wrote: On 9/7/10 4:21 AM, Daniel Fischer wrote: On Tuesday 07 September 2010 05:22:55, David Menendez wrote: In fact, I think *every* appropriately-typed function satisfies that law. Does anyone know of a counter-example? -- | Multiply the *Hask* category by its number of objects. data E a where E :: a - b - E a -- | Maintain all the morphisms of *Hask* in each *E*-copy of -- it, but keep the tag for which *E*-copy we were in. instance Functor E where fmap f (E a b) = E (f a) b snip -- | The object part of a functor to enter *E* along the diagonal. impure :: a - E a impure a = E a a -- | Proof that impure is not p...@e fmap f (impure a) == fmap f (E a a) == E (f a) a /= E (f a) (f a) == impure (f a) And yet, impure has the correct type. Fascinating. I figured there might be a counter-example involving seq, but this is pretty subtle. In particular, would it be fair to say that in Haskell-without-seq, E (f a) a and E (f a) (f a) are indistinguishable? Functors like this happen to be helpful too, not just as oddities. They're functors for tracking the evolution of a value through a computation (e.g., tracking the initial value passed to a function). In this example, the existential tag is restricted by observational equivalence to only allow us to distinguish bottom from non-bottom initial values. But we can add context constraints on the data constructor in order to extract more information; at the cost of restricting impure to only working for types in those classes. ...at which point, it no longer has the same type as pure. But your point is taken. -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Tuesday 07 September 2010 05:22:55, David Menendez wrote: On Mon, Sep 6, 2010 at 10:22 PM, wren ng thornton w...@freegeek.org wrote: On 9/6/10 1:33 PM, David Menendez wrote: For that matter, can you even describe what pure is intended to do without reference to* or join? As already stated: fmap f . pure = pure . f That's pretty general. For lists, the functions having that property include const [], \x - [x,x], and repeat. In fact, I think *every* appropriately-typed function satisfies that law. Does anyone know of a counter-example? class Functor f = Pointed f where point :: a - f a -- satisfying fmap f . point = point . f notQuitePure :: Pointed f = a - f a notQuitePure _ = point undefined fmap (const True) . notQuitePure = point . const True But I don't see how to violate that law without introducing undefined on the RHS. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
2010/9/7 Ivan Lazar Miljenovic ivan.miljeno...@gmail.com 2010/9/7 Gábor Lehel illiss...@gmail.com: *That said*, I actually have nothing at all against splitting the 'a - f a' method out into a separate class if you think it's useful, whether you call it Pointed or something else. (And `class (Pointed f, Functor f) = PointedFunctor f` is sort of cute.) It might be cute, but until we get class aliases [1] this results in yet another class to make your data type an instance of, and what's more it's one that doesnt' even give you anything. I think it makes much more sense to have Functor, Pointed and (Functor f, Pointed f) = Applicative f rather than a useless intermediary class. If, however, we could get class aliases _for free_ (i.e. something like class alias PointedFunctor f = (Functor f, Pointed f) for which all instances of Functor and Pointed are automatically instanced of PointedFunctor), then I can see that as being something nice to have. I agree completely. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
From: Stephen Tetley stephen.tet...@gmail.com On 6 September 2010 20:18, John Lato jwl...@gmail.com wrote: Can you give an example of a Functor that doesn't have pure? I think it's Pointed Functors which are useful; not Functor by itself. Strictly speaking is Pair one? The current implementation tacks on monoid. Interesting example. I tend not to like implementations which rely on bottoms, so I think I'd agree. In a similar spirit, I would propose Data.Vector.Unboxed.Vector as a Pointed Functor (modulo element restrictions) which is not Applicative, since the necessary element restrictions mean * can't be defined. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 07/09/10 05:24, wren ng thornton wrote: that other class would (most likely) be a subclass of pointed functors. In any case, it does mean there's something of a mismatch between singleton vs return/pure/point/unit. Not quite sure what you mean by a mis-match Of course, I'd expect singleton to obey the pointed law as well, so Just that they're not the same thing. For example, ZipList supports pure but it has no meaningful instance of singleton since every ZipList is infinite. I don't believe that every ZipList is infinite (if this should be the case, the constructor shouldn't be exposed!), just that ZipLists created by pure are infinite -- that's the obvious definition to meet the Applicative laws. You can quite happily use: (+) $ ZipList [1,2,3] * ZipList [4,5] == ZipList [5,7] So ZipList does have a meaningful definition of singleton (singleton x = ZipList [x]; I'm sure there are other pointed functors that don't have a good definition for singleton), and a meaningful definition of pure, but they're not the same definition. Thanks, Neil. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/5/10 10:19 AM, Ivan Lazar Miljenovic wrote:
Hmmm is there any reason for Functor to be a superclass of
Pointed? I understand Functor and Pointed being superclasses of
Applicative (which in turn is a superclass of Monad), but can't see
any relation between Pointed and Functor...
Because there's a law for pointed functors which ensures that return
(point, unit, pure,...) only creates trivial structure:
forall {A B : Type} (f : A - B) (a : A)
, fmap f (return a) = return (f a)
If we require this law, then the five laws for Applicative can be
reduced to only three; which is nice. (Though, if the extra two laws are
satisfied, then we can prove this one.)
We don't actually enforce that instances obey their class' laws anywhere
else, so it's not like we'd need somewhere to store this proof. But the
law is there nevertheless. What use would it be to have a return
function that doesn't satisfy any laws (i.e., without fmap)?
--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 6 September 2010 16:15, wren ng thornton w...@freegeek.org wrote:
On 9/5/10 10:19 AM, Ivan Lazar Miljenovic wrote:
Hmmm is there any reason for Functor to be a superclass of
Pointed? I understand Functor and Pointed being superclasses of
Applicative (which in turn is a superclass of Monad), but can't see
any relation between Pointed and Functor...
Because there's a law for pointed functors which ensures that return (point,
unit, pure,...) only creates trivial structure:
forall {A B : Type} (f : A - B) (a : A)
, fmap f (return a) = return (f a)
If we require this law, then the five laws for Applicative can be reduced to
only three; which is nice. (Though, if the extra two laws are satisfied,
then we can prove this one.)
We don't actually enforce that instances obey their class' laws anywhere
else, so it's not like we'd need somewhere to store this proof. But the law
is there nevertheless. What use would it be to have a return function that
doesn't satisfy any laws (i.e., without fmap)?
Well, if we consider what this does, pure is equivalent to singleton
for container types. The actual definition of pure (or any other
aspect of Pointed) doesn't require Functor; however there are
properties for types that are instances of Functor and Pointed.
So, from a proof/testing POV having Functor as a superclass is nice;
from an implementation POV it doesn't seem to be needed.
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Sun, Sep 5, 2010 at 7:18 PM, David Menendez d...@zednenem.com wrote: On Sun, Sep 5, 2010 at 8:40 AM, John Lato jwl...@gmail.com wrote: On Sat, Sep 4, 2010 at 12:34 PM, David Menendez d...@zednenem.com wrote: On Fri, Sep 3, 2010 at 8:23 AM, John Lato jwl...@gmail.com wrote: +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). What's the argument for Pointed? Are there many types which are instances of Pointed but not Applicative? Are there many algorithms which require Pointed but not Applicative? Having Pointed is categorically the right thing to do, which is why I argue for its inclusion. Why is it categorically the right thing to do? Because it's the proper abstraction underlying Applicative and Monad, as far as I understand category theory. When Conor McBride was promoting the use of Applicative (then called Idiom), he provided several instances and algorithms showing that it was a useful generalization of Monad, and it still took several years and a few papers[1] before Applicative found its way into the standard library. In other words, we didn't add Applicative and then discover Traversable later. Traversable was a big part of the argument for why Applicative is useful. I take this in favor of my point. Applicative wasn't considered useful, so it wasn't included. Then Conor McBride shows that it is useful, but at that point it was too late and now we're stuck with pure, return, ap, liftA2, liftM2, etc. [1] Idioms: applicative programming with effects http://www.cs.nott.ac.uk/~ctm/Idiom.pdf Also, I think it would be prudent to avoid a situation with the possibility of turning into a rehash of the Functor/Applicative/Monad mess. Granted, but let's not rush blindly in the opposite direction. Are there any good reasons for not including it? Just because we don't have a use now doesn't mean it might not be useful in the future. This is an argument for putting every member of the container API into its own independent class. Why make things more complicated for little or no benefit? Not every member, but I would argue that type classes for containers should be much more fine-grained than anything I have seen proposed so far. I'm thinking of the collections provided by the .Net framework, i.e. a base ICollection interface, then IEnumerable, IList, and ISet on top of them. If an algorithm needs a list interface (integer-indexed, etc.), it can specify IList in the context, whereas if it only needs e.g. to check the length, or that a container is non-null, it can just specify ICollection and work with more data structures. I would be in favor of breaking it down further, and then the ListClass, SetClass, etc. would likely be classes with no methods, just a particular combination of superclasses. Edison is a good model too, although again I would go further. One category of containers that is currently impossible to express (with container-classes or Edison) is non-null data, e.g. SafeList. Adding support for these would be nice, and it would be easier with finer-grained dependencies. As an example, a List interface could work for both regular lists and SafeList's, but only if it didn't require Monoid (or similar) as a superclass constraint. That's hard to do with the current structure, but if you're just combining several type classes it's easy. At a minimum, I think that having extra classes for the specifics of e.g. Map or Queue interfaces is required for maximum utility. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
Message: 20 Date: Sat, 04 Sep 2010 03:40:49 -0400 From: wren ng thornton w...@freegeek.org Subject: Re: [Haskell-cafe] Restricted type classes To: Haskell Cafe haskell-cafe@haskell.org Message-ID: 4c81f801@freegeek.org Content-Type: text/plain; charset=UTF-8; format=flowed On 9/3/10 12:16 AM, Ivan Lazar Miljenovic wrote: 2) How far should I go? Should I restrict myself to the data-oriented classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should: I'd say you should do as much as seems reasonable. I tend to take things as far as I can, but that'd end up doing a lot of the same work as category-extras. For a general collections library, I think it'd make sense to try to keep things simpler than that if possible. The simpler it is, the better the uptake will be, so long as it's still complex enough to capture what it needs to. I'd say you should include: Functor, Foldable, Traversable, Pointed, Applicative, Monad, and Monoid (both additive and multiplicative in separate classes, as in the monoids package). Those eight make for a really comprehensive toolkit that does most of the things people frequently need. Of course, not every collection will have instances for all of them. Although I agree these do most things that people need, it's very rare that I need a data structure that guarantees *only* these features. Most often I need a map, a queue, etc. because I need either lookup by key, queue properties, etc. I think it's necessary to include classes like Indexable and Queue. Indexable may need to be split into two, one for ordered-Int indexes (i.e. lists) and one for Maps. Just a few days ago I wanted to change the priority queue implementation in some code. This was painful because the different available implementations all have varying APIs, so I couldn't just change the imports. I've wanted to do this in other contexts as well (e.g. maps and tries). The perhaps more important use is for coding algorithms that depend upon map properties, queue properties, etc., but leaving the actual implementation polymorphic so it can be chosen by a higher level. If the purpose of this project is to present a common interface for containers, then I think you should start by seeing what are the most common containers (I would guess lists, sets, maps, and queues) with a goal of providing their specific functionality through classes. Then all the common stuff can be stripped out and provided by superclasses. Of course we already know a great deal of the common operations, e.g. Traversable and Foldable, and we make use of those abstractions. It's this last step of a common map interface, queue interface, etc. that's missing. If you're just going to provide stuff we already have, I don't really see the point. 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base? If you're defining a new hierarchy, I'd say you should do it correctly, i.e. classFunctor where fmap class Functor = Pointed where unit -- or point class Pointed = Applicative where (*) ; (*) ; (*) class Applicative = Monad where (=) ; join Shouldn't it be: class Functor where fmap class Pointed where point class (Functor f, Pointed f) = PointedFunctor f where class PointedFunctor f = Applicative f where (*); --etc. class Applicative f = Monad f where (=); --etc. even I might omit PointedFunctor, though, because it doesn't add anything. If it is omitted, that just means your Applicative contexts are slightly longer. But please don't make Pointed depend on Functor - we've already seen that it won't work for Bloom filters. Cheers, John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Mon, Sep 6, 2010 at 5:11 PM, John Lato jwl...@gmail.com wrote: Message: 20 Date: Sat, 04 Sep 2010 03:40:49 -0400 From: wren ng thornton w...@freegeek.org Subject: Re: [Haskell-cafe] Restricted type classes To: Haskell Cafe haskell-cafe@haskell.org Message-ID: 4c81f801@freegeek.org Content-Type: text/plain; charset=UTF-8; format=flowed On 9/3/10 12:16 AM, Ivan Lazar Miljenovic wrote: 2) How far should I go? Should I restrict myself to the data-oriented classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should: I'd say you should do as much as seems reasonable. I tend to take things as far as I can, but that'd end up doing a lot of the same work as category-extras. For a general collections library, I think it'd make sense to try to keep things simpler than that if possible. The simpler it is, the better the uptake will be, so long as it's still complex enough to capture what it needs to. I'd say you should include: Functor, Foldable, Traversable, Pointed, Applicative, Monad, and Monoid (both additive and multiplicative in separate classes, as in the monoids package). Those eight make for a really comprehensive toolkit that does most of the things people frequently need. Of course, not every collection will have instances for all of them. Although I agree these do most things that people need, it's very rare that I need a data structure that guarantees *only* these features. Most often I need a map, a queue, etc. because I need either lookup by key, queue properties, etc. I think it's necessary to include classes like Indexable and Queue. Indexable may need to be split into two, one for ordered-Int indexes (i.e. lists) and one for Maps. Just a few days ago I wanted to change the priority queue implementation in some code. This was painful because the different available implementations all have varying APIs, so I couldn't just change the imports. I've wanted to do this in other contexts as well (e.g. maps and tries). The perhaps more important use is for coding algorithms that depend upon map properties, queue properties, etc., but leaving the actual implementation polymorphic so it can be chosen by a higher level. If the purpose of this project is to present a common interface for containers, then I think you should start by seeing what are the most common containers (I would guess lists, sets, maps, and queues) with a goal of providing their specific functionality through classes. Then all the common stuff can be stripped out and provided by superclasses. Of course we already know a great deal of the common operations, e.g. Traversable and Foldable, and we make use of those abstractions. It's this last step of a common map interface, queue interface, etc. that's missing. If you're just going to provide stuff we already have, I don't really see the point. 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base? If you're defining a new hierarchy, I'd say you should do it correctly, i.e. class Functor where fmap class Functor = Pointed where unit -- or point class Pointed = Applicative where (*) ; (*) ; (*) class Applicative = Monad where (=) ; join Shouldn't it be: class Functor where fmap class Pointed where point class (Functor f, Pointed f) = PointedFunctor f where class PointedFunctor f = Applicative f where (*); --etc. class Applicative f = Monad f where (=); --etc. even I might omit PointedFunctor, though, because it doesn't add anything. If it is omitted, that just means your Applicative contexts are slightly longer. But please don't make Pointed depend on Functor - we've already seen that it won't work for Bloom filters. Cheers, John I think most people have been using Pointed merely as shorthand for Pointed Functor -- in the same way that Applicative isn't called ApplicativeFunctor, even though that's what it is. So if it doesn't work for Bloom filters, the reason is that Bloom filters aren't pointed functors. *That said*, I actually have nothing at all against splitting the 'a - f a' method out into a separate class if you think it's useful, whether you call it Pointed or something else. (And `class (Pointed f, Functor f) = PointedFunctor f` is sort of cute.) I'm just trying to clarify where people are probably coming from -- those people can hopefully correct me if I'm wrong about this. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Mon, Sep 6, 2010 at 7:51 AM, John Lato jwl...@gmail.com wrote: On Sun, Sep 5, 2010 at 7:18 PM, David Menendez d...@zednenem.com wrote: On Sun, Sep 5, 2010 at 8:40 AM, John Lato jwl...@gmail.com wrote: On Sat, Sep 4, 2010 at 12:34 PM, David Menendez d...@zednenem.com wrote: On Fri, Sep 3, 2010 at 8:23 AM, John Lato jwl...@gmail.com wrote: +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). What's the argument for Pointed? Are there many types which are instances of Pointed but not Applicative? Are there many algorithms which require Pointed but not Applicative? Having Pointed is categorically the right thing to do, which is why I argue for its inclusion. Why is it categorically the right thing to do? Because it's the proper abstraction underlying Applicative and Monad, as far as I understand category theory. What makes it the proper abstraction? Applicative Functors have three parts: the functor, pure, and *, along with some equations they need to satisfy. We know Functor by itself is useful, but what makes Functor+pure better than Functor+* or pure+* or any other subset? The fact that it has a name doesn't make it useful for programming; category theory has names for all sorts of things that don't come up very often. For that matter, can you even describe what pure is intended to do without reference to * or join? You can say that it's a natural transformation from Id to f, but so is \x - [x,x]. You can say it contains one copy of the argument, but that doesn't work for the Const functor or the infinite stream functor, among others. I notice no one has given any algorithms that operate on arbitrary pointed functors. When Conor McBride was promoting the use of Applicative (then called Idiom), he provided several instances and algorithms showing that it was a useful generalization of Monad, and it still took several years and a few papers[1] before Applicative found its way into the standard library. In other words, we didn't add Applicative and then discover Traversable later. Traversable was a big part of the argument for why Applicative is useful. I take this in favor of my point. Applicative wasn't considered useful, so it wasn't included. Then Conor McBride shows that it is useful, but at that point it was too late and now we're stuck with pure, return, ap, liftA2, liftM2, etc. I think that has more to do with Haskell 98 compatibility. We broke Category out of Arrow not too long ago. Furthermore, you didn't address my point: Applicative is *useful*. We have algorithms that are parameterized by arbitrary applicative functors. We have multiple examples of useful non-monad applicative functors. What are pointed functors good for? -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Mon, Sep 6, 2010 at 12:33 PM, David Menendez d...@zednenem.com wrote: On Mon, Sep 6, 2010 at 7:51 AM, John Lato jwl...@gmail.com wrote: On Sun, Sep 5, 2010 at 7:18 PM, David Menendez d...@zednenem.com wrote: On Sun, Sep 5, 2010 at 8:40 AM, John Lato jwl...@gmail.com wrote: On Sat, Sep 4, 2010 at 12:34 PM, David Menendez d...@zednenem.com wrote: On Fri, Sep 3, 2010 at 8:23 AM, John Lato jwl...@gmail.com wrote: +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). What's the argument for Pointed? Are there many types which are instances of Pointed but not Applicative? Are there many algorithms which require Pointed but not Applicative? Having Pointed is categorically the right thing to do, which is why I argue for its inclusion. Why is it categorically the right thing to do? Because it's the proper abstraction underlying Applicative and Monad, as far as I understand category theory. What makes it the proper abstraction? Applicative Functors have three parts: the functor, pure, and *, along with some equations they need to satisfy. We know Functor by itself is useful, but what makes Functor+pure better than Functor+* or pure+* or any other subset? The fact that it has a name doesn't make it useful for programming; category theory has names for all sorts of things that don't come up very often. I'm arguing in favor of pure by itself, not just pure+Functor. Ivan's already given one example of a structure that only meets the point criteria: a Bloom filter. Regarding Applicative Functors somewhat off-topic, you can define fmap strictly in terms of pure+*. It's interesting that they're somewhat parallel to non-applicative Functors in that the Functor instance isn't necessary, it's the pointed and * that are. Once you have those you get Functor for free. But a non-applicative functor doesn't necessarily have either. Can you give an example of a Functor that doesn't have pure? I think it's Pointed Functors which are useful; not Functor by itself. For that matter, can you even describe what pure is intended to do without reference to * or join? You can say that it's a natural transformation from Id to f, but so is \x - [x,x]. You can say it contains one copy of the argument, but that doesn't work for the Const functor or the infinite stream functor, among others. Broadly, I agree that pure should behave in a manner consistent with the Applicative or Monad instance if they exist. In the context of a collections interface though, pure should be identical to singleton, which should guide the choice of Applicative or Monad if there is one. I notice no one has given any algorithms that operate on arbitrary pointed functors. Ivan gave one useful data structure for which point by itself has meaning but Applicative doesn't. Also Point would be a useful base class for a non-empty data API (for which Monoid is unusable). When Conor McBride was promoting the use of Applicative (then called Idiom), he provided several instances and algorithms showing that it was a useful generalization of Monad, and it still took several years and a few papers[1] before Applicative found its way into the standard library. In other words, we didn't add Applicative and then discover Traversable later. Traversable was a big part of the argument for why Applicative is useful. I take this in favor of my point. Applicative wasn't considered useful, so it wasn't included. Then Conor McBride shows that it is useful, but at that point it was too late and now we're stuck with pure, return, ap, liftA2, liftM2, etc. I think that has more to do with Haskell 98 compatibility. We broke Category out of Arrow not too long ago. What was Category doing in Arrow to begin with? Wouldn't it have been easier if they had been separate from the start? Why do you think we should do the same thing now? Furthermore, you didn't address my point: Applicative is *useful*. We have algorithms that are parameterized by arbitrary applicative functors. We have multiple examples of useful non-monad applicative functors. What are pointed functors good for? Again, I don't care so much for pointed functors as for Pointed, and I've given two examples of where it would be useful. What's wrong with breaking Pointed off? All it requires is one instance with one method which you would have written anyway. That's one extra LOC, and if you base Monad and Applicative off of it there's zero change. Also a clear separation of concerns is better than conflating meanings together. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 6 September 2010 20:18, John Lato jwl...@gmail.com wrote: Can you give an example of a Functor that doesn't have pure? I think it's Pointed Functors which are useful; not Functor by itself. Strictly speaking is Pair one? The current implementation tacks on monoid. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/6/10 2:35 AM, Ivan Lazar Miljenovic wrote: Well, if we consider what this does, pure is equivalent to singleton for container types. The actual definition of pure (or any other aspect of Pointed) doesn't require Functor; however there are properties for types that are instances of Functor and Pointed. Right, that's what I was meaning to highlight. If we were doing this in Coq, for example, then not having Functor as a superclass of Pointed would mean that we'd need a third class PointedFunctor which has both as superclasses. In Haskell, since we don't have proofs, PointedFunctor wouldn't have any methods and would therefore just be unnecessary complication. Though this raises the question of which one makes more sense to keep around: Pointed (with no superclass), or PointedFunctor. So, from a proof/testing POV having Functor as a superclass is nice; from an implementation POV it doesn't seem to be needed. Though, again, I wonder what the use case would be. Your example of singleton collections doesn't seem quite right. I'd expect the singleton functions to obey various spatial laws (i.e., module-like or vector space-like laws). For example, union (singleton a) x = insert a x This isn't exactly like Applicative because 'a' is an element instead of a function. And it's not quite like Alternative either, since it only requires union to be a semigroup instead of a monoid. However, I can see some pointed functors that don't have this law, either because insert or union don't make sense or because the obvious implementations don't fit the pattern. Consider, for instance, the ZipList applicative functor which has pure=repeat. It satisfies the pointed law just fine, but it's not clear what insert or union should mean (interleaving, perhaps? It still wouldn't be an Alternative though). Perhaps this just means that union/insert should be part of some other class. Of course, I'd expect singleton to obey the pointed law as well, so that other class would (most likely) be a subclass of pointed functors. In any case, it does mean there's something of a mismatch between singleton vs return/pure/point/unit. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/6/10 1:33 PM, David Menendez wrote: For that matter, can you even describe what pure is intended to do without reference to* or join? As already stated: fmap f . pure = pure . f -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Mon, Sep 6, 2010 at 10:22 PM, wren ng thornton w...@freegeek.org wrote: On 9/6/10 1:33 PM, David Menendez wrote: For that matter, can you even describe what pure is intended to do without reference to* or join? As already stated: fmap f . pure = pure . f That's pretty general. For lists, the functions having that property include const [], \x - [x,x], and repeat. In fact, I think *every* appropriately-typed function satisfies that law. Does anyone know of a counter-example? -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
2010/9/7 Gábor Lehel illiss...@gmail.com: *That said*, I actually have nothing at all against splitting the 'a - f a' method out into a separate class if you think it's useful, whether you call it Pointed or something else. (And `class (Pointed f, Functor f) = PointedFunctor f` is sort of cute.) It might be cute, but until we get class aliases [1] this results in yet another class to make your data type an instance of, and what's more it's one that doesnt' even give you anything. I think it makes much more sense to have Functor, Pointed and (Functor f, Pointed f) = Applicative f rather than a useless intermediary class. If, however, we could get class aliases _for free_ (i.e. something like class alias PointedFunctor f = (Functor f, Pointed f) for which all instances of Functor and Pointed are automatically instanced of PointedFunctor), then I can see that as being something nice to have. [1]: http://www.haskell.org/haskellwiki/Context_alias -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 7 September 2010 12:18, wren ng thornton w...@freegeek.org wrote: On 9/6/10 2:35 AM, Ivan Lazar Miljenovic wrote: Well, if we consider what this does, pure is equivalent to singleton for container types. The actual definition of pure (or any other aspect of Pointed) doesn't require Functor; however there are properties for types that are instances of Functor and Pointed. Right, that's what I was meaning to highlight. If we were doing this in Coq, for example, then not having Functor as a superclass of Pointed would mean that we'd need a third class PointedFunctor which has both as superclasses. In Haskell, since we don't have proofs, PointedFunctor wouldn't have any methods and would therefore just be unnecessary complication. Though this raises the question of which one makes more sense to keep around: Pointed (with no superclass), or PointedFunctor. So, from a proof/testing POV having Functor as a superclass is nice; from an implementation POV it doesn't seem to be needed. Though, again, I wonder what the use case would be. Your example of singleton collections doesn't seem quite right. I'd expect the singleton functions to obey various spatial laws (i.e., module-like or vector space-like laws). For example, union (singleton a) x = insert a x This isn't exactly like Applicative because 'a' is an element instead of a function. And it's not quite like Alternative either, since it only requires union to be a semigroup instead of a monoid. Well, I think the ability to create singleton values is a nice function to abstract away into a type class. Whether we can prove something or not is, however, a different story. Perhaps this just means that union/insert should be part of some other class. That is part of the plan (I'm tentatively calling the class with the insert method Buildable or Extendable); this means that if a type is an instance of Monoid (for mempty), Buildable/whatever (for insert) and Foldable (for foldr), then we can possibly define a build-fusion rule (note: I dont' think this will work on Sets, etc. unless we have some way of guarantee-ing that the folding function is strictly monotonic). Note also that we can then define that singleton = flip insert mempty (but in general this might not be ideal; Sets, for example, don't have the Ord constraint for singleton). Of course, I'd expect singleton to obey the pointed law as well, so that other class would (most likely) be a subclass of pointed functors. In any case, it does mean there's something of a mismatch between singleton vs return/pure/point/unit. Not quite sure what you mean by a mis-match -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/7/10 12:04 AM, Ivan Lazar Miljenovic wrote: Perhaps this just means that union/insert should be part of some other class. That is part of the plan (I'm tentatively calling the class with the insert method Buildable or Extendable); this means that if a type is an instance of Monoid (for mempty), Buildable/whatever (for insert) and Foldable (for foldr), then we can possibly define a build-fusion rule You don't need mempty for fusion. All you need is a basis case, and singleton can give that. Actually, you don't even need a base case, you just need an inductive step and a coinductive step. So, insert from Whatever and msplit from MonadLogic, for example. The trick is just that the insertion and the extraction must be trivial in the sense that you needn't store additional structure along the way; e.g., when folding a list there's no structure above the head, i.e. outside of the top-level constructor and any recursive tails. For Data.Set that isn't the case, since there are constructors along the path from the root to the current element (even if all structure before the head has been GCed). (note: I dont' think this will work on Sets, etc. unless we have some way of guarantee-ing that the folding function is strictly monotonic). You should only have to require that mapping functions are injective, and that folding functions are associative and commutative. Alternatively, that the folding function is associative, commutative, and idempotent. There's no need for the target domain to be ordered nor for the folding function to be monotonic in that order... Of course, I'd expect singleton to obey the pointed law as well, so that other class would (most likely) be a subclass of pointed functors. In any case, it does mean there's something of a mismatch between singleton vs return/pure/point/unit. Not quite sure what you mean by a mis-match Just that they're not the same thing. For example, ZipList supports pure but it has no meaningful instance of singleton since every ZipList is infinite. -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 7 September 2010 14:24, wren ng thornton w...@freegeek.org wrote: On 9/7/10 12:04 AM, Ivan Lazar Miljenovic wrote: Perhaps this just means that union/insert should be part of some other class. That is part of the plan (I'm tentatively calling the class with the insert method Buildable or Extendable); this means that if a type is an instance of Monoid (for mempty), Buildable/whatever (for insert) and Foldable (for foldr), then we can possibly define a build-fusion rule You don't need mempty for fusion. All you need is a basis case, and singleton can give that. I'm talking about the build-foldr fusion rule from A Shortcut to Deforestation, which (in my admittedly brief search) seems to be the easiest to adapt to a wide range of containers (assuming there is some linearity involved). Yes, for specific types without mempty, we can possibly define specific fusion rules; but I'd like to be able to say if we're doing a foldr over a build from any sequential type to another sequential type, then we can just fuse the intermediary type. (note: I dont' think this will work on Sets, etc. unless we have some way of guarantee-ing that the folding function is strictly monotonic). You should only have to require that mapping functions are injective, and that folding functions are associative and commutative. Alternatively, that the folding function is associative, commutative, and idempotent. There's no need for the target domain to be ordered nor for the folding function to be monotonic in that order... Well, even given those constraints: it's a bit hard to say Associative (a - b), Communtative (a - b), Idempotent (a - b) = ... for a specific function... Of course, I'd expect singleton to obey the pointed law as well, so that other class would (most likely) be a subclass of pointed functors. In any case, it does mean there's something of a mismatch between singleton vs return/pure/point/unit. Not quite sure what you mean by a mis-match Just that they're not the same thing. For example, ZipList supports pure but it has no meaningful instance of singleton since every ZipList is infinite. Huh; didn't know that ZipList did that. OK, so there's a definite mis-match between what we'd want a singleton function to do and what pure appears to do. How can we specify such a hierarchy given that for the majority of containers they will be the same? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Fri, Sep 3, 2010 at 12:01 PM, C. McCann c...@uptoisomorphism.net wrote: On Fri, Sep 3, 2010 at 11:47 AM, John Lato jwl...@gmail.com wrote: On Fri, Sep 3, 2010 at 1:29 PM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 3 September 2010 22:23, John Lato jwl...@gmail.com wrote: Do you have a kind * implementation of Foldable? I'd be interested in seeing it, because I was unable to create a usable implementation (based upon the RMonad scheme) on my last attempt. I was going to make it a subset of Foldable: fold, foldr, foldl, etc. So you don't have a working implementation yet? I ended up thinking this is impossible, although I don't remember the reasoning that led me to that conclusion (and I could very well be wrong). I would suggest that you check this before going too far along the restricted-monad path. This sounds odd to me. An RMonad-style version of Foldable is straightforward: class RFoldable t where rfold :: Control.RMonad.Suitable t a = (a - b - b) - b - t a - b instance RFoldable Data.Set.Set where rfold = Data.Set.fold A similar class for types of kind * is also straightforward: class Reduce t where type Elem t reduce :: (Elem t - r - r) - r - t - r instance Reduce Data.ByteString.ByteString where type Elem Data.ByteString.ByteString = Word8 reduce = Data.ByteString.foldr Both seem to work as I'd expect. Am I missing something? Foldable is pretty trivial--perhaps it was Traversable that you found problematic? This certainly does seem to work just fine in ghc-6.12, but not 6.10.4. I wonder if that was the source of my problems last time. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Sat, Sep 4, 2010 at 12:34 PM, David Menendez d...@zednenem.com wrote: On Fri, Sep 3, 2010 at 8:23 AM, John Lato jwl...@gmail.com wrote: +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). What's the argument for Pointed? Are there many types which are instances of Pointed but not Applicative? Are there many algorithms which require Pointed but not Applicative? Having Pointed is categorically the right thing to do, which is why I argue for its inclusion. Also, I think it would be prudent to avoid a situation with the possibility of turning into a rehash of the Functor/Applicative/Monad mess. Are there any good reasons for not including it? Just because we don't have a use now doesn't mean it might not be useful in the future. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 5 September 2010 22:40, John Lato jwl...@gmail.com wrote: Having Pointed is categorically the right thing to do, which is why I argue for its inclusion. Also, I think it would be prudent to avoid a situation with the possibility of turning into a rehash of the Functor/Applicative/Monad mess. Are there any good reasons for not including it? Just because we don't have a use now doesn't mean it might not be useful in the future. Only reason I can think of: it's a pain to make useless class instances when there is no reason why they can't be combined (since you never make an instance of one without an instance of the other). I _can_ think of a data type that could conceivably be an instance of Pointed but not Applicative: a BloomFilter (though there's not really any point in having a BloomFilter with only one value that I can see, but maybe someone can since there's the singletonB function). -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Sun, Sep 5, 2010 at 7:47 AM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 5 September 2010 22:40, John Lato jwl...@gmail.com wrote: Having Pointed is categorically the right thing to do, which is why I argue for its inclusion. Also, I think it would be prudent to avoid a situation with the possibility of turning into a rehash of the Functor/Applicative/Monad mess. Are there any good reasons for not including it? Just because we don't have a use now doesn't mean it might not be useful in the future. Only reason I can think of: it's a pain to make useless class instances when there is no reason why they can't be combined (since you never make an instance of one without an instance of the other). It's a one-time cost, though, so to me at least it's not a big deal. I _can_ think of a data type that could conceivably be an instance of Pointed but not Applicative: a BloomFilter (though there's not really any point in having a BloomFilter with only one value that I can see, but maybe someone can since there's the singletonB function). Thanks for mentioning this. Bloom filters certainly are an interesting structure, in many ways. John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
Just because we don't have a use now doesn't mean it might not be useful in the future. I am suspicious about complicating a design for potential future benefits. However, difference lists provide an example of a type that support Pointed more naturally than Applicative: the dlist package [1] provides Applicative and Monad instances but only by converting to normal lists in between. Note that even fmap cannot be defined without converting difference lists to normal lists in between. The natural interface to difference lists would be Pointed (without a Functor superclass) and Monoid. Sebastian [1]: http://hackage.haskell.org/package/dlist -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 6 September 2010 00:11, Sebastian Fischer s...@informatik.uni-kiel.de wrote: Just because we don't have a use now doesn't mean it might not be useful in the future. I am suspicious about complicating a design for potential future benefits. However, difference lists provide an example of a type that support Pointed more naturally than Applicative: the dlist package [1] provides Applicative and Monad instances but only by converting to normal lists in between. Note that even fmap cannot be defined without converting difference lists to normal lists in between. The natural interface to difference lists would be Pointed (without a Functor superclass) and Monoid. Hmmm is there any reason for Functor to be a superclass of Pointed? I understand Functor and Pointed being superclasses of Applicative (which in turn is a superclass of Monad), but can't see any relation between Pointed and Functor... -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Sun, Sep 5, 2010 at 8:40 AM, John Lato jwl...@gmail.com wrote: On Sat, Sep 4, 2010 at 12:34 PM, David Menendez d...@zednenem.com wrote: On Fri, Sep 3, 2010 at 8:23 AM, John Lato jwl...@gmail.com wrote: +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). What's the argument for Pointed? Are there many types which are instances of Pointed but not Applicative? Are there many algorithms which require Pointed but not Applicative? Having Pointed is categorically the right thing to do, which is why I argue for its inclusion. Why is it categorically the right thing to do? When Conor McBride was promoting the use of Applicative (then called Idiom), he provided several instances and algorithms showing that it was a useful generalization of Monad, and it still took several years and a few papers[1] before Applicative found its way into the standard library. In other words, we didn't add Applicative and then discover Traversable later. Traversable was a big part of the argument for why Applicative is useful. [1] Idioms: applicative programming with effects http://www.cs.nott.ac.uk/~ctm/Idiom.pdf Also, I think it would be prudent to avoid a situation with the possibility of turning into a rehash of the Functor/Applicative/Monad mess. Granted, but let's not rush blindly in the opposite direction. Are there any good reasons for not including it? Just because we don't have a use now doesn't mean it might not be useful in the future. This is an argument for putting every member of the container API into its own independent class. Why make things more complicated for little or no benefit? -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Sun, Sep 5, 2010 at 8:47 AM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: I _can_ think of a data type that could conceivably be an instance of Pointed but not Applicative: a BloomFilter (though there's not really any point in having a BloomFilter with only one value that I can see, but maybe someone can since there's the singletonB function). Do Bloom filters have a Functor instance? -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 6 September 2010 04:25, David Menendez d...@zednenem.com wrote: On Sun, Sep 5, 2010 at 8:47 AM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: I _can_ think of a data type that could conceivably be an instance of Pointed but not Applicative: a BloomFilter (though there's not really any point in having a BloomFilter with only one value that I can see, but maybe someone can since there's the singletonB function). Do Bloom filters have a Functor instance? Nope; once something is in the bloom filter you can't change it (you can't even apply an a - a map if I understand correctly). -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 9/3/10 12:16 AM, Ivan Lazar Miljenovic wrote: 1) How should I name the kind * versions? For example, the kind * version of Functor is currently called Mappable with a class method of rigidMap. What should I call the kind * version of Foldable and its corresponding methods? Is there a valid system I can use for these? I think it'd be good to be consistent, whatever you do. For (*-*-*) monads I've seen them called GMonads (for generalized) and indexed monads. For the (*-*) monads, I've seen RMonads and parameterized monads. Here are some links for those who may be interested; they have more links to independent invention by Oleg Kiselyov and also by Bob Atkey, as well as a Coq implementation and a mention of Agda. (For my part, I've since moved on to playing with monads between different categories, which isn't really germane here.) http://winterkoninkje.dreamwidth.org/65416.html http://winterkoninkje.dreamwidth.org/65585.html So, in the interest of generality, perhaps you should just pick a letter or a short prefix and use that for each of the classes. In my blog posts I called them 0-monads, 1-monads, and 2-monads; following Ganesh Sittampalam and Matthieu Sozeau, they'd be monads, r-monads, and g-monads. 2) How far should I go? Should I restrict myself to the data-oriented classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should: I'd say you should do as much as seems reasonable. I tend to take things as far as I can, but that'd end up doing a lot of the same work as category-extras. For a general collections library, I think it'd make sense to try to keep things simpler than that if possible. The simpler it is, the better the uptake will be, so long as it's still complex enough to capture what it needs to. I'd say you should include: Functor, Foldable, Traversable, Pointed, Applicative, Monad, and Monoid (both additive and multiplicative in separate classes, as in the monoids package). Those eight make for a really comprehensive toolkit that does most of the things people frequently need. Of course, not every collection will have instances for all of them. (N.B., following the naming convention in those blog posts, 2-monoids are exactly the same as categories.) 2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default* (since (a - b) isnt' an instance of Ord). That depends. In general, it's better to have smaller classes because it reduces the burden on programmers writing instances and it allows for smaller dictionaries at runtime. In general, I'd say that functions should be included into the class when they often permit specialized definitions which are more efficient than the generic one. And of course, they should be included when they serve as the basis of the class (e.g., both (==) and (/=) should be included in Eq since they both serve as a basis for equality, with no one being obviously easier to implement than the other). If there's little chance of a performance gain, then why would you want it in the class at all? For example, many types can implement fmap/($) more efficiently than by using the liftM/liftA implementations or the default implementation from Foldable. (Of course, fmap is also a basis for the class.) For applicatives, the (*) and (*) operators should be included in the class too. While they seem trivial, some parser combinator libraries can get major performance improvements by using non-generic definitions. There was a discussion about this a while back, I forget if it was here or on the libraries list. And I forget if (**) also had efficient implementations... For another example of the principle, while compare is a sufficient basis for defining Ord, we include (), (=), (), (=) because they can often be implemented more efficiently than by using compare. 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base? If you're defining a new hierarchy, I'd say you should do it correctly, i.e. classFunctor where fmap class Functor = Pointed where unit -- or point class Pointed = Applicative where (*) ; (*) ; (*) class Applicative = Monad where (=) ; join There's no benefit to preserving the ill designs of the past. 3) Am I wasting my time with this? Not at all. Many people want a good containers API, and many people want a cleaned up version of the categorical
Re: [Haskell-cafe] Restricted type classes
On 4 September 2010 17:40, wren ng thornton w...@freegeek.org wrote: On 9/3/10 12:16 AM, Ivan Lazar Miljenovic wrote: 1) How should I name the kind * versions? For example, the kind * version of Functor is currently called Mappable with a class method of rigidMap. What should I call the kind * version of Foldable and its corresponding methods? Is there a valid system I can use for these? I think it'd be good to be consistent, whatever you do. For (*-*-*) monads I've seen them called GMonads (for generalized) and indexed monads. For the (*-*) monads, I've seen RMonads and parameterized monads. Here are some links for those who may be interested; they have more links to independent invention by Oleg Kiselyov and also by Bob Atkey, as well as a Coq implementation and a mention of Agda. (For my part, I've since moved on to playing with monads between different categories, which isn't really germane here.) http://winterkoninkje.dreamwidth.org/65416.html http://winterkoninkje.dreamwidth.org/65585.html So, in the interest of generality, perhaps you should just pick a letter or a short prefix and use that for each of the classes. In my blog posts I called them 0-monads, 1-monads, and 2-monads; following Ganesh Sittampalam and Matthieu Sozeau, they'd be monads, r-monads, and g-monads. I think I'd prefer to put the prefix on the kind * versions (though does a kind * version of something like Monad even make sense?). 2) How far should I go? Should I restrict myself to the data-oriented classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should: I'd say you should do as much as seems reasonable. I tend to take things as far as I can, but that'd end up doing a lot of the same work as category-extras. For a general collections library, I think it'd make sense to try to keep things simpler than that if possible. The simpler it is, the better the uptake will be, so long as it's still complex enough to capture what it needs to. I'd say you should include: Functor, Foldable, Traversable, Pointed, Applicative, Monad, and Monoid (both additive and multiplicative in separate classes, as in the monoids package). Those eight make for a really comprehensive toolkit that does most of the things people frequently need. Of course, not every collection will have instances for all of them. Monoid was probably just going to be re-exported from base, since it's already for kind * (and as such works with all types, and doens't need any parametricity). 2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default* (since (a - b) isnt' an instance of Ord). That depends. In general, it's better to have smaller classes because it reduces the burden on programmers writing instances and it allows for smaller dictionaries at runtime. In general, I'd say that functions should be included into the class when they often permit specialized definitions which are more efficient than the generic one. And of course, they should be included when they serve as the basis of the class (e.g., both (==) and (/=) should be included in Eq since they both serve as a basis for equality, with no one being obviously easier to implement than the other). If there's little chance of a performance gain, then why would you want it in the class at all? Well, the point was that liftA/liftA2 might make more sense as being the methods to be defined for some types rather than *, but you could define them in terms of each other. 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base? If you're defining a new hierarchy, I'd say you should do it correctly, i.e. class Functor where fmap class Functor = Pointed where unit -- or point class Pointed = Applicative where (*) ; (*) ; (*) class Applicative = Monad where (=) ; join There's no benefit to preserving the ill designs of the past. Yes, that was my point. 3) Am I wasting my time with this? Not at all. Many people want a good containers API, and many people want a cleaned up version of the categorical classes which isn't quite as involved as category-extras. Go for it! *sigh* I was almost wishing people would say I _was_ wasting my time with this... ;-) -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list
Re: [Haskell-cafe] Restricted type classes
On 9/4/10 3:50 AM, Ivan Lazar Miljenovic wrote:
On 4 September 2010 17:40, wren ng thorntonw...@freegeek.org wrote:
So, in the interest of generality, perhaps you should just pick a letter or
a short prefix and use that for each of the classes. In my blog posts I
called them 0-monads, 1-monads, and 2-monads; following Ganesh Sittampalam
and Matthieu Sozeau, they'd be monads, r-monads, and g-monads.
I think I'd prefer to put the prefix on the kind * versions (though
does a kind * version of something like Monad even make sense?).
Oh sure. I was just meaning that you should do something systematic like
have XFoo and YFoo, instead of having Foo and Bar. That way people can
just remember ({X,Y},{Foo,Fob,Fez}) instead of having to remember
{(Foo,Bar), (Fob,Baz), (Fez,Quux)}.
I'm a fan of keeping the undecorated names for the current versions, and
using a prefix for the * versions.
I'd say you should include: Functor, Foldable, Traversable, Pointed,
Applicative, Monad, and Monoid (both additive and multiplicative in separate
classes, as in the monoids package). Those eight make for a really
comprehensive toolkit that does most of the things people frequently need.
Of course, not every collection will have instances for all of them.
Monoid was probably just going to be re-exported from base, since it's
already for kind * (and as such works with all types, and doens't need
any parametricity).
I was just talking general API, not necessarily what you need to write.
Reusing the standard classes is fine.
Well, the point was that liftA/liftA2 might make more sense as being
the methods to be defined for some types rather than*, but you
could define them in terms of each other.
Well, liftA and liftM are just generic implementations of fmap using
pure/(*) and return/(=). If you can define fmap directly, then you
should do so. If you can't, you're always free to use the
implementations that liftA and liftM use. The liftA function is defined
explicitly for allowing you can say instance Functor F where fmap =
liftA. There's no reason for liftA to belong to Applicative, because
it has Functor as a superclass and therefore fmap exists. Since fmap can
be more efficient than liftA, it is better to use fmap when writing
code. Note that ($) is defined as fmap, and liftA2, liftA3, etc are
defined in terms of ($) i.e. fmap.
For liftM things are a bit hazier because Monad fails to mention Functor
as an explicit superclass, but it really ought to. Assuming it did, then
there's no reason for liftM to belong to Monad, because we're assured
that fmap exists. Though, again, liftM should be defined as a non-class
function in order to serve as a default implementation of fmap for those
who need it. This is the same reason why Data.Traversable defines
fmapDefault and foldMapDefault: not so that they can be used as
functions, but so that they can be used for giving class instances.
Perhaps we should be calling them fmapApplictiveDefault,
fmapMonadDefault, and fmapTraversableDefault instead...
I suppose you could use liftA2 as the basis of Applicative instead of
(*), but that seems a bit perverse to me. The (*) operation captures
exactly what we want to say--- namely the K axiom for modal logics;
which is equivalent to saying the applicative category has exponentials;
which is also the name for the whitespace of function application;... .
Whereas liftA2 seems like a far more round-about way of getting there.
There may be efficiency reasons for arguing that liftA2 should be
included in _addition_ to (*), but I'm not aware of them.
--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 4 September 2010 18:27, wren ng thornton w...@freegeek.org wrote:
On 9/4/10 3:50 AM, Ivan Lazar Miljenovic wrote:
On 4 September 2010 17:40, wren ng thorntonw...@freegeek.org wrote:
So, in the interest of generality, perhaps you should just pick a letter
or
a short prefix and use that for each of the classes. In my blog posts I
called them 0-monads, 1-monads, and 2-monads; following Ganesh
Sittampalam
and Matthieu Sozeau, they'd be monads, r-monads, and g-monads.
I think I'd prefer to put the prefix on the kind * versions (though
does a kind * version of something like Monad even make sense?).
Oh sure. I was just meaning that you should do something systematic like
have XFoo and YFoo, instead of having Foo and Bar. That way people can just
remember ({X,Y},{Foo,Fob,Fez}) instead of having to remember {(Foo,Bar),
(Fob,Baz), (Fez,Quux)}.
I'm a fan of keeping the undecorated names for the current versions, and
using a prefix for the * versions.
Right, so what prefix? ;-)
Well, liftA and liftM are just generic implementations of fmap using
pure/(*) and return/(=). If you can define fmap directly, then you
should do so. If you can't, you're always free to use the implementations
that liftA and liftM use. The liftA function is defined explicitly for
allowing you can say instance Functor F where fmap = liftA. There's no
reason for liftA to belong to Applicative, because it has Functor as a
superclass and therefore fmap exists. Since fmap can be more efficient than
liftA, it is better to use fmap when writing code. Note that ($) is
defined as fmap, and liftA2, liftA3, etc are defined in terms of ($) i.e.
fmap.
Gah, you're right. I didn't think that liftA = fmap.
For liftM things are a bit hazier because Monad fails to mention Functor as
an explicit superclass, but it really ought to. Assuming it did, then
there's no reason for liftM to belong to Monad, because we're assured that
fmap exists. Though, again, liftM should be defined as a non-class function
in order to serve as a default implementation of fmap for those who need it.
Hmmm, I was thinking of just having liftM = fmap, but yeah using the
monadic defaults makes sense to avoid having to define fmap
explicitly.
This is the same reason why Data.Traversable defines fmapDefault and
foldMapDefault: not so that they can be used as functions, but so that they
can be used for giving class instances. Perhaps we should be calling them
fmapApplictiveDefault, fmapMonadDefault, and fmapTraversableDefault
instead...
I suppose you could use liftA2 as the basis of Applicative instead of (*),
but that seems a bit perverse to me. The (*) operation captures exactly
what we want to say--- namely the K axiom for modal logics; which is
equivalent to saying the applicative category has exponentials; which is
also the name for the whitespace of function application;... . Whereas
liftA2 seems like a far more round-about way of getting there. There may be
efficiency reasons for arguing that liftA2 should be included in _addition_
to (*), but I'm not aware of them.
Well, I _can_ define * for Sets (and have done so), but such an
instance doesn't make any sense because functions don't have Ord
instances. As such, the default liftA2, etc. definitions don't work
with Sets because of this.
--
Ivan Lazar Miljenovic
ivan.miljeno...@gmail.com
IvanMiljenovic.wordpress.com
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 4 September 2010 08:50, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: 3) Am I wasting my time with this? Not at all. Many people want a good containers API, and many people want a cleaned up version of the categorical classes which isn't quite as involved as category-extras. Go for it! *sigh* I was almost wishing people would say I _was_ wasting my time with this... ;-) Hi Ivan Okay, I'll bite... Its good someone is looking into arity versions of Monad, Applicative etc. I think previously pointed you to Conor McBride's message on the subject: http://www.haskell.org/pipermail/haskell-cafe/2008-June/044011.html But, I don't know that work on this will lead to a better API for collection classes... Supposing classes is the way to go, I think there's still a lot of design work to be done on what the classes should be rather than how they are implemented. The current design space (ListLike and your Data.Containers) looks like a factoring of the operations from Data.List and Data.Sequence, personally I have serious doubts that this will lead to a nice API. If I was looking at it myself, I'd start from Chris Okasaki and Ralf Hinze's observations that data structures have analogies to numerical representations. So, I would try to build classes upwards from that (monoid is obviously already in place), rather than design by factoring what List already has. As an example, I think someone has pointed out on the Cafe that C++ has a container library following the analogy to numerical representations. As an aside I thought someone added an implementation of Simon Peyton Jones's Bulk Types with Class to Hackage recently? If they did they didn't give it a findable description. Best wishes Stephen ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 4 September 2010 18:54, Stephen Tetley stephen.tet...@gmail.com wrote: Supposing classes is the way to go, I think there's still a lot of design work to be done on what the classes should be rather than how they are implemented. The current design space (ListLike and your Data.Containers) looks like a factoring of the operations from Data.List and Data.Sequence, personally I have serious doubts that this will lead to a nice API. If I was looking at it myself, I'd start from Chris Okasaki and Ralf Hinze's observations that data structures have analogies to numerical representations. So, I would try to build classes upwards from that (monoid is obviously already in place), rather than design by factoring what List already has. As an example, I think someone has pointed out on the Cafe that C++ has a container library following the analogy to numerical representations. Where exactly can I find these observations on the analogies between data structures and numerical representations? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 4 September 2010 09:57, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: Where exactly can I find these observations on the analogies between data structures and numerical representations? Chris Okasaki - Chapter 9 of Purely Functional Data Structures. Ralf Hinze's slides Number Systems and Data Structures, March 2005 - http://www.cs.nott.ac.uk/~gmh/bctcs-slides/hinze.pdf On second thoughts, I don't think C++ has a collection classes library designed in this way. The message on the Cafe I had in mind was this one, but it is talking about something else: http://www.haskell.org/pipermail/haskell-cafe/2010-April/076157.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
I have only one thing to add to this discussion: On Fri, Sep 3, 2010 at 5:16 AM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: 2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default * (since (a - b) isnt' an instance of Ord). One problem with defining both * and liftA2 in the class in terms of each other is that omitting them from instances is no longer a compile-time error, nor is it even an obvious runtime error - it's frequently an infinite loop, which is unpleasant. Though I understand that it's nice to be able to choose the methods you want to define, I think static error detection is nice too, so I tend to avoid providing extra class methods with defaults unless the alternative is much worse. On that note, why *do* we have missing instance methods filled in with bottoms, so that even without defaults, it's a warning rather than an error? It seems like quite an un-Haskelly thing to do. I know there may be some cases where you do not need to define a particular method, but imo you should be required to explicitly opt out of it if that's the case. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Fri, Sep 3, 2010 at 8:23 AM, John Lato jwl...@gmail.com wrote: Do you have a kind * implementation of Foldable? I'd be interested in seeing it, because I was unable to create a usable implementation (based upon the RMonad scheme) on my last attempt. I always figured it would look something like: class Foldable f where type Elem f :: * foldMap :: Monoid m = (Elem f - m) - f - m with the usual definitions for foldr, foldl, etc. +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). What's the argument for Pointed? Are there many types which are instances of Pointed but not Applicative? Are there many algorithms which require Pointed but not Applicative? -- Dave Menendez d...@zednenem.com http://www.eyrie.org/~zednenem/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 5 September 2010 03:34, David Menendez d...@zednenem.com wrote: On Fri, Sep 3, 2010 at 8:23 AM, John Lato jwl...@gmail.com wrote: Do you have a kind * implementation of Foldable? I'd be interested in seeing it, because I was unable to create a usable implementation (based upon the RMonad scheme) on my last attempt. I always figured it would look something like: class Foldable f where type Elem f :: * foldMap :: Monoid m = (Elem f - m) - f - m with the usual definitions for foldr, foldl, etc. +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). What's the argument for Pointed? Are there many types which are instances of Pointed but not Applicative? Are there many algorithms which require Pointed but not Applicative? Presumably just that it's another possible abstraction. -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
From: Ivan Lazar Miljenovic ivan.miljeno...@gmail.com When I released the first version of container-classes (which I hacked on during AusHac), some people said I should split out the various folding, etc. into duplicates of the current Foldable class, etc. rather than having large monolithic classes. I've been working on this (see my more recent email with the subject along the lines of fighting the type system), and I think I've worked out how to do this: * Have one version of the class (when this makes sense) for values of kind * * Have another version that's closer to the original class for kind * - * but allowing restrictions (e.g. allowing Set to be an instance of Functor). This is based upon Ganesh Sittampalam's rmonad package (http://hackage.haskell.org/package/rmonad). Rather than my original goal of forcing all kind * - * values to be instances of the kind * classes, my new approach is to write instances that automatically make all instances of a * - * class to also be an instance of the kind * class, and to use a newtype wrapper with a phantom type value to allow lifting/promotion of a kind * value to a kind * - * value (e.g. foo :: (Word8 - Word8) - ByteString - ByteString; foo f = unpromote . fmap f . Promote is a valid usage, rather than using the kind * function of rigidMap). My goal with this is that if I have duplicated a class Foo to allow restricted values, then it should be a drop-in replacement for the original in terms of _usage_ (i.e. the class and method/function names are the same, but the type signatures are not). However, I would appreciate the communities advice on a few matters: 1) How should I name the kind * versions? For example, the kind * version of Functor is currently called Mappable with a class method of rigidMap. What should I call the kind * version of Foldable and its corresponding methods? Is there a valid system I can use for these? You could prefix (or postfix) classes with an 'R' similar to RMonad, but that would conflict with the rmonad package. For just Foldable, maybe Reduceable? Do you have a kind * implementation of Foldable? I'd be interested in seeing it, because I was unable to create a usable implementation (based upon the RMonad scheme) on my last attempt. 2) How far should I go? Should I restrict myself to the data-oriented classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should: I don't have a strong opinion either way, but could you re-use RMonad and RFunctor from the rmonad package? 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base? +1 for using the proper constraints, and especially for bringing over Pointed (and anything else that applies). 3) Am I wasting my time with this? I would find it useful, and I appreciate all the care you're putting into the design. Cheers, John ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On 3 September 2010 06:16, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? I also opt for putting the constraints in. 3) Am I wasting my time with this? Definitely not. A standard container interface is something a lot of people want. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Restricted type classes
On Fri, Sep 3, 2010 at 11:47 AM, John Lato jwl...@gmail.com wrote: On Fri, Sep 3, 2010 at 1:29 PM, Ivan Lazar Miljenovic ivan.miljeno...@gmail.com wrote: On 3 September 2010 22:23, John Lato jwl...@gmail.com wrote: Do you have a kind * implementation of Foldable? I'd be interested in seeing it, because I was unable to create a usable implementation (based upon the RMonad scheme) on my last attempt. I was going to make it a subset of Foldable: fold, foldr, foldl, etc. So you don't have a working implementation yet? I ended up thinking this is impossible, although I don't remember the reasoning that led me to that conclusion (and I could very well be wrong). I would suggest that you check this before going too far along the restricted-monad path. This sounds odd to me. An RMonad-style version of Foldable is straightforward: class RFoldable t where rfold :: Control.RMonad.Suitable t a = (a - b - b) - b - t a - b instance RFoldable Data.Set.Set where rfold = Data.Set.fold A similar class for types of kind * is also straightforward: class Reduce t where type Elem t reduce :: (Elem t - r - r) - r - t - r instance Reduce Data.ByteString.ByteString where type Elem Data.ByteString.ByteString = Word8 reduce = Data.ByteString.foldr Both seem to work as I'd expect. Am I missing something? Foldable is pretty trivial--perhaps it was Traversable that you found problematic? - C. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Restricted type classes
When I released the first version of container-classes (which I hacked on during AusHac), some people said I should split out the various folding, etc. into duplicates of the current Foldable class, etc. rather than having large monolithic classes. I've been working on this (see my more recent email with the subject along the lines of fighting the type system), and I think I've worked out how to do this: * Have one version of the class (when this makes sense) for values of kind * * Have another version that's closer to the original class for kind * - * but allowing restrictions (e.g. allowing Set to be an instance of Functor). This is based upon Ganesh Sittampalam's rmonad package (http://hackage.haskell.org/package/rmonad). Rather than my original goal of forcing all kind * - * values to be instances of the kind * classes, my new approach is to write instances that automatically make all instances of a * - * class to also be an instance of the kind * class, and to use a newtype wrapper with a phantom type value to allow lifting/promotion of a kind * value to a kind * - * value (e.g. foo :: (Word8 - Word8) - ByteString - ByteString; foo f = unpromote . fmap f . Promote is a valid usage, rather than using the kind * function of rigidMap). My goal with this is that if I have duplicated a class Foo to allow restricted values, then it should be a drop-in replacement for the original in terms of _usage_ (i.e. the class and method/function names are the same, but the type signatures are not). However, I would appreciate the communities advice on a few matters: 1) How should I name the kind * versions? For example, the kind * version of Functor is currently called Mappable with a class method of rigidMap. What should I call the kind * version of Foldable and its corresponding methods? Is there a valid system I can use for these? 2) How far should I go? Should I restrict myself to the data-oriented classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should: 2a) Which namespace to use? Should Monad go in Data.Restricted.Monad to keep it in the same namespace as the other classes, or should I make it closer to base with Control.Restricted.Monad? 2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default * (since (a - b) isnt' an instance of Ord). 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base? 3) Am I wasting my time with this? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
