-2

In Maybe applicative, <*> can be implemented based on fmap. Is it incidental, or can it be generalized to other applicative(s)?

(<*>)   ::  Maybe   (a  ->  b)  ->  Maybe   a   ->  Maybe   b
Nothing <*> _   =   Nothing
(Just   g)  <*> mx  =   fmap    g   mx

Thanks.

See also In applicative, how can `<*>` be represented in terms of `fmap_i, i=0,1,2,...`?

Tim
  • 1
  • 141
  • 372
  • 590
  • 2
    Since the `fmap f x = pure f <*> x` law holds, it is not uncommon that one is sometimes implemented in terms of the other. But here the implementation of `<*>` still does some work: it does pattern matching and unwraps the `g` out of the `Just` data constructor. – Willem Van Onsem Jul 26 '19 at 12:48
  • Note that your `fmap0` is `pure`, something that is *not* defined on a `Functor`. – Willem Van Onsem Jul 26 '19 at 12:52
  • Thanks. In Maybe applicative, could you write `<*> without fmap? – Tim Jul 26 '19 at 13:00
  • 1
    you can just "inline" the definition of `fmap` in the definition of `(<*>)`, like `Just f <*> Just x = Just (f x)` and `_ <*> _ = Nothing` – Willem Van Onsem Jul 26 '19 at 13:01
  • 5
    As @AJFarmar already says, it might probably help to "get your hands dirty" and do some implementations. Yes studying algebraic structures definitely has a lot of value (especially in Haskell), but usually one appreciates the power of algebraic structures more, once one has solved some challenges. – Willem Van Onsem Jul 26 '19 at 13:16

1 Answers1

5

It cannot be generalized. A Functor instance is unique:

instance Functor [] where
    fmap = map

but there can be multiple valid Applicative instances for the same type constructor.

-- "Canonical" instance: [f, g] <*> [x, y] == [f x, f y, g x, g y]
instance Applicative [] where
    pure x = [x]
    [] <*> _ = []
    (f:fs) <*> xs = fmap f xs ++ (fs <*> xs)

-- Zip instance: [f, g] <*> [x, y] == [f x, g y]
instance Applicative [] where
    pure x = repeat x
    (f:fs) <*> (x:xs) = f x : (fs <*> xs)
    _ <*> _ = []

In the latter, we neither want to apply any single function from the left argument to all elements of the right, nor apply all the functions on the left to any single element on the right, making fmap useless.

chepner
  • 497,756
  • 71
  • 530
  • 681
  • Yeah, blanked on `concat`'s arguments (would have been `concat [fmap f xs, fs <*> xs]`). – chepner Jul 26 '19 at 16:20
  • `(f:fs) <*> xs = fmap f xs ++ (fs <*> xs) = concat [fmap f xs, fs <*> xs] = concat [fmap f xs | f <- fs] = [f x | f <- fx, x <- xs]` ... (it also means, `[f, g] <*> [x, y] == [f x, f y, g x, g y]` ...) BTW it's interesting, could the transposed version be the canonical...? probably would break some laws maybe... – Will Ness Jul 26 '19 at 16:23
  • @WillNess That's actually the equivalence I meant to add in the comment. On the plus side, I think this answer is running out of things to fix :) – chepner Jul 26 '19 at 16:35