Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Understanding Data.Functor.Constant constructor and applicative laws

I'm confused about Data.Functor.Constant's type constructor and also how it works with applicative.


First the constructor:

When I examine the type of Constant :: a -> Constant a b

I see it takes an a, but returns a Constant a b

Where does the b come from and why does it exist?


Secondly, I'm struggling with Applicative:

I understand Constant needs to have a Monoid inside to be an Applicative instance.

A law it must obey is: pure id <*> Constant x = x

I thought that was the same as: Constant id <*> Constant x = x

but I guess I'm wrong about that since the follow code clearly shows pure acts differently.

:t pure id <*> Constant "hello" // Constant [Char] b

:t Constant id <*> Constant "hello" // Couldn't match expected type `a0 -> a0' with actual type `[Char]'

:t pure id <*> Constant reverse //  Constant ([a] -> [a]) b

:t Constant id <*> Constant reverse // Constant ([a] -> [a]) b

I see that it only works if x is the same monoid unless I use pure. So I'm not sure why pure is working differently. I suspect this has to do with that b which is why they're in the same question.

To sum up the two questions:

  1. What does b do in the Constant constructor?

  2. Why does pure work even though the monoids are different inside?

Thanks so much!

like image 382
Brian Avatar asked Jan 16 '14 18:01

Brian


People also ask

What is an applicative functor in Haskell?

In Haskell, an applicative is a parametrized type that we think of as being a container for data of that type plus two methods pure and <*> . Consider a parametrized type f a . The pure method for an applicative of type f has type. pure :: a -> f a. and can be thought of as bringing values into the applicative.

Why is functor useful?

Functor is also important in its role as a superclass of Applicative and of Traversable . When working with these more powerful abstractions, it's often very useful to reach for the fmap method. Show activity on this post. For example, it's possible to derive the function lift in a way that works for any functor.

How are functions functors?

In functional programming, a functor is a design pattern inspired by the definition from category theory, that allows for a generic type to apply a function inside without changing the structure of the generic type. Simple examples of this are Option and collection types.

How does Fmap work Haskell?

Here's how it works. fmap takes an a -> b function and an f a data type ( a wrapped in any context f ). The function is applied to what's inside the context, and a value of type b wrapped in f is returned. The value can change, but the context remains the same.


1 Answers

Okay, so you have this type

data Const a b = Const { getConst :: a }

Your first question was "Where does the b come from?"

The answer is that it doesn't come from anywhere. In the same way that you can think of Maybe b as a container that holds either 0 or 1 values of type b, a Const a b is a container that holds exactly 0 values of type b (but does definitely hold a value of type a).

Your second question was "Why is it there?"

Well, sometimes it's useful to have a functor that says it might contain values of type b, but actually holds something else (e.g. think of the Either a b functor -- the difference is that Either a b might hold a value of type b, whereas Const a b definitely doesn't).

Then you asked about the code snippets pure id <*> Const "hello" and Const id <*> Const "hello". You thought that these were the same, but they're not. The reason is that the Applicative instance for Const looks like

instance Monoid m => Applicative (Const m) where
  -- pure :: a -> Const m a
  pure _ = Const mempty

  -- <*> :: Const m (a -> b) -> Const m a -> Const m b
  Const m1 <*> Const m2 = Const (m1 <> m2)

Since there aren't actually any values having the type of the second parameter, we only have to deal with those having the type of the first parameter, which we know is a monoid. That's why we can make Const an instance of Applicative -- we need to pull a value of type m from somewhere, and the Monoid instance gives us a way to make one from nowhere (using mempty).

So what happens in your examples? You have pure id <*> Const "hello" which must have type Const String a since id :: a -> a. The monoid in this case is String. We have mempty = "" for a String, and (<>) = (++). So you end up with

pure id <*> Const "hello" = Const "" <*> Const "hello"
                          = Const ("" <> "hello")
                          = Const ("" ++ "hello")
                          = Const "hello"

On the other hand, when you write Const id <*> Const "hello" the left-hand argument has type Const (a -> a) b and the right has type Const String b and you see that the types don't match, which is why you get a type error.

Now, why is this ever useful? One application is in the lens library, which lets you use getters and setters (familiar from imperative programming) in a pure functional setting. A simple definition of a lens is

type Lens b a = forall f. Functor f => (a -> f a) -> (b -> f b)

i.e. if you give it a function that transforms values of type a, it will give you back a function that transforms values of type b. What is that useful for? Well, let's pick a random function of type a -> f a for a particular functor f. If we choose the Identity functor, which looks like

data Identity a = Identity { getIdentity :: a }

then if l is a lens, the definition

modify :: Lens b a -> (a -> a) -> (b -> b)
modify l f = runIdentity . l (Identity . f)

provides you with a way to take functions that transform as and turn them into functions that transform bs.

Another function of type a -> f a we could pass in is Const :: a -> Const a a (notice that we've specialized so that the second type is the same as the first). Then the action of the lens l is to turn it into a function of type b -> Const a b, which tells us that it might contain a b, but actually sneakily it really contains an a! Once we've applied it to something of type b in order to get a Const a b, we can hit it with getConst :: Const a b -> a to pull a value of type a out of the hat. So this gives us a way to extract values of type a from a b -- i.e it's a getter. The definition looks like

get :: Lens b a -> b -> a
get l = getConst . l Const

As an example of a lens, you could define

first :: Lens (a,b) a
first f (a,b) = fmap (\x -> (x,b)) (f a)

so that you could open up a GHCI session and write

>> get first (1,2)
1
>> modify first (*2) (3,4)
(6,4)

which, as you might imagine, is useful in all kinds of situations.

like image 61
Chris Taylor Avatar answered Oct 22 '22 10:10

Chris Taylor