13

Are there any good examples of Functors which are not Applicatives? By good, I'm seeking non-trivial (not Const Void) examples which don't need appeals to undefined. If there are none is there any method of proving that the space there is uninteresting?

This is similar to Good examples of Not a Functor/Functor/Applicative/Monad?, but it wasn't completely resolved there.

As a follow-up question, are there any interesting examples of Functors which might be left without Applicative instances due to having far too many non-canonical Applicative instances to be meaningful? For instance, "extended Maybe" is a bit boring

data MayB a = Jus a | Nothing1 | Nothing2 | Nothing3 | ...

instance Applicative MayB where
  pure = Jus
  Jus f <*> Jus x = Jus (f x)
  Jus f <*> n     = n
  n     <*> Jus x = n
  n1    <*> n2    = methodOfResolvingNothingWhatsoever n1 n2

Are there examples where the variations of the Applicative instance are more material?

Community
  • 1
  • 1
J. Abrahamson
  • 72,246
  • 9
  • 135
  • 180
  • As a side note, `data MayB a = Jus a | Nothin Int` and `Nothin n1 <*> Nothin n2 = Nothin $ max n1 n2` is how I'd implement it. Then you have a notion of the level of failure where the higher level takes precedence. Not sure where this is useful, but it's easy to encode. – bheklilr Feb 28 '14 at 15:44
  • 2
    Defining uninteresting would be good. To my knowledge, `Cont m` is an applicative iff `m` is a monoid so there's a lot of functors-not-applicatives there. Essentially anything with a lot of "structure" unrelated to the parameter which we've defined functor over is going to have a hard time being an applicative. – daniel gratzer Feb 28 '14 at 16:32
  • @bheklilr That's sensible, there's also the "purely-applicative Either" `data Eit b a = L b | R a` with `instance Monoid b => Applicative (Either b) where L b1 <*> L b2 = L (b1 <> b2)`. Generally, though, there are just a whole lot of ways to merge failures and "purely applicative Either" is the closest thing I know to a canonical method. – J. Abrahamson Feb 28 '14 at 16:50
  • @jozefg That's true and I don't much know a good way to define "uninteresting". I think your point about structure holds generally. I'd just like to motivate the need for a `Functor` typeclass and not just an `Applicative` one that includes `fmap`. – J. Abrahamson Feb 28 '14 at 16:52
  • @jozefg: `(a -> m) -> m` can be given an `Applicative` instance (modulo wrapping it in a `newtype`) for any `m` that has an associative binary operation with an identity, not just ones that happen to have been given a `Monoid` instance. – Tom Ellis Feb 28 '14 at 17:01
  • @J.Abrahamson I made an attempt to make my thought a bit clearer, not sure if I succeeded. – daniel gratzer Feb 28 '14 at 17:06
  • I think `Const` is more interesting than it's given credit for. The connections to big products and general lens uses demonstrate how common it is to have structure beyond the functor parameter. – Anthony Feb 28 '14 at 17:46
  • @jozefg that's wrong. In Haskell, all Monads are Applicatives. – Sassa NF Feb 28 '14 at 18:42
  • @SassaNF That was a mistake sorry, I had meant `Const` – daniel gratzer Mar 01 '14 at 05:20

2 Answers2

5

The main place where I see functor but not applicatives is in large product types. Consider something like

 data Mean where
    Unfair :: Monad a => a () -> Mean
 data Foo a = Bar Int Mean a

This is easily a functor, but there's no way to make this an applicative because

 (Bar i g f) (Bar i' g' a) = Bar ??? ??? (f a)

We can only fill in our ???s with something that's a monoid-like in at least one way and Mean never is since we have no way of specifying something to combine two values of arbitrary types g :: a and g' :: b in an associative way.

Additionally, we need the mempty or something like it for pure :: a -> f a. We're given an a so most of the data type that involves an a is trivial to construct, but the rest needs a sane "empty" value.

So if we smashed applicative and functor into one large type class, most of lens would fall apart because most of the useful cases for lens involve situations just like these, where there isn't a sane Applicative instance.

So to put this in a hand-wavey squishy way: When there's a lot of "stuff" in a type that isn't directly to do with the type parameter applicative is defined over, we need a way to merge all of this "stuff" which isn't always possible.

daniel gratzer
  • 52,833
  • 11
  • 94
  • 134
  • 2
    `Int -> Bool` can be made a monoid in many ways. `Bool` can be made a monoid in four ways I think, and then you take the product `Int`-many times. – Tom Ellis Feb 28 '14 at 17:14
  • `instance Monoid (Int -> Bool) where { mempty = const False; mappend f1 f2 = \x -> f1 x || f2 x }` – Tarmil Feb 28 '14 at 17:17
  • You can also always define the Leftmost monoid: `Bar i g f <*> Bar _ _ a = Bar i g (f a)` – J. Abrahamson Feb 28 '14 at 17:23
  • Is that really a monoid? It doesn't seem to have an identity, in general. This will prevent you from defining `pure`. – Tom Ellis Feb 28 '14 at 17:25
  • Losing the notion of a "single-target `Lens`" is pretty important—even if there were no `Functor`s without `Applicative`s then `forall f . Functor f => f` would still be a very different type than `forall f . Applicative f => f`. It doesn't help at all with the argument I was trying to research for, but that doesn't mean it's not very true. – J. Abrahamson Feb 28 '14 at 17:25
  • @TomEllis Er, I spoke imprecisely—my definition defines only the semigroup part, but you're good with these concrete types since there are `2^N * N` `mempty`'s possible here: `pure = Bar 0 (const True)` – J. Abrahamson Feb 28 '14 at 17:27
  • I'm saying the "Leftmost monoid" isn't a monoid. Although there may be many choices you could make for the identity, none of them satisfies the monoid laws. – Tom Ellis Feb 28 '14 at 17:30
  • Oh, apologies. You're absolutely correct. You need the `Maybe`. – J. Abrahamson Feb 28 '14 at 17:31
  • @TomEllis Oh you're totally right, that was just careless mistake on my part, I'll edit with an example of something that's not a monoid :) – daniel gratzer Feb 28 '14 at 19:07
  • @jozefg Your `Monad a => a -> Mean` doesn't kind-check – J. Abrahamson Feb 28 '14 at 22:24
3

A very important (if unfair) example is 

{-# LANGUAGE ExistentialQuantification #-}

data AFunctor a = forall f . Functor f => AFunctor { unFunct :: f a }
J. Abrahamson
  • 72,246
  • 9
  • 135
  • 180