Can ZipList be Distributive?

Question

Base provides ZipList, which is just a wrapper for [] where <*> is based on zip instead of cartesian-product. This isn't the default because it's not consistent with the Monad [] instance, but some people find it more intuitive, and both behaviors are useful in different contexts.

Edward Kmett provides Distributive, the dual of Traversable. A Traversable can be mapped/pushed/distributed into any Applicative Functor; a Distributive can be pulled/factored out of any Functor. (For reasons I haven't unpacked, distribute does not require the outer layer to be Applicative.)

Length-indexed lists are Distributive, and work how you'd expect. Specifically, their Applicative instance is based on zip, just like ZipList! This suggests ZipList could also be Distributive, which would be useful.

The docs for Distributive note two things that must be true of any instance:

• "It [must be] isomorphic to (->) x for some x."
  • A list is isomorphic to a partial function Int ->.
• "[It] will need to have a way to consistently zip a potentially infinite number of copies of itself."
  • This is more-or-less the raison d'être of ZipList.

Is that good enough? I spent a couple hours this afternoon trying to write instance Distributive ZipList where distributive = ... and couldn't quite get it to work. For most functors f ZipList a there's an obvious meaning to distribute f, although I worry that might just be because I'm not thinking of enough non-Traversable functors.

• Maybe is tricky; should distribute Nothing be [] or repeat Nothing? But distribute is dual to sequenceA, and the Traversable Maybe instance says it should be repeat Nothing.
• (->) e might be the dealbreaker.
  • Intuitively distribute $ const (repeat x) = repeat (const x).
  • We can extend that to any function that's guaranteed to return an infinite list; it looks kinda like (\i -> (! i) <$> f) <$> [0..].
  • We can extend that to functions returning finite lists; we end up with an infinite list of partial functions. It's not obvious to me that that's unacceptable; partial functions show up all the time when working with lists.
  • But that means distribute $ const [] ≅ repeat undefined, which is kinda silly.
  • The instance Applicative ZipList contains an important design decision: length (a <*> b) == min (length a) (length b) (as opposed to an error or whatever). We're not leveraging that at all; the way I can see we might would be distribute = const [].

Does anyone see a way forward?

If the partial-function interpretation were "acceptable", could we generalize that in any less-dumb way than distribute f = (\i -> (!! i) <$> f) <$> [0..]?

Answer 1

No, it cannot be distributive.

The obvious Distributive instance for Pair looks like this:

instance Distributive Pair where
    distribute vs = Pair (pFst <$> vs) (pSnd <$> vs)

Now let's think about the list instance. (Let's ignore the ZipList noise for now and just suppose basic lists have the zippy instance.) We require distribute . distribute = id. Suppose

x = distribute (Pair "" "a")

so that the law requires:

distribute x = Pair "" "a"

We can substitute the definition of distribute for Pair, and get:

Pair (pFst <$> x) (pSnd <$> x) = Pair "" "a"

This is a problem, because list's (<$>) preserves length, and here we are requiring it to return answers of two different lengths when provided with the same argument. Whoops!

As an alternative, you might be interested in data Stream a = Cons a (Stream a), the type of guaranteed-infinite lists, which can be made Distributive:

sHead :: Stream a -> a
sHead (Cons a _) = a

sTail :: Stream a -> Stream a
sTail (Cons _ as) = as

instance Distributive Stream where
    distribute streams = Cons (sHead <$> streams) (distribute (sTail <$> streams))