Applicative in Haskell for single variable

Question

I recently started learning Haskell and encountered a problem with the idea of Applicative.

I need to make an implementation for

newtype MyTriple a = MyTriple (a,a,a) deriving Show

as Applicative instance.

I cannot really understand how exactly am i supposed to do that. As far as i know applicative is mostly used with more than one variable. In this particular example im not sure what should be in that part with <*> symbol. Can someone please explain this to me (based on my example or not)? If it is possible please dont provide a direct answer.

Answer 1

When writing an instance of a type class in Haskell, there are two things that can guide us to the correct implementation: types and type class laws.

What does the type say?

One remarkable property of the type system used in Haskell (and some other functional languages as well) is that given a sufficiently polymorphic function type, there are surprisingly few ways it can be implemented. The intuition is that since a polymorphic function knows nothing about the types it operates on, there are no interesting operations it can apply to values of these types.

The simplest example is a function of type a -> a. It must produce a value of type a as its output; how can it come up with one? Since Haskell doesn't provide a way to conjure a value of arbitrary type out of thin air¹, the function must use its input value of type a. What can it do with it? Since it's a value of an arbitrary type, the answer is "nothing" - it can only return it as its result. Thus, the only reasonable function of type a -> a is the identity function. A more thorough explanation of this idea and further examples can be found in a famous paper by P. Wadler.

Let's go back to the example at hand. The types of pure and <*> in the Applicative instance for MyTriple are

pure  :: a -> MyTriple a
(&lt*>) :: MyTriple (a -> b) &lt*> MyTriple a -> MyTriple b

In pure, to construct MyTriple a, we need a triple of values of type a. Since we are given one value of type a and we have no way of producing any other (just like in the a -> a function), the only way to implement it is as

pure x = MyTriple (x, x, x)

Operator <*> is more interesting. In this case:

MyTriple (f, g, h) &lt*> MyTriple (x, y, z) = ...
-- f, g, h :: a -> b
-- x, y, z :: a

we are given three functions of type a -> b and three values of type a. To construct MyTriple b, we need three values of type b. The only way to get our hands on the value of type b is to apply one of f, g, h to one of x, y, z. There is no unique way to do this; we can pair up the functions and their arguments in an arbitrary fashion. It follows that all the possible implementations of <*> for MyTriple are of the form

MyTriple (f1, f2, f3) &lt*&gt MyTriple (x1, x1, x3) = MyTriple (fi xp, fj xq, fk xr)

for some values of i, j, k and p, q, r between 1 and 3. From the point of view of the type system, all these are correct. In general, there may be multiple valid instances of applicative functor for a given type (e.g. list has two: the regular one and ZipList), so it's not necessarily a problem. That being said, there is one more thing we need to consider.

Applicative functor laws

The applicative functor laws are the following rules:

• Identity: pure id <*> v = v
• Composition: pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
• Homomorphism: pure f <*> pure x = pure (f x)
• Interchange: u <*> pure y = pure ($y) <*> u

A valid instance of the applicative functor must satisfy all these equations. Note that it is not enforced by the compiler - this responsibility lies with the programmer.

At this point, we need to figure out what additional constraints do the applicative functor laws put on the implementation of operator <*> for MyTriple. Let's start with the Identity. Using our definitions of pure and <*>, the identity law requires that

MyTriple (x1, x1, x3) = MyTriple (id xp, id xq, id xr) = MyTriple (xp, xq, xr)

The only way for this to hold for all possible values of x's is if p = 1, q = 2 and r = 3. This narrows down the set of possible definitions of <*> to

MyTriple (f1, f2, f3) &lt*&gt MyTriple (x1, x1, x3) = MyTriple (fi x1, fj x2, fk x3)

so the components of the right argument of <*> cannot be permuted.

What about the left argument? The answer to that question is given by the interchange law. We have

MyTriple (f1, f2, f3) &lt*&gt pure x = MyTriple (fi x, fj x, fk x)

and by the interchange law this must be equal to

pure ($x) &lt*&gt MyTriple (f1, f2, f3) = MyTriple (fp x, fq x, fr x)

since in this case f functions assume the role of arguments of $x, that is ($x) f = f x. Combining these two, we see that

MyTriple (fi x, fj x, fk x) = MyTriple (fp x, fq x, fr x)

and again, the only way for this to hold regardless of f's and x is if i = p, j = q and k = r, so i = 1, j = 2, k = 3. The final version of operator <*>, the only one satisfying the applicative functor laws², is thus the simplest and most natural one:

MyTriple (f1, f2, f3) &lt*&gt MyTriple (x1, x1, x3) = MyTriple (f1 x1, f2 x2, f3 x3)

---

¹ Apart from undefined & co.

² Strictly speaking, we need to check the remaining two laws (composition and homomorphism) before we are done

