Marty Stumpf
10 Nov 2022
•
7 min read
This is the first of a series of articles that deep dives a few very powerful type classes that every functional programmer should know. For example,Monoid
, Functor
, Applicative
, etc. These are indeed so functional that they are prevalent in Haskell production code. We explain them with examples in Haskell
. This series assumes the audience is familiar with some functional programming concepts we went through in the last series including higher order functions and types and typeclasses.
I'll first give an overview of the class of typeclasses that will be covered in this series. Then, we will go through a very universal typeclass: Semigroup
.
Recall that typeclasses are categories of types, and so the instances of a class are types (not values)! A typeclass definition consists of:
As I go through more typeclasses I first introduce their methods and laws and what these empower us to do.
Let's look at the Num
typeclass in Haskell as an example:
These operations are defined for the Num
typeclass:
(+)
addition:
(+) :: a -> a -> a
infixl 6(-)
subtraction:
(-) :: a -> a -> a
infixl 6(*)
multiplication:
(*) :: a -> a -> a
infixl 7abs
get the absolute value:
abs :: a -> a
signum
get the sign of a number:
signum :: a -> a
signum
is either -1 (negative), 0 (zero), or 1 (positive).fromInteger
getting an a
from an Integer
:
fromInteger :: Integer -> a
negate
negation:
negate :: a -> a
That is, for any type that belongs to the Num
class, we are able to perform addition, subtraction, etc on them. For example, since Int is an instance of Num
, we know we can perform these operations on any Int
.
For all typeclasses, the defined methods must satisfy certain laws. Associativity and Commutativity are common laws for typeclasses.
For example, for the Num
typeclass (the Haskell Report defines no laws for Num
. However, (+)
and (*)
are customarily expected to have the following properties):
Associativity of (+)
(x + y) + z = x + (y + z)
Commutativity of (+)
x + y = y + x
Typeclasses like Num
has simple types like Integer
or Natural
(natural numbers) in it but the typeclasses we'll focus on in this series specify more generic methods. Therefore, these typeclasses have instances of mostly type families in them. That is, the instances are type constructors. They take at least one type argument to form a type. For example, some of the instances of the Semigroup typeclass include:
Semigroup [a]
Semigroup (Either a b)
That is, [Int]
, [Bool]
(from the List
type family) and Either Int Bool
, Either Char Int
(from the Either
type family) etc are all Semigroup
instances!
The typeclasses we'll cover are related, as depicted from the below graph from Typeclassopedia:
Foo
to Bar
it means that every Bar
is a Foo
.We'll start from the middle: Semigroup
. We'll then look at Monoid
. As you can see from the graph, all Monoid
instances are Semigroup
instances. Next, we'll look at Foldable
and Traversable
. Finally, Functor
, which will build up to Applicative
. Then Alternative
and Monad
. All these are very common typeclasses.
Looking at the reference for Semigroup
, you will see that there's only one method, <>
, sometimes called append
:
(<>) :: a -> a -> a
In a nutshell, if a type is an instance of the Semigroup
we know that we can apply the <>
operator to two values.
The function (<>)
has to satisfy associativity. I.e., the following has to hold for <>
:
x <> (y <> z) = (x <> y) <> z
And that's it! For example, List
is an instance of Semigroup
because the append
function ((++)
) is associative:
(++) :: [a] -> [a] -> [a]
Because we know that:
[1,2] ++ ([3,4] ++ [5,6])
= [1,2,3,4,5,6]
= ([1,2] ++ [3,4]) ++ [5,6]
Because list
's (++)
satisfies the requirement for Semigroup
, it is an instance of Semigroup
.
This also means that you can use <>
on lists to append lists. We can see this in GHCi:
Prelude> [1,2] <> ([3,4] <> [5,6])
[1,2,3,4,5,6]
In production code, it is not uncommon to preferentially use the more general <>
to the datatype specific operators. It's good to get used to seeing them!
Semigroup
sIn this section we study some notable Semigroup
s and how the operator <>
behaves with GHCi.
As from hackage: the Either
type represents values with two possibilities: a value of type Either a b
is either Left a
or Right b
.
data Either a b
The Either type is sometimes used to represent a value which is either correct or an error; by convention, the Left constructor is used to hold an error value and the Right constructor is used to hold a correct value (mnemonic: "right" also means "correct").
Since Either
is an instance of Semigroup
, we know we can use the <>
operator on them. Trying it in GHCi:
Prelude> import Data.Either
Prelude Data.Either> Right 1 <> Right 2 <> Left ()
Right 1
Prelude Data.Either> Left () <> Right 1 <> Right 2
Right 1
Prelude Data.Either> Left 1 <> Left 2 <> Right 3
Right 3
Prelude Data.Either> Left 1 <> Left 2 <> Left 3 <> Left 4
Left 4
Notice that <>
in Either
returns the first Right
and if there is no Right
, returns the last Left
. The name "append" doesn't really work well for the <>
operator here!
Let's look at the Maybe semigroup
:
data Maybe a
= Nothing
| Just a
The
Maybe
type encapsulates an optional value. A value of typeMaybe a
either contains a value of typea
(represented asJust a
), or it is empty (represented asNothing
).
Maybe
is listed as an instance of Semigroup
like this in hackage (in the "instances" section of either Maybe
or Semigroup
):
Semigroup a => Semigroup (Maybe a)
That is, we need the type variable a
to be a Semigroup
instance for a Maybe a
to be a Semigroup
instance!
Let's see what <>
does with Maybe String
:
Prelude> import Data.Maybe
Prelude Data.Maybe> Just " is awesome" <> Nothing
Just " is awesome"
Prelude Data.Maybe> Just "Haskell" <> Just " is awesome" <> Nothing
Just "Haskell is awesome"
Prelude Data.Maybe> Nothing <> Just "Haskell" <> Just " is awesome"
Just "Haskell is awesome"
Prelude Data.Maybe> Just "Haskell" <> Nothing <> Just " is awesome"
Just "Haskell is awesome"
<>
appends the strings, ignoring any Nothing
. This makes sense because type String = [Char]
and we know that [a]
is an instance of Semigroup
.
()
is also an instance of Semigroup
, so it just works in GHCi:
Prelude Data.Maybe> Just () <> Just ()
Just ()
Prelude Data.Maybe> Just () <> Just () <> Nothing
Just ()
What about Maybe Integer
? We get some errors in GHCi:
Prelude Data.Maybe> (Just 1::Maybe Integer) <> Just 2
<interactive>:3:1: error:
• No instance for (Semigroup Integer) arising from a use of ‘<>’
• In the expression: (Just 1 :: Maybe Integer) <> Just 2
In an equation for ‘it’: it = (Just 1 :: Maybe Integer) <> Just 2
This is because Integer
is not an instance of Semigroup
! That is, the compiler doesn't know how to apply the <>
operator on Integer
!
To fix that, we can tell the compiler how to apply the <>
operator on Integer
or any Num
type. As listed on Semigroup's hackage, for the Num
class, its Semigroup
instances are via either Sum or Product from Data.Monoid (in the "Num
wrappers" section):
Num a => Semigroup (Product a)
Num a => Semigroup (Sum a)
If we specify the type to be a Product a
, then the GHCi should know to <>
them by multiplication:
Prelude Data.Maybe> import Data.Monoid
Prelude Data.Maybe Data.Monoid> (Just 1::Maybe (Product Integer)) <> Just 2
Just (Product {getProduct = 2})
Prelude Data.Maybe Data.Monoid> (Just 1::Maybe (Product Integer)) <> Just 2 <> Just 3 <> Nothing
Just (Product {getProduct = 6})
Try it out with Sum
!
The NonEmpty
data family is a list that has at least one element in it.
data NonEmpty a
We construct it by using the :|
constructor, and specifying the first element before the :|
constructor - this ensures that it won't be an empty list. <>
works the same on NonEmpty
as on List
:
Prelude> import Data.List.NonEmpty
Prelude Data.List.NonEmpty> (1 :| [2,3]) <> (4 :| [])
1 :| [2,3,4]
Note that the type argument need not be a simple type for any of these! For example, we can have a NonEmpty (Either [Int] Bool)
and <>
will still work, as long as the typeclass requirements are fulfilled:
Prelude> import Data.Either
Prelude Data.Either> import Data.List.NonEmpty
Prelude Data.Either Data.List.NonEmpty> (Right [1,2] :| [Left False, Right [3]]) <> (Left True :| [Right []])
Right [1,2] :| [Left False,Right [3],Left True,Right []]
There are many other Semigroup
instances that are not mentioned here and I encourage you to try them out in GHCi!
This concludes this post. You now know what the <>
operator is, and what it does in some common Semigroup
s. In the next post, we'll learn about Monoid
. Stay tuned!
Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.
See other articles by Marty
Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ
108 E 16th Street, New York, NY 10003
Join over 111,000 others and get access to exclusive content, job opportunities and more!