Monoids and Associativity

Introduction

Associativity is a property of a function which has an output equivalent no matter what order the function is applied. Addition and product are examples of mathematical functions that are associative as opposed to subtraction and division which are not. Today’s post will focus on associative functions and their definitions through Monoids in Haskell.

Associative functions

In the introduction to this post, I spoke about associative functions and gave a few examples. Here are those examples again, but demonstrated mathematically.

(5 * 7) * 9 == 5 * (7 * 9)
(5 + 7) + 9 == 5 + (7 + 9)
(5 - 7) - 9 != 5 - (7 - 9)
(5 / 7) / 9 != 5 / (7 / 9)

These examples are pretty straight forward in their reading. You can see clearly that the product and addition operators are associative, subtraction and division not. String concatenation (or array concatenation) is also associative such that:

"Hello " ++ ("World" ++ "!") == ("Hello " ++ "World") ++ "!"

These proofs are pretty straight forward. I think that you should have the idea of what associative functions are by now.

Monoids

Monoids are Haskell’s way of decorating a type that is functionally associative. The definition of a Monoid is as follows.

class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty

You can find more information specifically about the type up on the Haskell Wiki. From the definition above, we can see that there are 3 functions to be defined.

mempty

mempty is the identity value for the monoid. It acts more like a constant rather than a function.

mappend

mappend is the binary function that can be used between two of these typed Monoids.

mconcat

mconcat folds the mappend function between the elements of an array of Monoids.

Monoid Laws

Above, I have gone through the basic principals of associative functions which by-and-large cover off on the laws that a Monoid must abide by. There are some explicit ways of writing this concept, there are as follows.

mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

That’s Monoids for you. Take a look as some example implementations on the Wiki and around the web.

Applying Applicative

Introduction

In a previous post, I had pretty much got the textbook definition down for an Applicative Functor and shown some of its pre-existing uses. Today’s post, I want to walk through some code that I’ve written that implements Applicative.

Put it in context!

Right on! It’s all about context. When making instances of the Functor typeclass, it’s all about defining fmap appropriately to “operate” on the data that sits in a context. What’s a context then? The books and articles that I’ve read use pre-existing types as examples. A list for instance is a context, Either is a context, Maybe is a context. All of these things wrap data. So, let’s make our own context to put something in.

data CustomContext a = CustomContext a
                       deriving (Show)

There’s our context, CustomContext. It just wraps around something .. anything. We can apply a functor instance to this with the following.

instance Functor CustomContext where             
  fmap f (CustomContext x) = CustomContext (f x)

fmap allows a function to get inside the context and operate on the inner data - alright, I’ve said this already. Proof that all of this is working is as follows.

λ> let x = CustomContext 10
λ> x                       
CustomContext 10           
λ> fmap (+5) x             
CustomContext 15           

We wrapped 10 in a context. We applied the function (+5) to the value inside our context. We got back a 15 wrapped in a context. Moving into Applicative territory now, it’s not only the value that we operate on that has the context this time - it’s also the function that we apply. We use the pure function to lift a value inside a context and we use <*> to apply a function to a value (both being inside their respective contexts). Here’s how we’ll define Applicative for our type.

instance Applicative CustomContext where                    
  pure                                = CustomContext      
  CustomContext f <*> CustomContext x = CustomContext (f x)

The implementation of pure is straight forward, we’re just going to pop the value in a CustomContext context. The sequential application function <*> is implemented very much how fmap was implemented, in fact it’s the same. The difference comes in with how the parameters are supplied. We’re taking the function out of the context, we take the value out of the context - we apply the function and wrap the result in the context. Here it is in action.

λ> CustomContext (+5) <*> CustomContext 10
CustomContext 15                          

Also, with the use of pure lifting our values or functions into the context.

λ> pure (+5) <*> CustomContext 10
CustomContext 15                 
λ> CustomContext (+5) <*> pure 10
CustomContext 15                 

Excellent. We’ve done it.

Conclusion

This may not be the most feature-rich example, but it should give you good insight into the implementation and workings of Applicative.

type, newtype & data

Introduction

This post is just a small write up on the differences between these three keywords and their uses within Haskell.

type

Using the type keyword is the same as just referring to the actual type that you’ve declared. In other words, type just lets you make a synonym for the original type.

-- a deck is an array of cards
type Deck = [Card]

-- an array of crows would be a murder
type Murder = [Crow]

Using these, we’ll be able to refer to a Card list as a Deck. They can be used interchangeably as they’ll directly cast. All this really does for us, is gives a pre-existing type a more meaningful name to our code.

newtype

Using the newtype keyword, we make a thin wrapper around an existing type. Something that will be treated differently at compile time, but will be directly translatable (and not subject to conversion) at runtime.

