Multiarity fmap is no longer fmap

[tel]

While reading the Fluokitten documentation I noticed that it's often touted as an advantage of implementing these concepts in Haskell that fmap is able to variadic. Later, it's pointed out Haskell requires using (<*>) or ap to achieve this effect.

The problem is that variadic fmap just isn't fmap—it's a stronger requirement than just being a Functor. In particular, it imbues a kind of sequencing on your "Functor" which is above the call of duty for just having a Functor—you're opening up each of the boxes in sequence, calling the combining function, then closing them back. A normal functor should disallow that.

One place this distinction shows up is that it prevents you from extracting the commonalities between various applicative instances of Lists/vectors. The applicative instance of vector in Fluokitten is the "Cartesian applicative"

pure a = [a]
fs <*> xs = [f x | f <- fs, x <- xs]

> [(+1), (+2)] <*> [1,2,3]
[2,3,4,3,4,5]

But there's also a law-abiding applicative instance for Lists/vectors of any fixed length. Often this is implemented with infinite lists in Haskell

pure a = repeat a  -- [a, a, a, a, ...]
fs <*> xs = zipWith (\f x -> f x) fs xs

> [(+1), (+2)] <*> [1,2,3]
[2,4]

This is all well and good—these are distinct types. However, it's important to note that they both have identical Functor instances so long as fmap is not variadic.

In fact, in Haskell we have the guarantee that there is exactly one non-pathological function with the type

fmap :: (a -> b) -> (f a -> f b)

and satisfying fmap id = id. That's the power of the Functor laws.

---

Obviously, it's a design choice in Fluokitten to include variadic fmap or not, but it's a patent inaccuracy in the documentation to call an interface Functor if it provides a variadic fmap.

[blueberry]

Thank you for the patience and a very detailed description. It would be very helpful if you could translate the problem to clojure code that demonstrate the issue. That would help in deciding how to handle it.

[tel]

The exact problem should be invariant to the language used to write it. The specific Clojure code is in the definition of the Functor protocol

(defprotocol Functor
  (fmap [fv g] [fv g fvs]))

should be, I believe

(defprotocol Functor
  (fmap [fv g]))

as the variadic fmap prevents you from having a type be only a Functor—it'll always accidentally be an Applicative as well.

[blueberry]

Can you provide a demonstration case where that is a problem?

[tel]

It won't cause any problems, just reduce the orthogonality of your interface. Anyone implementing it will need to also design the Applicative implementation when writing their fmap. Honestly, the places where this shows up by force (and would be a bug otherwise) are few any far between. A Haskell example which isn't really problematic in Clojure is

data Void = Void Void
data Foo x = Foo { foo :: Void }

 instance Applicative Foo where -- this cannot exist, else
 foo (pure ()) :: Void -- we could construct Void, which is invalid

As a larger example, it's often valid to construct Const Functors which pretend to hold one thing while actually holding something else

data Const b a = Const { getConst :: b }

instance Functor (Const b) where fmap (Const b) = Const b
instance Monoid b => Applicative (Const b) where 
  pure _ = Const mempty
  Const b1 <*> Const b2 = Const (mappend b1 b2)

and these are always Functors but only Applicatives when b is a monoid. This could be constructed in Clojure but it'd be a bit silly.

---

Really, the sum of my issue is just that it's not valid to say something is a functor and ask for a variadic fmap. It causes the Functor interface to step on the foot of Applicative, it brings the interface further from the Haskell one, and it finally makes even less sense in terms of the category theory here.

[blueberry]

Since the goal is not 100% compatibility with Haskell, but a familiarity and usefulness for Clojure developers, I keep the variadic fmap. Honestly, even Haskell have its confusing points when it comes to CT, at least to me (I am not an CT expert nor a mathematician, BTW). If there is a serious practical programming problem, I'll reconsider this, otherwise I think compatibility with Clojure is more important than compatibility with Haskell.

[tel]

My concern is not so much that this should be compatible with Haskell either. I'm also not invested in saying whether or not this produces familiarity or usefulness for Clojure developers. In totality, the problem is that whether or not variadic fmap is useful, it's no longer honest to call it a Functor. You may as well invent your own term ("Mappable" is popular).

[tel]

Then, as a secondary note, variadic fmap makes it confusing as to what Applicative brings to the table since variadicity and the notion of sequencing that comes along with it is usually exactly what you'd say Applicative brings to the table.