Answer 2

I think in terms of liftA2 rather than (<*>). (<*>) is lifted function application

(<*>) = liftA2 ($)

For your type, the applicative performs "element-wise" lifting, meaning n-th element in your result is the combination of the incoming n-th element

type V3 :: Type -> Type
data V3 a = V3 a a a
  deriving
  stock Functor

instance Applicative V3 where
 pure :: forall a. a -> V3 a
 pure a = V3 a a a

 liftA2 :: forall a b c. (a -> b -> c) -> (V3 a -> V3 b -> V3 c)
 liftA2 (·) (V3 a1 a2 a3)
            (V3 b1 b2 b3)
          = (V3 c1 c2 c3)
  where

  c1, c2, c3 :: c
  c1 = a1 · b1
  c2 = a2 · b2
  c3 = a3 · b3

Lists of a given length (vectors) are isomorphic to functions

Vec 0 a = (Void  -> a)
Vec 1 a = (()    -> a)
Vec 2 a = (Bool  -> a)
Vec 3 a = (Fin3  -> a)
..
Vec n a = (Fin n -> a)

and their applicative instance follows the element-wise function definition. Functors like MyTriple and others isomorphic to functions (.. ->) are called Representable functors.

instance Applicative ((->) a) where
 pure :: b -> (a -> b)
 pure = const

 liftA2 :: (b1 -> b2 -> b3) -> ((a->b1) -> (a->b2) -> (a->b3))
 (liftA2 (·) bs1 bs2) a = 
   bs1 a · bs2 a

Verify that (->) Fin3 is isomorphic to V3/MyTriple with the same Applicative instance.

Consider what happens when (·) is instantiated with ($).

---

With base 4.17 you can use Generically1 (from GHC.Generics) to derive Applicative:

type V3 :: Type -> Type
data V3 a = V3 a a a
  deriving
  stock (Functor, Generic1)

  deriving Applicative
  via Generically1 V3

---

You can derive Applicative and Monad for any Representable functor via Co V3

type V3 :: Type -> Type
data V3 a = V3 a a a
 deriving (Functor, Applicative, Monad)
 via Co V3

instance Distributive V3 where
 distribute :: Functor f => f (V3 a) -> V3 (f a)
 distribute = distributeRep

type Fin3 :: Type
data Fin3 = Fin0 | Fin1 | Fin2

instance Representable V3 where
 type Rep V3 = Fin3

 index :: V3 a -> (Fin3 -> a)
 index (V3 a b c) = \case
  Fin0 -> a
  Fin1 -> b
  Fin2 -> c

 tabulate :: (Fin3 -> a) -> V3 a
 tabulate make = V3 (make Fin0) (make Fin1) (make Fin2)

We would derive Distributive if it weren't for "role" problems, i.e. we cannot coerce under the argument of the functor f.

Answer 3

I'm going to assume that you're not having problem with pure.

You can play around with MyTriple and <*> in GHCi to get a better sense for what you're supposed to do. For example, you can ask about the type of <*> if you constrain the return type to MyTriple _:

*Q65326400> :t (<*>) :: _ -> _ -> MyTriple _

<interactive>:1:10: error:
    * Found type wildcard `_' standing for `MyTriple (a1 -> w1)'
      Where: `a1', `w1' are rigid type variables bound by
               the inferred type of
                 <expression> :: MyTriple (a1 -> w1) -> MyTriple a1 -> MyTriple w1
               at <interactive>:1:10-29
      To use the inferred type, enable PartialTypeSignatures
    * In an expression type signature: _ -> _ -> MyTriple _
      In the expression: (<*>) :: _ -> _ -> MyTriple _

...

(More, similar, error messages follow...)

This looks scary, but it actually tells you what the involved types are supposed to be:

MyTriple (a1 -> w1) -> MyTriple a1 -> MyTriple w1

or, if we translate to more 'friendly' type variables:

MyTriple (a -> b) -> MyTriple a -> MyTriple b

So, as @Nearoo has pointed out in the comments, the left-hand side of <*> should be a MyTriple value that contains functions of the type a -> b. These can be three different functions, but they must have compatible types.

The right-hand side should be a MyTriple a, and the return value a MyTriple b.

You could, for example, implement an Applicative instance that behaves like this:

*Q65326400> MyTriple (null, odd . length, elem 'f') <*> MyTriple ("foo", "bar", "baz")
MyTriple (False,True,False)

The left-hand side is a MyTriple (String -> Bool) value, and the right-hand side is a MyTriple String.

This isn't the only possible Applicative instance. I can easily think of a dozen more instances, but they probably wouldn't all be lawful.

The next step, once you've figured out how to implement an instance, is to convince yourself (and possibly others) that the instance obeys the applicative functor laws. That's going to rule out some of those technically possible instances.