Inconsistency in protocol realisations for sequential collections

[adavydow]

1. Using 'fmap' as variadic function requires instance of Applicative. Proof: you can define 'fapply' as (partial fmap apply) and '(pure x)' as (fmap #(identity x)) (it is impossible to write this realisation of 'pure' in clojure due to the absence of return-type polymorphism). Looks like this point was discussed in Issue Multiarity fmap is no longer fmap #12 .

2. Lists and other sequentional collections can be instances of Applicative and Monad in two different ways: as fixed-size vectors with componentwise operations, and as an undetermenistic computation (undetermenistic computation is more common and it is a default behaviour in Haskell):

   1. (fapply [inc dec] [3 4]) = [4 3]
   2. (fapply [inc dec] [3 4]) = [4 2 5 3]

   If variadic 'fmap' and 'fapply' are defined independently, then inequality
   (not= (fmap apply [inc dec] [1 2]) (fapply [inc dec] [1 2])) is an unexcpected behaviour from my point of view.
   And in the case of sequentional collections (i) is chosen for 'fmap' and (ii) for 'fapply'.

3. Every Monad has an inherited Applicative Functor structure, but in the library Monad and Applicative protocol realisations for sequential collections are incoherent (see (2)) which is an unexpected behaviour from my point of view.

[blueberry]

Hi Alex. Thank you for taking time to write a detailed comment.

I think there is a flaw in your proof. If I understood correctly, you put it as:

1. Suppose that a and b are true.
2. Applying some rules, we get c, which is inconsistent.
3. Therefore, there is unexpected behavior in sequential collections.

I must admit that I don't think that 3 follows from 1 and 2. Actually, the strategy in your proof is one of most common proving strategies in mathematics (as far as I remember), but I would say that the real conclusion should be: a or b (or both) is not true. And, indeed, a and b are not.

So, your proof demonstrated that:

1. fapply is not equivalent to (fmap apply) (note: partial is not needed here, fmap supports currying). Nor Fluokitten claims it is. I think that Haskell even does not have a lisp-style apply function.
2. (pure x) is not equivalent to (fmap #(identity)).
   Your code is broken, since Fluokitten pure needs to know the type of the context. So, for collections it should be something like (pure [] x). Also, (fmap #(identity)) is equivalent to (fmap identity), which is clearly not equivalent to pure, since (fmap identity) creates a function that just returns the unchanged input, and (pure [] x) should return [x].

[adavydow]

Thank you for your response, however you completely missed my point.

1. Your library claims to represent some categorical theory structures as protocols. My proof in (1) has nothing to do with your realisation of fapply, the only thing I tried to proof is that your Functor protocol implies Applicative functor structure on objects in hand, not Functor structure. (Functor structure alone is not enough to implement variadic fmap).
   In fact you can translate categorical definitions of Functor and Applicative Functor to programmers' language like this:
   Functor is anything you can non-variadic fmap (non-variadic fmap takes a function of 1 parameter and a functor).
   Applicative Functor is anything you can variadic fmap (variadic fmap takes a function of x >= 0 parameters and x functors).
2. I mentioned, that there is no way to implement (pure x) as (fmap #(identity x)) in clojure (my phrase about absence of return-type polymorphism and your phrase about need of context is in fact the same). However the claim you tried to object (which is not my claim) that (pure x) = (fmap #(identity)) is absurd and i completely agree that it makes no sence. To make my reasonings about pure clearer I can suggest the following implementation which is completely valid for clojure:
   (pure [x] [y]
   (fmap (fn [z] (identity x)) y)). Usage: (pure 3 [4]) = [3]. (y is for context only))
3. So both of your protocols implies structures which are isomorphic (an idea of isomorphism is described above). This structure is called "Applivative Functor" in category theory. However
   for sequentional collections there are several ways to provide Applicative Functor structure, and your interfaces provides two different structures.
4. I'm not going to tell you what applicative functor structure (i) or (ii) you shall prefer for sequential collections, but if you choose one it's better to be consistent and stick with it.
   So, if (fapply [inc dec] [1 2]) = [1 0 1 3] (ii)
   then it'll be greate if (fapply [+] [1 2] [3 4]) = [3 5 5 6] and (fmap + [1 2] [3 4]) = [3 5 5 6]
5. In category theory every Monad is Applicative Functor and every Applicative Functor is Functor.
   In programming language it can be expressed as inheritance: Functor is a base interface, Applicative Functor extends Functor and Monad extends Applicative (one of the problems in Haskell is absence of this inheritance and they are going to solve it in future versions).
   I don't tell that realisation of this inheritance is essential, but there is a problem:
   Defining realisations of Functor, Applicative and Monad protocols for a list you are defining Applicative Functor structure on lists three times, however this structures differ. And this is unexpected behabiour for me (it has nothing to do with Haskell, it just breakes my expectations carried from cathegory theory)

[blueberry]

If you'd provide an implementation that is better than existing, I'll be glad to consider including it in fluokitten.

[adavydow]

Great! I was going to provide such a realisation anyway, but I'll always
prefer collaboration to competing realisations.

On Tue, Dec 16, 2014 at 8:34 PM, Dragan Djuric notifications@github.com
wrote:

If you'd provide an implementation that is better than existing, I'll be
glad to consider including it in fluokitten.

—
Reply to this email directly or view it on GitHub
#17 (comment)
.

[adavydow]

I made changes we discussed in a fork. Here is a changelog: https://github.com/adavydow/fluokitten/blob/master/CHANGELOG.md. What do you think about changes like this?
(Currently performance is a bit slower, because for test purposes I removed specialized functor and variadic implementations, but I'm going to return them)

[blueberry]

I discussed variadic fmap in the first response and do not agree with your argumentation. Not only the changes are breaking, but the three conditions you mention in the changelog are pulled from thin air - all existing fluokitten implementations satisfy all functor, applicative and monadic laws already. Also, you just removed many tests that started failing once you introduced the changes.

Having said that, nothing should stop you from releasing the library that is suited to your liking, but please do not call it Fluokitten, and do not use Fluokitten's versioning since that will cause confusion with users when I release version 0.4.0.

[adavydow]

ok

On Sat, Dec 20, 2014 at 12:31 PM, Dragan Djuric notifications@github.com
wrote:

I discussed variadic fmap in the first response and do not agree with your
argumentation. Not only the changes are breaking, but the three conditions
you mention in the changelog are pulled from thin air - all existing
fluokitten implementations satisfy all functor, applicative and monadic
laws already. Also, you just removed many tests that started failing once
you introduced the changes.

Having said that, nothing should stop you from releasing the library that
is suited to your liking, but please do not call it Fluokitten, and do not
use Fluokitten's versioning since that will cause confusion with users when
I release version 0.4.0.

—
Reply to this email directly or view it on GitHub
#17 (comment)
.