CODEWITHSUNDEEP
haskell
maxloo
maxloo

Reputation: 491

Haskell quickBatch: Ap applicative monoid

Based on the suggestion provided at ZipList Monoid haskell, I have created this code which works:

newtype Ap f a = Ap { getAp :: f a }
  deriving (Eq, Show)
instance (Applicative f, Semigroup a) =>
  Semigroup (Ap f a) where
    Ap xs <> Ap ys = 
      Ap $ liftA2 (<>) xs ys
instance (Applicative f, Monoid a) => 
  Monoid (Ap f a) where
    mempty = Ap $ pure mempty
    Ap xs `mappend` Ap ys = 
      Ap $ liftA2 mappend xs ys
app :: Ap ZipList (Sum Int)
app = Ap (ZipList [1,2 :: Sum Int])
instance Arbitrary (f a) =>
  Arbitrary (Ap f a) where
    arbitrary = Ap <$> arbitrary 
instance Eq a => EqProp (Ap ZipList a) where
  xs =-= ys = xs' `eq` ys' where 
    xs' = 
      let (Ap (ZipList l)) = xs
        in take 3000 l
    ys' = 
      let l = (getZipList . getAp) ys
        in take 3000 l
main :: IO ()
main = do
  quickBatch $ monoid app

However, I do not fully understand how the code works. Why is it mempty = Ap $ pure mempty? How is this equation calculated or derived? Why is it Ap xs 'mappend' Ap ys? I would have thought that since it is Monoid (Ap f a), it should be Ap f xs 'mappend' Ap f ys?

And why is it that when the quickBatch monoid tests are run on Ap, it doesn't result in stackoverflow at the mconcat test as seen at Haskell quickBatch: Testing ZipList Monoid at mconcat results in stack overflow?

Upvotes: 1

Views: 194

Answers (2)

DDub
DDub

Reputation: 3924

Why is it mempty = Ap $ pure mempty? How is this equation calculated or derived? Why is it Ap xs 'mappend' Ap ys? I would have thought that since it is Monoid (Ap f a), it should be Ap f xs 'mappend' Ap f ys?

In order to answer these questions, it will be important to take a careful look at the definition of Ap itself:

newtype Ap f a = Ap { getAp :: f a }

This declaration introduces both a new type Ap and a new constructor Ap—they have the same name but they are definitely different entities.

The type Ap has kind (Type -> Type) -> Type -> Type, which is to say that it takes two arguments: f, which itself is a function on types, and a, which is just a type. We can use the type Ap in type signatures, when we write things like app :: Ap ZipList (Sum Int) or in class instances like instance Eq a => EqProp (Ap ZipList a).

The constructor Ap has type f a -> Ap f a (note the use of the type version of Ap here!). This constructor takes one argument, a value of type f a, in order to produce a value of type Ap f a. So, for instance, you can write:

t1 :: Ap Maybe Int
t1 = Ap (Just 3)

t2 :: Ap [] Bool
t2 = Ap [True, False]

t3 :: Ap ZipList Int
t3 = Ap (ZipList [1,2,3])

Notice that in every case, the type Ap takes two arguments, but the constructor Ap takes one argument.

Now, let's consider how to write the Monoid instance for Ap f a. Let's recall the Monoid class:

class Semigroup a => Monoid a where
  mempty  :: a
  mappend :: a -> a -> a

So, for instance (Applicative f, Monoid a) => Monoid (Ap f a), we'll need mempty :: Ap f a and mappend :: Ap f a -> Ap f a -> Ap f a. How can we write mempty? Well, first off, we need a value of type Ap f a, and the only way we've seen so far for how to make one is with the Ap constructor. Recalling the Ap constructor, that means we need a value of type f a that we can feed to it. How can we produce one of those? Fortunately, we know Monoid a, so we have access to mempty :: a, and we know Applicative f, so we have access to pure :: forall x. x -> f x. Sticking these two together, we can make a value pure mempty :: f a. All that's left is to provide that to the Ap constructor:

  mempty = Ap $ pure mempty

Next, we need to define mappend. We're given two values of type Ap f a, which means they must be of the form Ap x for some values x (remember that the Ap in Ap x here is the constructor, not the type). So, we begin by pattern matching:

  Ap xs `mappend` Ap ys = ...

What types do xs and ys have? Well, Ap xs :: Ap f a, and Ap :: f a -> Ap f a, so xs, ys :: f a. We need to somehow combine these two values of type f a into a single value of type f a, and then we can use the Ap constructor to wrap it up for output. We can do this with liftA2 mappend xs ys. This gives us:

  Ap xs `mappend` Ap ys = Ap $ liftA2 mappend xs ys

As a note here, check out how it wouldn't make sense to write something like:

  Ap f xs `mappend` Ap g ys` = -- pattern error!

because we'd be mixing up the type Ap, which takes two arguments, with the constructor Ap, which takes only one.

And why is it that when the quickBatch monoid tests are run on Ap, it doesn't result in stackoverflow at the mconcat test

The stack overflow is the result of trying to compare two infinite lists for equality. GHC will just keep checking each element looking for either the end of the list or for two elements that aren't equal, and since the lists are infinitely long, the program won't terminate (or will run out of memory).

However, in your definition of EqProp for Ap ZipList a, you're basically saying that it's okay to only check the first 3000 elements of a list for equality. So, even if infinite lists are encountered, as long as the first 3000 elements are equal, we can just go ahead and assume that the lists are equal.

Upvotes: 1

leftaroundabout
leftaroundabout

Reputation: 120711

It is in fact the only possible definition (except ⊥).

  • Knowing nothing more about the monoid, the only expressions you can write are of the form mempty <> mempty <> ... <> mempty, which is just mempty by monoid laws.
  • Knowing nothing more about the applicative, only expressions you can write are of the form f <$> pure y <*> pure z <*> ..., which is the same as pure $ f y z ... where f is some n-ary function on the monoid – which again can only have the form \y' z' ... -> y' <> mempty <> ... <> z' <> mempty, and also y and z can only be mempty.

So, whatever expression you could possibly write, it'll always be identical to pure mempty, provided the monoid and applicative you put in are law-abiding.

Upvotes: 1

Related Questions