-- declare the data type
newtype Word = Word { getWord :: String }
  derives (Show, Eq)

-- using the data type
let helloWord = Word "Hello"
let byeWord = Word "Bye"
let greetingWord = Word "Hello"

newtype only allows you one constructor and one field. It’s important that its used when you’re creating data entries that have these constraints on them. These attributes make newtype a great candidate for when you just want to add a typeclass instance to an existing type.

data

The data keyword allows you to build much more complex types. With the data keyword, you can have as many constructors and fields as you like.

-- create a person data type
data Person = Person String String Int deriving (Show)
let john = (Person "John" "Smith" 35)

-- create a more complex employee type
data Employee = Employee Int Person deriving (Show)
let john = (Employee 6 (Person "John" "Smith" 35))

Of course, it would make more sense to use “record syntax” when defining these datatypes above.

-- define a person
data Person = Person {firstName :: String
                     ,lastName :: String
                     ,age :: Int} deriving (Show)

-- define an employee
data Employee = Employee {employeeId :: Int
                         ,person :: Person} deriving (Show)

-- define "john"
let john = Employee {employeeId = 6
                    ,person = (Person {firstName = "John"
                                      ,lastName = "Smith"
                                      , age = 35}) 
                    }

Wrapping up

• Use type to give your types more meaningful names
• Use newtype if you just want to take an existing type and add a typeclass instance to it
• Use data if you want to create your own datatype

Applicative Functors in Haskell

Introduction

As a follow up to my previous post on Functors, it’s a natural progression for me to do a post on the more advanced version, the Applicative Functor. In a normal functor, you’ll map a function over a functor and applicative functor is a reverse view of this where it’ll allow you to map many functor values over a single function.

What is an Applicative Functor?

At the code level, an Applicative Functor is any type that is in instance of the Applicative typeclass. At a concept level, the Applicative Functor has not only the values in “a context” but also the function that we’ll apply is in a context. This differs from just a normal Functor where it’s only the value that’s wrapped in a context. An Applicative Functor has 2 functions that require implementation. pure and <*>. This typeclass and functions are defined as follows.

class (Functor f) => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

The definition for pure on Hoogle suggests that it will

Lift a value

“Lifting” is very well described in articles all over the web. Here’s the Haskell Wiki’s article on Lifting. pure takes in a value and returns an applicative value around that value. It’s actually quite a simple definition when you read it. The other function defined here is <*>. The definition for <*> on Hoolgle suggests that it will perform

Sequential application

The definition of sequential application here can be expanded such that <*> takes a function (a -> b) wrapped up in a functor f and another functor value f a. It’ll extract the function from the first parameter (a -> b), map it over the functor value f a to produce a result f b. The concept is very similar to what we’ve seen before in mapping scenarios, it’s just that we “map” with different “things”. Today we’re mapping with functor values over a function.

pure

Here’s some examples of pure in action. You’ll see that when we’re casting to a type, we receive the appropriate value back

> pure "Hey" :: Maybe String
Just "Hey"
> pure "Should be in a List" :: [String]
["Should be in a List"]

You can see here that the value is “lifted” by pure into the container (in this case either a Maybe or a List).

<*>

For the next set of examples, I’ll show you some usages of <*>. You’ll need to keep in the front of your mind that all functions on the left hand side are applied to all values on the right hand side, so we end up with a Cartesian effect.

> [sin, cos, tan] <*> [pi, pi, pi]
[1.2246467991473532e-16,1.2246467991473532e-16,1.2246467991473532e-16,-1.0,-1.0,-1.0,-1.2246467991473532e-16,-1.2246467991473532e-16,-1.2246467991473532e-16]

The <*> function is left associable, so when you start chaining calls together it’s the leftmost that is evaluated first.

> [(+),(*)] <*> [1,2] <*> [3,4]
[4,5,5,6,3,4,6,8]

(which is really)
[1+3,1+4,2+3,2+4,1*3,1*4,2*3,2*4]

Applicative Style

You can see how using this “applicative style” in code can often be swapped 1-for-1 with list comprehensions as you achieve the same permuted or Cartesian effect. Take this for example.

> [salutation ++ name | salutation <- ["Hello ", "Goodbye ", "Yo! "], name <- ["John", "Mary", "Anne"]]
["Hello John","Hello Mary","Hello Anne","Goodbye John","Goodbye Mary","Goodbye Anne","Yo! John","Yo! Mary","Yo! Anne"]

> (++) <$> ["Hello ", "GoodBye ", "Yo! "] <*> ["John", "Mary", "Anne"]
["Hello John","Hello Mary","Hello Anne","Goodbye John","Goodbye Mary","Goodbye Anne","Yo! John","Yo! Mary","Yo! Anne"]

