On Fri, Sep 3, 2010 at 11:47 AM, John Lato wrote:

On Fri, Sep 3, 2010 at 1:29 PM, Ivan Lazar Miljenovic wrote:

...

On 3 September 2010 22:23, John Lato 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.

On Sat, Sep 4, 2010 at 12:34 PM, David Menendez wrote:

On Fri, Sep 3, 2010 at 8:23 AM, John Lato 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

On Sun, Sep 5, 2010 at 7:47 AM, Ivan Lazar Miljenovic < ivan.miljenovic@gmail.com> wrote:

On 5 September 2010 22:40, John Lato 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

On 6 September 2010 00:11, Sebastian Fischer 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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On 6 September 2010 16:15, wren ng thornton 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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On 7 September 2010 12:18, wren ng thornton 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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On 7 September 2010 14:24, wren ng thornton 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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On 9 September 2010 12:10, wren ng thornton 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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

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

On 6 September 2010 04:25, David Menendez wrote:

On Sun, Sep 5, 2010 at 8:47 AM, Ivan Lazar Miljenovic 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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

On Sun, Sep 5, 2010 at 7:18 PM, David Menendez wrote:

On Sun, Sep 5, 2010 at 8:40 AM, John Lato wrote:

...

On Sat, Sep 4, 2010 at 12:34 PM, David Menendez

wrote:

...

...

On Fri, Sep 3, 2010 at 8:23 AM, John Lato 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

On Mon, Sep 6, 2010 at 12:33 PM, David Menendez wrote:

On Mon, Sep 6, 2010 at 7:51 AM, John Lato wrote:

...

On Sun, Sep 5, 2010 at 7:18 PM, David Menendez wrote:

...

On Sun, Sep 5, 2010 at 8:40 AM, John Lato wrote:

...

On Sat, Sep 4, 2010 at 12:34 PM, David Menendez wrote:

...

On Fri, Sep 3, 2010 at 8:23 AM, John Lato 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

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

On Tuesday 07 September 2010 05:22:55, David Menendez wrote:

On Mon, Sep 6, 2010 at 10:22 PM, wren ng thornton 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.

On Wed, Sep 8, 2010 at 11:17 PM, wren ng thornton 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 pure@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 http://www.eyrie.org/~zednenem/

On Thu, Sep 9, 2010 at 11:33 PM, wren ng thornton 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 http://www.eyrie.org/~zednenem/

On Wednesday 08 September 2010 11:17:43 pm wren ng thornton wrote:

-- | Proof that impure is not pure@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