9

What is the general term for a functor with a structure resembling QuickCheck's promote function, i.e., a function of the form:

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

(this is the inverse of flip $ fmap (flip ($)) :: f (a -> b) -> (a -> f b)). Are there even any functors with such an operation, other than (->) r and Id? (I'm sure there must be). Googling 'quickcheck promote' only turned up the QuickCheck documentation, which doesn't give promote in any more general context AFAICS; searching SO for 'quickcheck promote' produces no results.

Jonathan Cast
  • 4,569
  • 19
  • 34
  • Is [`sequenceA`](http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-Traversable.html#v:sequenceA) relevant? – Christian Conkle Oct 08 '14 at 21:36
  • Let me see. Substituting into the type of `sequenceA`, we would get `t = (->) a` and `f = f`. So if `(->) a` had a `Traversable` instance, this function would exist for all `a`. I think `Traversable ((->) a)` requires `(Bounded a, Enum a)` of or the equivalent, though. – Jonathan Cast Oct 08 '14 at 22:11
  • 1
    For what it's worth, the [universe](http://hackage.haskell.org/package/universe) package family provides the [requisite `Traversable` instance](http://hackage.haskell.org/package/universe-reverse-instances-1.0/docs/src/Data-Universe-Instances-Traversable.html). – Daniel Wagner Apr 05 '16 at 20:48
  • @Daniel Wagner, ah, given `Finite`, which I guess is essentially the same thing. – Jonathan Cast Apr 05 '16 at 20:50

3 Answers3

5
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(=<<) :: Monad m => (a -> m b) -> m a -> m b

Given that Monad is more powerful an interface than Applicative, this tell us that a -> f b can do more things than f (a -> b). This tells us that a function of type (a -> f b) -> f (a -> b) can't be injective. The domain is bigger than the codomain, in a handwavey manner. This means there's no way you can possibly preserve behavior of the function. It just doesn't work out across generic functors.

You can, of course, characterize functors in which that operation is injective. Identity and (->) a are certainly examples. I'm willing to bet there are more examples, but nothing jumps out at me immediately.

Carl
  • 26,500
  • 4
  • 65
  • 86
1

So far I found these ways of constructing an f with the promote morphism:

  • f = Identity
  • if f and g both have promote then the pair functor h t = (f t, g t) also does
  • if f and g both have promote then the composition h t = f (g t) also does
  • if f has the promote property and g is any contrafunctor then the functor h t = g t -> f t has the promote property

The last property can be generalized to profunctors g, but then f will be merely a profunctor, so it's probably not very useful, unless you only require profunctors.

Now, using these four constructions, we can find many examples of functors f for which promote exists:

f t = (t,t)

f t = (t, b -> t)

f t = (t -> a) -> t

f t = ((t,t) -> b) -> (t,t,t)

f t = ((t, t, c -> t, (t -> b) -> t) -> a) -> t

Also note that the promote property implies that f is pointed.

point :: t -> f t
point x = fmap (const x) (promote id)

Essentially the same question: Is this property of a functor stronger than a monad?

Community
  • 1
  • 1
winitzki
  • 3,179
  • 24
  • 32
  • Could you add the actual instances you're suggesting? For example what does this instance for `(t, t)` look like? When implementing `a -> (b, b) -> (a, a) -> (b, b)`, does it just apply the input function to both `a`s and throw away 2/4 `b`s? – Asad Saeeduddin Mar 09 '20 at 13:40
  • @AsadSaeeduddin The instance for `(t, t)` requires us to implement `promote:: (a -> (b, b)) -> (a -> b, a -> b)`, not `a -> (b, b) -> (a, a) -> (b, b)`. Implementing `promote:: (a -> (b, b)) -> (a -> b, a -> b)` does not throw away anything; `promote f = (fst . f, snd . f)`. Try to derive the general construction: if `f` and `g` have promote then `h` has promote where `h a = (f a, g a)`. There is only one way to implement `promote` for `h`, and it does not throw away any information. – winitzki Mar 10 '20 at 18:46
1

Data.Distributive has

class Functor g => Distributive g where
  distribute :: Functor f => f (g a) -> g (f a)
  -- other non-critical methods

Renaming your variables, you get

promote :: (c -> g a) -> g (c -> a)

Using slightly invalid syntax for clarity,

promote :: ((c ->) (g a)) -> g ((c ->) a)

(c ->) is a Functor, so the type of promote is a special case of the type of distribute. Thus every Distributive functor supports your promote. I don't know if any support promote but not Distributive.

dfeuer
  • 48,079
  • 5
  • 63
  • 167
  • 3
    `Distributive` is strictly stronger than `promote`. Every `Distributive` functor `g` is representable: that is, there exists a constant type `b` such that `g t = b -> t `. However, functors such as `g t = (t -> a) -> t` have `promote` but are not representable and thus fail to be `Distributive`. More generally, a functor `g` defined as `g t = c t -> h t` has `promote` if `c` is any contrafunctor and `h` has `promote. This construction can define a `Distributable` only if `c` is a constant (contra)functor. – winitzki Sep 24 '16 at 01:22