4

As mentioned in Hackage for Applicative Functors, they are strong lax monoidal functors. So why doesn't their definition in Haskell show it like so :

class Functor f => MonoidalApplicative f where
  mult :: f a -> f b -> f (a,b)
  unit :: a -> f a 

  starAp :: f (a -> b) -> f a -> f b
  starAp h x = fmap (uncurry ($)) (mult h x)

<*> (starAp) is easily reconstructed in terms of the multiplication and this definition looks simpler to me. For exemple, here is the Maybe instance :

instance MonoidalApplicative Maybe where
  mult (Just x) (Just y) = Just (x,y)
  mult _ _ = Nothing

  unit x = Just x
V. Semeria
  • 3,128
  • 1
  • 10
  • 25
  • 7
    The `(<*>)` presentation tends to be more convenient in day-to-day programming, even though the `mult` one is indeed neater in some aspects (e.g. the applicative laws look nicer when expressed in its terms). This scenario is similar to the relationship betweeen `(>>=)` and `join`. Relevant blog post: http://blog.ezyang.com/2012/08/applicative-functors/ – duplode Dec 30 '16 at 18:34
  • 5
    Note: the monoidal presentation usually has `unit :: f ()`. `pure`, then, can be recovered through `pure x = fmap (const x) unit`. – duplode Dec 30 '16 at 18:38
  • 2
    See http://stackoverflow.com/a/27262462/414413 – Cirdec Dec 30 '16 at 18:39
  • Almost always the standard mathematical notation/convention is better (that is, more efficient) for proving things, but not necessarily so for programming. – mnish Dec 31 '16 at 08:07

1 Answers1

6

As it was mentioned in comments to your answer, there is similar story with join and >>=. When there're several semantically equivalent ways to define something it's better always to choose most efficient & pragmatic way. Haskell was designed to write code, not to prove things (though, somehow Haskell haven't still become very popular programming language unfortunately).

If starAp had default implementation almost nobody would implement it (just as it happens now with >> in Monad type class). But <*> is extremely useful operation. It is used in applicate & monadic parsers a lot (megaparsec, attoparsec, optparse-applicative) and I can't imagine my life w/o liftA* for joining things. And it is very important for this operation to be as efficient as possible. Implementing starAp as fmap (uncurry ($)) (mult h x) may bring hard times to inlining and optimizing things for compiler.

Moreover, representation of Applicative using mult and unit operations doesn't really solves any problems. Obviously, mult = liftA2 (,). But your implementation with

mult (Just x) (Just y) = Just (x,y)

not fully correct. Because your implementation is not lazy enough. You will evaluate both cases when it may be enough to evaluate only one. So you still can mess up even with this simple function. Thus this representation is strictly worse.

Shersh
  • 9,019
  • 3
  • 33
  • 61
  • But in the case of Monad `join` was actually supposed to be added to Monad with the AMP. It wasn't due to technical difficulties: http://stackoverflow.com/questions/31552064/why-isnt-join-part-of-the-monad-class/31552223 – Julia Path Dec 31 '16 at 12:26
  • So is it just a performance concern ? Then why not declare both `mult` and `<*>` in Applicative, each one calling the other, so that instances can choose which one to override (or both) ? Also, almost all calls I've seen to `<*>` are fully evaluated, giving as many values as the function has variables. For example with a 3-variable function, I prefer `liftA3 f x y z` to `f <$> x <*> y <*> z`. Then the performance expectations are on `liftA3` rather than `<*>`. – V. Semeria Dec 31 '16 at 13:08
  • 1
    `liftA3 f x y z = f <$> x <*> y <*> z`, this function is not faster than `<*>`. And it can easily not fully evaluate something. Example: sum of two maybe's. `liftA2 (+) Nothing (Just $ 2^(2^100))` evaluates instantly while `liftA2 (+) (Just 3) (Just $ 2^(2^100))` will kill your machine. Very legit case. Why define both when `mult = liftA2 (,)` and such implementation is lazy enough? Allowing multiple functions inside one type class is error-prone approach. You can see another explanations here: https://ghc.haskell.org/trac/ghc/wiki/Proposal/MonadOfNoReturn – Shersh Dec 31 '16 at 15:47
  • 1
    There is a delicate issue here. If you allow unrestricted recursions and non-strictness, then Hask is not a category and Applicatives are not even functors. See for example [Wader's remark](http://ttic.uchicago.edu/~dreyer/course/papers/wadler.pdf) for a sufficient condition under which 'parametricity' holds in System-F like calculus, without which you can easily construct a 'counterexample' to (say) the Yoneda lemma. – mnish Jan 01 '17 at 00:34
  • 2
    So this is not only a performance concern, but also about correctness. In a sense Haskell's categorical definitions are a declaration that 'this is a programming language, and may not be correct in a strictly mathematical sense'. – mnish Jan 01 '17 at 00:44