NOTE: Apologies for formatting errors, this was meant for a blog which I no longer contribute to.
Making Our Own Types and Typeclasses
This is a concise tutorial based on the popular book from Miran Lipovača located at learnyouahaskell.com, thanks to him for permission to write this derivation. Minus the terminology, this tutorial assumes you will understand most everything up until the section on type signatures, and references are listed at the bottom of the page and linked to when detail might be useful.
Haskell is a lazy, purely functional programming language with static and strong typing. Its code is often considered elegant, terse, and mind bending in a great way. Given that programmers can benefit from thinking about languages and the various methods for abstracting and combinining expressions, learning Haskell should be a beneficial exercise.
To get started, visit haskell.org/platform to download everything you need, or use a package manager of choice to grab the platform.
GHCi is the interpreter which comes with the Haskell Platform. Just type ghci in a shell to get a feel for the language.
$ ghci
GHCi, version 7.4.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> 2 + 15
17
You can change the text before the prompt by typing in the following into the interpreter:
:set prompt "ghci> "
Let's add a number to a string!
ghci> 5 + "llama"
And the results: no llama for you!
No instance for (Num [Char])
arising from a use of `+' at <interactive>:1:0-9
Possible fix: add an instance declaration for (Num [Char])
In the expression: 5 + "llama"
In the definition of `it': it = 5 + "llama"
This error from the interpeter lets us know that the plus operator operates strictly on data types of Num (short for number).
Here's our first function:
ghci> let doubleMe x = x + x
ghci> doubleMe 2
4
Lists in Haskell are a homogeneous data structure, i.e. they only store elements of the same type. Here's how you create a list:
ghci> let groceryList = ["pecans", "blueberries", "chocolate"]
ghci> groceryList
["pecans","blueberries","chocolate"]
ghci> let oneToTen = [1..10]
ghci> oneToTen
[1,2,3,4,5,6,7,8,9,10]
That last variable assignment demonstrates how to construct a list using a range. Creating a list of infinite length is easy with ranges:
ghci> let allNaturals = [0..]
ghci> allNaturals
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21...
ghci> let allOdds = [1,3..]
ghci> allOdds
[1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39...
These examples will execute forever unless you stop the process within GHCi using the command ctl-c. That last example is a demonstration of how to specify the step within a range.
Often we only want a subset of numbers from such a list, and Haskell provides several facilities for doing this. Common methods for operating on lists include:
ghci> head [5,4,3,2,1]
5
ghci> tail [5,4,3,2,1]
[4,3,2,1]
ghci> last [5,4,3,2,1]
1
ghci> init [5,4,3,2,1]
[5,4,3,2]
Hey look! A helpful list monster from LYAH:
A set comprehension using math notation looks like this:
This can be interpreted to represent a set that contains the first ten even, positivie natural numbers. The part before the pipe is called the output function, x is the variable, N is the input set and x <= 10 is the predicate. That means that the set contains the doubles of all natural numbers that satisfy the predicate.
Here's how we do the same thing in Haskell:
ghci> [x*2 | x <- [1..10]]
[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
To filter within a list comprehension, you use a predicate:
ghci> [x*2 | x <- [1..10], x*2 >= 12]
[12, 14, 16, 18, 20]
More examples of lists comprehensions at learnyouahaskell.com/starting-out#im-a-list-comprehenson
Like Standard ML, OCaml, and other languages in functional programming land, the _ symbol acts like a wildcard matching against any value.
ghci> sum [2,4,6] -- an example of the sum function which operates on lists
12
ghci> length [2,4,6] -- an example of the length function which also operates on lists
3
ghci> let length' xs = sum[1 | _ <- xs]
ghci> length' [2,4,6]
3
This custom length function, length', replaces every element of a list with 1 and then sums that up. This means that the resulting sum will be the length of our list. Also demonstrated in the examples is commenting. The -- operator tells
the compiler to not evaluate the characters pass this point until the
end of the line. If you want a multiline comment You would use the {-
and -} operators.
Tuples are like lists, but unlike lists, they may contain more than one type of value, i.e they are heterogenous. Also unlike lists, the type of a tuple is dependent on its length and the type of values it contains. Use tuples when you know in advance how many components some piece of data should have.
ghci> let a = (1, 'b')
ghci> :t a
a :: (Integer, Char)
Within GHCi, :t
instructs the interpeter to give us back the the type of the
following expression (in this case a) . You can get a list of
commands by entering :h at the prompt. The output we see here tells
us that the tuple contains just two elements, the first one being a
data type of Integer and the second element of type Char (short for
character). A string is really just a list of characters, and a string
has type [Char]. It is different than a single character, and it must
be enclosed by double quote marks, not single quotes. Other common
types include: Int, Integer, Float, Double, and Bool.
Aye! Still following? Great! Because now we're getting to the fun stuff: types and typeclasses. Type classes first appeared in Haskell, and the concept really is not hard, let's go over some terminology.
Type annotations are what you put above your statements to let the compiler know how things should behave, for example:
first :: [a] -> a
first a = head a
That first line is the type annotation and it states that the following function takes a list as an argument and returns some value which is the same type that the list originally contained. Save the above to a file named something like head.hs, and then load it within GHCi like this:
ghci> :l head.hs -- given you are in the current dir of the file
Type annotations are very helpful in helping you to reason about how something should operate without requiring you to look at the statement's definition
An excerpt from the Haskell 2010 Report:
There are six kinds of names in Haskell: those for variables and constructors denote values; those for type variables, type constructors, and typeclasses refer to entities related to the type system; and module names refer to modules. There are two constraints on naming:
Names for variables and type variables are identifiers beginning with lowercase letters or underscore; the other four kinds of names are identifiers beginning with uppercase letters. An identifier must not be used as the name of a type constructor and a class in the same scope."
And a note from LYAH:
Note: the equality operator, == is a function. So are +, *, -, / and pretty much all operators. If a function is comprised only of special characters, it's considered an infix function by default. If we want to examine its type, pass it to another function or call it as a prefix function, we have to surround it in parentheses.
Given this information, let's look at the type signature of the plus symbol:
ghci> :t (+)
(+) :: Num a => a -> a -> a
And here's a graph breaking down the different parts of the type signature.
This states that the plus operator takes two values of
type Num and outputs another value with the same type. The :: operator can be read as "has type of". The class constraint
specifies the typeclass of the type variable a.
A typeclass is a sort of interface that defines some behavior. If a type is a part of a typeclass, that means that it supports and implements the behavior the typeclass describes.
Here are some common typeclasses:
- Eq defines equality,
==, and inequality,/=. - Ord is is used for ordering data.
- Show is used for making values into readable strings.
- Read is used for parsing of strings to produce values
- Enum specificies enumeration across a certain type
- Bounded is used to name upper and lower limits of a type.
- Num is what you think it is, a numeric type.
A function may utilize pattern matching to define how it operates, and a function may contain several function bodies to match against. Here's an example of a function utilizing pattern matching:
lucky :: (Integral a) => a -> String
lucky 7 = "LUCKY NUMBER SEVEN!"
lucky x = "Sorry you're out of luck, pal"
-- save the above as lucky.hs and import it using :load lucky.hs
-- then type lucky 3 or lucky 7 to see how this operates
When you call lucky, its patterns are checked from top to bottom
and when a pattern matches, that function body is used.
This an example of a recursive factorial function using pattern matching:
factorial :: (Integral a) => a -> a
factorial 0 = 1
factorial n = n * factorial (n - 1)
Haskell has if/then/else statements but guards are easier to read:
bmiTell :: (RealFloat a) => a -> a -> String bmiTell weight height | weight / height ^ 2 <= 18.5 = "You're underweight, you emo, you!" | weight / height ^ 2 <= 25.0 = "You're supposedly normal, pffft." | weight / height ^ 2 <= 30.0 = "You're fat! Lose some weight, fatty!" | otherwise = "You're a whale, congratulations!"
That can be read as:
when weight divided by height squared is less than or equal to 18.5 then output some text, otherwise when...
Let's check Miran's weight:
ghci> bmiTell 85 1.90
"You're supposedly normal, pffft."
We can make that function even more readable by using the where keyword at the end of the guards to assign variables:
bmiTell :: (RealFloat a) => a -> a -> String
bmiTell weight height
| bmi <= skinny = "You're underweight, you emo, you!"
| bmi <= normal = "You're supposedly normal, pffft."
| bmi <= fat = "You're fat! Lose some weight, fatty!"
| otherwise = "You're a whale, congratulations!"
where bmi = weight / height ^ 2
skinny = 18.6
normal = 25.0
fat = 30.0
I'm sure many of you are familiar with case syntax from other imperative languages. Haskell takes this concept perhaps a little further.
first :: [a] -> a
first xs = case xs of [] -> error "No head for empty lists!"
(x:_) -> x
This function acts just like our previous implementation of and returns the first element in the list or an error if the list is empty. Remember the _ symbol acts like a wildcard.
The syntax for case expressions is simple:
case expression of pattern -> result
pattern -> result
pattern -> result
...
expression is matched against a pattern, and if it matches, a result is returned.
At this point, LYAH covers currying, which shows that functions really only process one argument at a time, which might make for a nice transition to partial function application and passing functions around. This is skipped here, but if you're interested in learning about currying, see the wiki stub on haskell.org regarding currying. We will instead focus on functionas as first class citizens, i.e. functions as values that can be passed around to other functions.
Haskell functions can take functions a parameters and return functions as return values. A function that does this is called a higher order function. And since functions can be passed around as parameters to other functions, they are called first class citizens. Let's look at how the map function implements this:
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
map takes a function and a list and applies that function every element in the list, producing a new list. Let's see it in action:
ghci> map (+3) [1,5,3,1,6]
[4,8,6,4,9]
When a compiler encounters the $ symbol, the expression on its right is applied as the parameter to the function on its left. So, given the statement:
sum (map sqrt [1..130))
We can rewrite it as:
sum $ map sqrt [1..130]
In mathematics, function composition is the application of one function to the results of another. -- Wikipedia article on function composition
Function composition in mathematical notation looks like:
(f ∘ g)(x) = f(g(x))
In Haskell, function composition is pretty much the same using the . function. The expression above looks like this:
(f . g ) x
And here's an example of function composition in practice:
ghci> map (sum . tail) [[1..5],[3..6],[1..7]]
[14,15,27]
Any powerful programming language should be able to describe primitive data and primitive procedures and should have methods for combining and abstracting procedures and data. -- SICP
You are probably familiar with the types Bool, Int, Char, etc. Now it's time to create some of these data types ourselves. Here's how you create the Bool type:
data Bool = False | True
Simple enough, right? The different parts of the above statement identified:
The type constructor denotes the data type, and the data constructor (sometimes referred to as the value contructor within LYAH) specifies the different values that this type can have. The | is the or operator, so we can read this as: the Bool type can have a value of True or False. Note, both the type and data constructor are required to be capitalized.
Data constructors are actually functions that ultimatley return a value of a data type. Here's how we might represent a shape by contructing a new type Shape:
data Shape = Circle Float Float FLoat
Let's look at the type signature the Circle constructor:
ghci> :t Circle
Circle :: Float -> Float -> Float -> Shape
Here's how you might write a function which takes a shape and returns its surface:
surface :: Shape -> Float
surface (Circle _ _ r) = pi * r ^ 2
This states that the function takes a shape and returns a float. We couldn't write a type declaration of Circle -> Float because Circle is not a type, Shape, however is a type. And because we're interested in the radius, we don't actually care about the first two fields, which tell us where the circle is located on a Cartesion coordinate system. Let's see this in action:
ghci> surface $ Circle 10 20 10
314.15927
It works! If we try to just print out Circle 10 20 5 in the prompt though, we'll get an error. That's because Haskell doesn't know how to display our data type as a string, yet. When we try to print a value out in the prompt, Haskell first runs the show function to get the string representation of our value and then it prints that out to the terminal. To make our Shape type part of the Show typeclass, we modify it like this:
data Shape = Circle Float Float Float deriving (Show)
Now that that the type is part of the Show typeclass, we can do this in the interpreter:
ghci> Circle 10 20 5
Circle 10.0 20.0 5.0
Let's make a data type which describes a person.
data Person = Person String String Int Float String String deriving (Show)
Do you know what the last string parameter is intended to represent? Ice cream. Yep. Our Person type holds the fields first name, last name, age, height, phone number, and favorite ice cream. Haskell has record syntax for making this information more obvious. Here's how that last example can be formatted using record syntax:
data Person = Person { firstname :: String
, lastName :: String
, age :: Int
, height :: Float
, phoneNumber :: String
, iceCream :: String
} deriving (Show)
By using record syntax, Haskell automatically made these functions from the data type: firstname, lastName, age, height, phoneNumber, and iceCream.
ghci> :t iceCream
flavor :: Person -> String
Not only can data constructors use parameters, but so can type constructors.
data Maybe a = Nothing | Just a
The type constructor here, Maybe, states that it takes one parameter, a, and it either returns Nothing or solely a.
A type can be made an "instance" of a typeclass if it supports the behavior. For example, the Int type is an instance of the Eq typeclass because the Eq typeclass defines behavior for stuff that can be equated. And because integers can be equated, Int is a part of the Eq typeclass. If a type is part of the Eq typeclass, we can use the == functions with values of that type. Consider this data type:
data Person = Person { firstName :: String
, lastName :: String
, age :: Int
}
If we have records for more than one person, it makes sense to see if they represent the same peson, which is why it makes sense for this type to be part of the Eq typeclass. So let's derive an instance:
data Person = Person { firstName :: String
, lastName :: String
, age :: Int
} deriving (Eq)
Now, let's test our Eq instance:
ghci> let mikeD = Person {firstName = "Michael", lastName = "Diamond", age = 43}
ghci> let adRock = Person {firstName = "Adam", lastName = "Horovitz", age = 41}
ghci> let mac = Person {firstName = "Adam", lastName = "Yauch", age = 44}
ghci> mac == adRock
False
ghci> mikeD == mikeD
True
ghci> adRock == Person {firstName = "Adam", lastName = "Horovitz", age = 41}
True
We can easily use algebraic data types to make enumerations, and the Enum and Bounded typeclasses help us with that. Consider the following data type:
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
Because all the data constructors are nullary (no parameters taken), we can make it part of the Enum typeclass. The Enum typeclass is for things that have predecessors and successors. We can also make it part of the Bounded typeclass, which is for things that have a lowest possible value and highest possible value. And while we're at it, let's also make it an instance of all the other derivable typeclasses and see what we can do with it.
data Day = Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Sunday
deriving (Eq, Ord, Enum)
Because it's part of the Eq and Ord typeclasses, we can compare and equate days.
ghci> Saturday == Sunday
False
ghci> Saturday > Friday
True
It's also an instance of Enum, so we can get predecessors and successors of days and we can make list ranges from them!
ghci> succ Monday
Tuesday
ghci> pred Saturday
Friday
ghci> [Thursday .. Sunday]
[Thursday,Friday,Saturday,Sunday]
A hello world program:
main = putStrLn "hello world!"
Put that in a file called helloworld.hs, and then compile it:
$ ghc --make helloworld
[1 of 1] Compiling Main ( helloworld.hs, helloworld.o )
Linking helloworld ...
And now to run it:
$ ./helloworld
hello world!
You can also run your program from the command line without having to compile:
$ runhaskell helloworld.hs`
hello world!
A common function used in I/O operations is putStrLn:
ghci> :t putStrLn
putStrLn :: String -> IO()
putStrLn takes a string and returns an I/O action which has a result type of an empty tuple. do syntax is used to glue several I/O actions together into one action to be performed. As an example:
main = do
putStrLn "Hi, what's your name?"
name <- getLine
putStrLn ("Hello " ++ name ++ ".")
++ is the concatenation operator for lists, requiring both lists to be of the same type. Note that a string is just a list of characters. The <- is for performing I/O actions and binding their results to names. Every line except the last line in a do block that doesn't bind can also be written with a bind.
Using return doesn't cause the I/O do block to end its execution. As an example, the following will cotinue executing through the return statement:
main = do
return ()
return "HAHAHA"
line <- getLine
return 4
putStrLine line
These return statements just encapsulate a result that is thrown away since it's not bound to a name. We use the <- function to bind stuff to names.
There are various functions mentioned in this section which are skipped, but one which will soon be needed is the getChar function which reads a character from input, and the 'putChar function which takes a character and returns an I/O action that will print it out to the terminal. Here's how you would use both:
main = do
c <- getChar -- grab user input
if c /= ' ' -- a space
then do
putChar c
else return ()
This is also the first time if/then/else notation has been shown, notice the indentation. This code exits its execution context with return () if it detects the input character is a space, otherwise it continues onward.
The when function is found in Control.Monad. We access it using import Control.Monad. The do block looks like a control flow statement, but it's actually a normal function. It takes a boolean value and an I/O action if that boolean value is True, and it returns the same I/O action that we supplied to it. However, if it's False, it returns the return () action, i.e. an I/O action that doesn't do anything. Here's how we can rewrite the previous piece of code by using when:
import Control.Monad
main = do
c <- getChar
when (c /= ' ') $ do
putChar c
Another handy function is the sequence function which takes a list of I/O actions and returns a single I/O action that will perform those actions in succession.
So, something like this:
main = do
a <- getLine
b <- getLine
c <- getLine
print [a,b,c]
can be rewritten to this:
main = do
rs <- sequence [getLine, getLine, getLine]
print rs
sequence [getLine, getLine, getLine] makes an I/O action that will perform getLine three times. print is something that is new, but it just prints to the screen as you expect.
Functors are things that can be mapped over, like lists, Maybes, and such. In Haskell, they're described by the typeclass Functor:
class Functor f where
fmap :: (a -> b) -> f a -> f b
class means we are defining a new typeclass. You can see that Functor has only one typeclass method, fmap. It takes a function, a -> b , which takes an a and returns a b . It then takes a box, f , with parameter(s) a inside it, and it returns a box, f with a b (or several of them) inside it.
The box analogy is used to help you get some intuition for how functors work, and later, we'll probably use the same analogy for monads. It's an okay analogy that helps people understand functors at first, just don't take it too literally, because for some functors the box analogy has to be stretched really thin to still hold some truth. A more correct term for what a functor is would be computational context. The context might be that the computation can have a value, or it might have failed, or that there might be more values (lists).
If we write fmap :: (a -> b) -> (f a -> f b) , we can think of fmap not as a function that takes one function and a functor and returns a functor, but as a function that takes a function and returns a new function that's just like the old one, only it takes a functor as a parameter and returns a functor as the result. It takes an a -> b function and returns a function f a -> f b . This is called lifting a function. Let's play around with that idea:
ghci> :t fmap (*2)
fmap (*2) :: (Num a, Functor f) => f a -> f a
ghci> :t fmap (replicate 3)
fmap (replicate 3) :: (Functor f) => f a -> f [a]
You can think of fmap as either a function that takes a function and a functor and then maps that function over the functor, or you can think of it as a function that takes a function and lifts that function so that it operates on functors. Both views are correct and in Haskell, equivalent.
There are two functor laws that might seem a bit confusing and unnecessary, but if we know that a type obeys both laws, we can make certain assumptions about how it will act. If a type obeys the functor laws, we know that calling fmap on a value of that type will only map the function over it, nothing more. This leads to code that is more abstract and extensible, because we can use laws to reason about behaviors that any functor should have and make functions that operate reliably on any functor.
- If we map the id function over a functor, the functor that we get back should be the same as the original functor.
Formally written:
fmap id = id
This says that if we do fmap id over a functor, it should be the same as just calling id on the functor:
ghci> fmap id [1..5]
[1,2,3,4,5]
ghci> id [1..5]
[1,2,3,4,5]
- Composing two functions and then mapping the resulting function over a functor should be the same as first mapping one function over the functor and then mapping the other one. Formally written:
fmap (f . g) = fmap f . fmap g
If we do fmap (f . g) (Just x) , we see from the implementation that it's implemented as Just ((f . g) x) , which is of course, Just (f (g x)) . If we do fmap f (fmap g (Just x)) , we see from the implementation that fmap g (Just x) is Just (g x) . For that reason, fmap f (fmap g (Just x)) equals fmap f (Just (g x)) and from the implementation we see that this equals Just (f (g x)) .
If you think of functors as things that output values, you can think of mapping over functors as attaching a transformation to the output of the functor that changes the value. When we do fmap (+3) [1,2,3], we attach the transformation (+3) to the output of [1,2,3], so whenever we look at a number that the list outputs, (+3) will be applied to it.
Further reading at LYAH
Monoids are simple algebraic data structures which have two properties:
- An an associative binary function
- an identity value with respect to the binary function
Here's its definition:
class Monoid a where
mempty :: a -- the identity
mappend :: a -> a -> a -- associative binary operator
Lists are monoids:
instance Monoid [a] where
mempty = []
mappend = (++)
Here's an example showing associativity using the ++ function:
ghci> "la" ++ ("di" ++ "da")
"ladida"
ghci> ("la" ++ "di") ++ "da"
"ladida"
And since mappend is equivalent to ++, we get the same associative functionality:
ghci> ("one" `mappend` "two") `mappend` "tree"
"onetwotree"
ghci> "one" `mappend` ("two" `mappend` "tree")
"onetwotree"
Further reading at LYAH
With monads, we are concerned with this problem:
If you have a value with a context,
m a, how do you apply to it a function that takes a normalaand returns a value with a context? That is, how do you apply a function of typea -> m bto a value of typem a?
We are needing a bind function defined within the monad typeclass:
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
x >> y = x >>= \_ -> y
fail :: String -> m a
fail msg = error msg
We can take a normal value and wrap it inside a data type. For instance, we can take a 1 and wrap it so that it becomes a Just 1. Or we can make it into a [1], or an I/O action that does nothing and just yields 1. The function that does this is called pure. return is the same as pure, return doesn't change the state at all, it only serves to bring a value into the monad's context.
The bind operations, >> and >>=, combine two monadic values. We are specifically interested in the >>= function.
>>= takes a monadic value, and a function that takes a normal value and returns a monadic value and manages to apply that function to the monadic value. For the function to take a normal value, it has to take into account the context of that monadic value.
Maybe is also of type monad:
instance Monad Maybe where
return x = Just x
Nothing >>= f = Nothing
Just x >>= f = f x
fail _ = Nothing
Playing around with Maybe as a monad :
ghci> return "WHAT" :: Maybe String
Just "WHAT"
ghci> Just 9 >>= \x -> return (x*10)
Just 90
ghci> Nothing >>= \x -> return (x*10)
Nothing
"What monads and their associated operations provide is modularity. By defining an operation monadically, we can hide underlying machinery in a way that allows new features to be incorporated into the monad transparently." -A Gentle Intro to Haskell
That quote sums this section up, and there really isn't a replacement for Lipovača's chapters on Monads:
Both chapters are well worth the read.
Chapter 6:
- let statements
- currying
- lambda functions
- partial function application
- folds
- tacit/point-free programming
Chapter 7:
- loading modules using the import statement
- playing around with the Data library
- exporting our modules.
Chapter 8
- type synonyms
- concrete types
- recursive data structures (and fixity)
- typeclass instances
- functors
- kinds
All of Chapter 10
Chapter 11
- Applicative functors
- newtype keyword
Chapter 12
- do notation
- The list monad
- monad laws
All of Chapter 14
## Appendix B ToC
-
Type safety
-
Cons (:) and nil ([])