You can see that when dealing with lists, the following is true:

pure f <*>; xs == fmap f xs

In this context, pure f is putting f into a list. [f] <*> xs just applies each function in the left list to the right. Another implementation of the Applicative Functor that doesn’t follow the same notion of a List is its use with IO. The idea of the applicative functor still holds, but when dealing with IO its the actions that are operated on. This can be thought of in the same way as sequencing and mapping in one.

ZipList

Another type that is an instance of Applicative is the ZipList. The ZipList type is defined as follows.

instance Applicative ZipList where
  pure x = ZipList (repeat x)
  ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

When we use applicative style on a normal list, we end up with a Cartesian product of the two lists involved. A ZipList differs here by operating on indicies in either list that are the same. Index [0] on the left gets applied to Index [0] on the right. Index [1] on the left gets applied to Index [1] on the right, and so on.

Applicative Functor Laws

Finally, there are a few laws that applicative functors must abide by, they are as follows.

• pure id <*> v = v
• pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
• pure f <*> pure x = pure (f x)
• u <> pure y = pure ($ y) <> u

Applying applicative functors for yourself

This has been a very difficult topic that I’ve burnt some time on as late. There are plenty of examples of how this knowledge has been applied for a List or Maybe, but I’ve struggled to apply this to a type of my own. So far though, I’ve come across this article on Applicative Functors on the Hakell Wiki and most notably this sentence:

Anytime you feel the need to define different higher order functions to accommodate for function-arguments with a different number of arguments, think about how defining a proper instance of Applicative can make your life easier.

That to me makes sense. So, if you have a function that operates on a particular type and you’d like to apply that function to “n” arguments - you’d normally create an fmap clone that would cater for that many arguments. Using an applicative functor, the re-creation of the fmap instance goes away as your higher-order function can expect any number of arguments. Because of this, the following is true.

fmap2 f a b = f `fmap` a <*> b
fmap3 f a b c = f `fmap` a <*> b <*> c
fmap4 f a b c d = f `fmap` a <*> b <*> c <*> d

That’s it for today’s post. I hope to update this post with some more examples and information as I discover it!

Functors in Haskell

Introduction

In a previous post, I had lightly grazed the surface of the topic of Functors in Haskell and I thought it was time to come back and be a little more comprehensive about it. Without further ado, let’s talk about Functors.

What is a Functor?

At the code level, a Functor is any type that is an instance of the Functor typeclass. At a concept level, a Functor is something that can be mapped over. As soon as anyone says something like this to me I immediately start thinking of any enumerated type (array, list, vector, etc) and this is right.

A Functor only needs to implement 1 function, fmap. How this looks in Haskell is as follows.

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Reading this gets to be a mouthful, but bear with me. This definition says: “for my first parameter, I want a function that takes an a type and returns a b; for my second parameter, I want an a value wrapped by this functor and I will return you a b value wrapped by this functor”. I’ve tried to place emphasis on a’s and b’s in that previous sentence, otherwise it reads like rather difficult english. Applying this knowledge to a living-breathing example, I’ll show you the Maybe type.

instance Functor Maybe where
  fmap f (Just x) = Just (f x)
  fmap _ Nothing  = Nothing

Looking at this we can see that when a Just value comes through, it’s the value (wrapped in the Just) that has the function applied to it. When nothing comes through, we don’t care for the function - we know that the return is going to be Nothing. The important thing to note here is that it’s the value (wrapped in the Just) that’s being operated on. Seeing this in action always helps an explanation.

ghci> fmap (replicate 3) (Just 4)
Just [4, 4, 4]

The way that I read this is: “A function” fmap “that takes a function” (replicate 3) “and a functor value” (Just 4) “that then maps that function” (replicate 3) “over the inner value” (4) “which gets wrapped up in the functor” (Just). This is the best way that I could think of to structure this sentence. It makes sense to me, I hope it helps you also. Again, the important thing to remember is that it’s the inner-value that’s getting processed which is why we ended up with Just [4, 4, 4] rather than [Just 4, Just 4, Just 4]. Finally, when you’re implementing functors of your own there are laws that must be met.

Law #1

Mapping the id function over any functor value should produce the functor value that we supplied.

fmap id = id

Law #2

Mapping two composed functions over a functor value should be the same as functionally composing those two functions.

fmap (f . g) = fmap f . fmap g

This second law makes sense once you think about performing fmap over a function, as it’s just the same as function composition.

fmap (*15) (-2) == (*15) . (-2)

This post should arm you sufficiently to start inflicting your own Functors on the world.