Table of Contents
- Chapter 1: Wizards, Types and Functions
- Chapter 2: Type Construction
- Chapter 3: I Wanna Be FAMIOus!
- Chapter 4: Monad Transformers - putting Ogres to sleep while counting bodies
- Chapter 5: Folding stuff, Traversing structures
- Part 2
How this book came to be: instead of an introduction
Feel free to skip this somewhat philosophical intro right to the Chapter 1
Lately, I’ve been spending quite a bit of time with Type Theory, lambda cube (e.g., implementing SystemF-omega-ish type library in coffeescript for the fun of finding out how things work as Dr. Feynman used to say), toy functional languages (Haskell is great, but what would a great functional language look like if it were designed today — with all that we’ve learned from state-of-the-art Haskell development in the last 20 years?), parsers, GUI libraries design and functional reactive programming.
Two thoughts persisted:
- “I need to write another monad tutorial” — haha, got ya— “how do I teach functional programming to my kids?” — so that it’s light, comprehensible, fun and conveys the beauty of the concepts involved, — and:
- “we’ve been doing it all wrong”
Ok, the latter may be a gross exaggeration, but I need to drive the point across. As many unfortunate souls before me, I have gone down the painful but oh-so-typical road of coming from imperative OO background and trying to build bridges from the patterns learned there to a completely, absolutely different functional world.
The problem with this is, your brain works against you (do read the classic “Thinking, Fast and Slow” by Dr. Kahneman if you haven’t yet — at the very least, it will help you detect and fight your own biases)
Our brain’s “System 1” works in patterns. It is efficient, extremely fast — much faster than the conscious “System 2”, which we are using when studying Category Theory, — it is in contrast subconscious, it deconstructs and shreds all the elephants you see in your life into basic shapes and curves and colors, which makes recognizing elephants a very easy task, until one day you glimpse upon a cloud like this —
— and your brain goes: “oh, look, it’s an elephant!”
Well, no, it’s a cloud.
And this is exactly the trap laid out for programmers trying to escape to the wonderful world of Haskell from the less elegant Java, C++, or that terrible-which-shall-not-be-named-but-ends-in-…avaScript backgrounds. The thought goes: C++ is a programming language, as is Haskell, so the concepts should be pretty similar, right? Isn’t it like Indian and African elephants: sure, one has bigger ears but aren’t they essentially the same?
To master the power of Haskell, you need to set aside everything you know about imperative programming and build upon a totally different foundation. One of pure abstract math, starting from category theory, from set theory, from type theory, from Henri Poincare; you have to build Natural numbers with pen and paper starting with an empty set, construct a Ring on them, abstract away and discover Monoids, start appreciating the beauty of internal structure of types and categories manifested in polymorphic functions and laws on them, be amazed at how one abstraction can elegantly describe seemingly unrelated entities…
But who in the world has time for this?!
Well, exactly. This is one of the primary reasons there’s still a certain bias against Haskell among practitioners — a big part of Haskell community give impression of very smart monad-stacking-arrow-composing-scientist-magicians sitting in their ivory towers with too much time on their hands working out some abstract problems, while we need to code stuff that works even if it’s ugly.
Take heart, there’s hope! But before I outline a proposed (yet another) way out, let me illustrate the elephant vs cloud conundrum with a pretty typical “where is my
for loop?!” situation.
Let’s say you are building a GUI library based on some low-level API and need to render lines of text on screen. You construct an array of textures where each corresponds to a new line of text and need to render each one under the other, incrementing an y coordinate, like so:
Something you’ve done a thousand times in different situations. You switch to Haskell where you have a list of textures
textures :: [Texture] and your System 1 starts screaming “where is my
for loop?!” and then “how do I pass the state when iterating?” Should I use mutable variables,
IORef, MVar, TVar ? I know I am supposed to map over lists, so should I use a
State monad to increment y while mapping?
And only when you tell your System 1 to stop getting ideas from your imperative experience, consider abstractions, realize it is best to fold and traverse structures in the functional world, you come to something like:
… which gives you goosebumps after all the braces and semicolons in the c-land, but patterns have nothing in common: you iterate over arrays with mutable variables in one and you fold structures with computations in the other. Elephants and clouds.
So, how do we teach Haskell to kids or help adults master its’ power faster and more efficiently?
First, stop trying to build bridges from imperative world — it messes with people’s brains. In fact, explaining design patterns for program architecture on the real world problems and contrasting approaches with imperative world is actually very much needed and largely missing now — but this needs to be done only after a student has learned functional approach and small patterns from scratch. However, starting teaching Haskell in the bottom-up imperative way, with “Hello World” and calculator in ghci is in my strong opinion absolutely counter productive — it leads right into the elephants vs clouds trap and it takes much longer to start appreciating the power and beauty of Haskell.
We need to start from something close to the Type Theory, make people understand and fall in love with Types, their structure, their daily lives, their relations with each other; student has to become fluent in writing and understanding type level functions before she even thinks about writing “real” functions. It is actually a pretty traveled road as well — but only if you have a reasonably strong math background.
Catch up on your Category Theory reading (Bartosz Milewski’s “Category Theory for Programmers” is out and it’s excellent), study Typeclassopedia, use amazing Stephen Diehl’s “What I Wish I Knew When Learning Haskell” as a reference, and get a feeling on how to structure real programs using monad transformer stacks, but whatever you do, under any circumstances, DO NOT read monad tutorials! Monads are actually very simple, it’s just another beautiful and powerful math abstraction, one among many, and you will confuse and break your brain with false analogies if you read the tutorials — study it in the context of Functor-Applicative-Monad hierarchy, so, again, Typeclassopedia.
Then, what was the point of all this? I am a very visual person when studying, and I’ve been thinking for some time now that math concepts underlying modern functional programming and type theory can be explained in a more accessible way using visuals, magic and various cute animal related analogies. Existing literature on the concepts mentioned above is often too technical, even for practicing programmers, let alone kids, even in their teens, and focuses on formal proofs a lot.
However, if we ease on trying to rigorously prove stuff and just illustrate and explain those same concepts, from lambda calculus in SystemFw (even the name is a mouthful, but the machinery is again extremely simple!) to types and their relations to category theory and arrows, in a top-down visual approach, this may help people build new patterns, completely unrelated to imperative programming, and then gradually move to more technical, more in-depth study while already becoming productive in writing elegant Haskell code for practical tasks. Something in the spirit of excellent “Learn you a Haskell” but building up upon math foundation of types and typeclass hierarchy vs “hello world” and ghci REPL.
Hence, the idea of “Magical Haskell” was born. In fact, it should probably go well hand in hand with “Learn you a Haskell” - with the latter providing for a lot of basic language foundation in much more detail, and “Magical Haskell” focusing on trying to create a system of typed functional patterns, typeclass hierarchy, and explaining abstract technical concepts in an accessible comprehensible way.
Chapter 1: Wizards, Types and Functions
In this chapter: functional programming is magic * solving problems the functional way * putting something on the screen * introducing types * introducing type functions
Functional Programming Is Magic
You wake up in a cheap motel room in Brooklyn. You hear police sirens outside, the ceiling is grey and dirty, and a big cockroach is slowly crawling across. You don’t remember much, except that you need to be in a fancy restaurant on Manhattan at 7 pm — oh my, it’s in 15 minutes! — and that you are a wizard. The problem is, you only remember 3 spells:
You are obviously in a hurry so looking attentively at a cockroach you wave your hands and go: “Moz’bah’da!” — and puff! — there’s a beautiful white horse right beside the bed! In a short moment you realize that riding a horse through New York might not get you there on time plus you are not sure you even can ride a horse, so you wave your hands again and shout: “Gimmeraree!”
The horse disappears in a puff of smoke and all you get is a pile of stinking goo on the floor. Oh-oh. You forgot that “Gimmeraree” works only on pigs! Poor horse. You catch another cockroach, go outside, and this time say your spells in the correct order — “K’hee-bah!”, “Gimmeraree!” — and there you go, red Ferrari Spider, in mint condition standing right there besides the garbage bins. Hastily, you jump into the car and drive away to a meeting that will hopefully clear up your past, present and future destiny.
Typed functional programming is just like magic. Your spells are functions — they turn something into something else (like pigs to Ferraris or strings to numbers) or produce some effect (like putting Ogres to sleep or drawing a circle on the screen), and you need to combine different spells in the right order to get to the desired result.
Solving Problems As Wizards Do
So how do we approach solving problems in a functional way? The mage above needed to get a fast mode of transportation and all he had were cockroaches. So, he had to think about how he could get from a cockroach to a Ferrari using the spells he knows by combining them in the right order. He started with an end-result — Ferrari — and worked backwards from there, getting to the right sequence by composing spells that work on the right subjects.
Now, let’s get more real and say you need to calculate an average of a list of numbers and show it on the screen. Please resist the imperative urge to start telling computer what to do and how to do it and let’s focus on the problem as a wizard would instead.
You have a human and you need to turn her into a line on the screen, hopefully without killing anyone. Let’s work backwards from our desired result — “line on the screen with the average printed out”.
To get to this result, we need something that takes a number and shows it on the screen. Let’s call this something “print”:
Now our problem is a bit easier - we need to get from a human to a number. “Print”, whatever it is, needs a number to operate. Since our goal is to calculate and show an average value, the previous step needs to take a list of numbers and, uhm, calculate their average:
Our problem became easier still - now we just need to extract the list of numbers from our human and the solution is ready!
What did we just do? We have broken down or decomposed our problem into smaller pieces, solutions to which we already know or can come up with easily enough, and combined them in the right order to get to the desired result. Just like with the mage above, we cannot give a string or a horse to our calculate average - it expects a list of numbers, so it will not compose with functions that produce something other than a list of numbers! Thus, we came up not only with “spells”-functions that we would need to solve our problem, but also with types that our functions should work with: a list of numbers, a number, an effect of putting something on screen. From the start, just by thinking about how to solve a problem, we “invented” two most important concepts in programming, computer science and mathematics itself: Functions and Types.
We’ll start looking at them more closely later on in this chapter. For now, here’s a bit of real magic: as it turns out, Haskell code maps virtually 1:1 to this approach! Look at the first line of the code below (don’t mind the rest for now) and try it live in your browser:
The first line is our sequence of “spells”, or, really, functions, that start with a human sitting at the keyboard and get us to the line on the screen with calculated average shown. First, we ask a human to enter the list of numbers with
ask and pass whatever was entered to the next function -
toList - to convert the string she enters to an actual
List. Resulting list is given to
calcAverage function that in turn passes its’ result to
printResult. Exactly what we came up with, reasoning about the problem in the passage above.
We started with the desired end result, worked backwards by decomposing the big problem into smaller pieces and connected or composed them so that the output type of one function fits to the input types of the next. This is the essence of every functional program. Lines of code after
where further detail how the “spells” we are chaining should behave - don’t concern yourself with them yet. What’s important, is to get a feel of the process:
- What is our desired result?
- What is our input?
- Work backwards from the result to the input, decomposing the problem into smaller pieces that we know how to solve, by thinking about how to convert between types along the way
- Compose smaller functions, each of which solves a smaller problem piece, together into a bigger function, making sure the types fit
Practice this approach on some other problems you would like to solve. We will use it on quite a bit of real world problems further along.
Let’s Fall In Love With Types!
To become a really powerful Haskell mage you need to get to know and understand Types, their birth, their daily lives and their relations with each other very intimately. Types come before functions and functions are meaningless without types. So, what are types? Intuitively, a type is just a bunch of objects (or subjects) sharing some common characteristic(s) thrown in a pot together. You could say that the type of your Ferrari Spider is Car, as is the type of that Toyota Prius. The type of both a pig and a horse is Animal. The type of 1, 114, 27428 is Natural Number. The type of letters ‘a’, ‘C’, ‘e’, ‘z’ is Char (that’s an actual type for characters in Haskell). The last two are ubiquitous in programming, so let’s look at them more closely.
However, let’s not forget that we are creative wizards, so we will be building a whole new world from scratch. We will call this world Category ‘Hask’ (for reasons that will become apparent much later), or simply Hask from now on, and it will be inhabited by Types, their members, or values, Functions, and some other interesting characters. As we create this world, we will gradually become more and more powerful, and eventually will be able to write efficient, elegant and robust Haskell programs for any practical task.
A Char and an Int walk into a bar, and make a Function
Natural numbers is the most intuitive math concept that everyone is familiar with - that’s what you use when counting times you read confusing monad tutorial articles. Natural numbers start with nothing, zero, and go on forever. Once you subtract the number of times you read confusing monad tutorials (at least 37) from the number of times it made sense (0), you realize the need for negative numbers, which together with naturals give you another infinite type - Integers. Various “ints” that you might be used to from the C-land, as well as the type Int in Haskell, is the teeny-tiny subset of real Integers, limited by 231-1 or 263-1 on the 64-bit systems. What is 9,223,372,036,854,775,807 compared to infinity? Same as nothing, but fortunately it’s enough for most practical purposes, including counting all the money in the world if you want to write a new Automated Banking System at some point.
Char is our second foundational type - a pot of all characters we use when writing stuff in different languages, including mathematics or Egyptian pictography if we want to get fancy. It is also a finite type and quite a bit smaller than Int at that.
By themselves, these types are quite boring and we can’t do much with them - it’s just lonely numbers and characters hanging out all by themselves. They are sort of like prisoners in solitary confinement with no way to interact with the others. Let’s break them out and set them free to roam the world and talk to each other! To do this, we are going to need functions.
Let’s line up our characters from the Char type as they do in English alphabet. Then we can ask each letter - “which number are you?” - like so:
We have just constructed our first function! What it does is match each letter with a number. Now, this is very important: it matches all letters with a number. We could match just some letters to certain numbers - then our function would be called a partial function, since it would be defined not for all members of our type. A function can map several members of a type to one member of another type, e.g., we could define a function that matches ‘a’ and ‘b’ to 1, ‘c’ and ‘d’ to 2 etc - it would be a perfectly fine, even if a bit weird, function. However, what we absolutely cannot do is define a function that matches a member of a type to several members of another type:
You can trust the word of a function. You cannot trust anything from a procedure.
Our function, let’s call it
whichNumberIsChar takes a Char and gives an Int as a result. In Haskell, we write:
whichNumberIsChar :: Char -> Int. You can try it live in your browser here. Just type (cheating a bit since we are using another, much more powerful polymorphic Haskell function to define ours) on the right where “GHCi” prompt is:
let whichNumberIsChar = fromEnum :: Char -> Int and then you can type
whichNumberIsChar 'Z' or some other character and see what happens.
Our world is still very boring. We have two basic types living in it and we have one function between them, but we can’t even add 2 numbers together! That’s not enough to solve a simple calculate an average for some numbers problem, let alone something more interesting. However, it turns out that Int, Char and some imagination can get us much further than may appear. Let’s make some more magic!
First, we need strings. What is a string? It’s basically just a bunch of characters put together in order. Like “abc”, “xyz” or “Hello World”. This hints at how we can introduce the type String: it’s a set of all possible combinations of characters from Char. Easy, right? We can also introduce another obvious useful function right away, between String and Int, that gives us the length of a string:
length :: String -> Int. Try it out in our repl and you should see something like:
How about “some numbers” type? We can use the same logic as above and introduce the type ListInt - a set of all possible ordered combinations of numbers from Int - such as
[1, 2, 3] or
[10, 500, 42, -18]. What if we treat each string as a sentence and want to define a type Book that would contain a bunch of sentences together? Again, we can define it as a set of all possible ordered combinations of strings from String.
Do you notice a pattern? We take a type, apply some manipulation we describe as “a set of all possible ordered combinations” to members of this type, and we get a new type as a result. Doesn’t it look just like a function?!
Let’s call it
List. Just like we have defined functions
whichNumberIsChar :: Char -> Int and
length :: String -> Int,
List is also indeed a function, one that takes a Type and creates a different Type! In Haskell, we write
List :: * -> * (‘*’ is a synonym for Type in Haskell). They are sometimes more formally called type level functions and they are the core of the beauty, elegance and efficiency of Haskell. We will be doing a lot of type creating down the line!
Curry and Recurse!
We saw that a function takes one argument of one type and maps it to exactly one value of another or the same type. A couple of questions should arise at this point:
- what do we do with functions of several arguments that exist even in math – like
f(x,y) = x + y, – not just C-land programming languages, and
- how do we actually define functions without resorting to writing explicit tables that map arguments to results, something like “1 + 1 = 2, 0 + 1 = 1, 1 + 0 = 1..” etc for all numbers. You could certainly do that but it’s a bit unpractical, where by “unpractical” I mean totally nuts.
There are a couple of ways to tackle the first one. Let’s say we want a function that takes a Char and an Int, converts a character to a number with the help of our
whichNumberIsChar function and calculates the sum of the two, something like
anotherWeirdFunction c i = (whichNumberIsChar c) + i – but we can’t do this since the functions we defined take only one argument! One way to work around it would be to somehow combine our Char and an Int into a new type of pairs (Int, Char) – similar to what we have done with List above – and write:
Now we are ok - our function takes just one argument. Like this:
TK – a picture of different options to define anotherWeirdFunction.
This is a perfectly valid way to do it, and we will see how to construct pairs from other types in the next chapter, however it turns out it is much more powerful to use a different approach. First, one very important point:
Functions are first-class citizens in functional programming (that’s kind of why it’s called functional programming) - which means you can pass a function to another function as an argument and return a different function as a result.
Let’s say you want to take a ListInt we defined above and multiply all it’s elements by some number
n. In the imperative world you’d write a function that takes a list and a number
n, goes through some cycle and multiplies it. An ok approach; but what if later on you’d need to add a number
n to all list elements? You’d need to write a different cycle that now adds numbers. Wouldn’t it be great if we could just pass a function that we want to apply to all list elements, whatever it is? In Haskell, you can, by simply writing:
We pass a function that adds 2 -
(+2) - or multiplies by 2 -
(*2) - and a ListInt to a function called
map (we will define it in the next chapter), and get another list as a result. Much more concise and powerful than writing a lot of boilerplate imperative cycles, and also hints at how we can define functions of multiple arguments by looking at some further examples:
(+) x yis a function that takes an Int and returns a new function that takes an Int and returns an Int. So,
(+2)is a function that adds 2 to any number,
(+18)adds 18 etc - and we create these functions on the fly by passing only 1 argument to (+) first. So, the type signature of (+) is:
(+) :: Int -> Int -> Int, which you can read as
(+) :: Int -> (Int -> Int), i.e. exactly what we just wrote - it takes an Int and returns a function that converts Int to Int!
anotherWeirdFunctionis defined similarly: it’s a function of one argument that takes a Char and returns a function of one argument that takes an Int and returns an Int:
TK - a picture of functions creating other functions
So, in general, function of many arguments can be defined as a function that takes 1 argument and returns a function that takes 1 argument and returns a function… etc. This technique is called currying, because that’s how you make chicken curry. No, not really. It was invented by Haskell Curry, in whose name both the currying and the Haskell language itself was named.
Currying is extremely useful, because it makes the math much simpler and also allows you to create different functions on the fly and pass them around as you see fit. If you want to dig into details, there’s a special optional chapter on Lambda Calculus - it’s quite educational if you want to look into internal machinery of pretty much any modern functional language - since we will create a simple functional language there from scratch, which let’s you look at all execution steps in detail, but you don’t really need it to learn Haskell.
Now, let’s turn to the second question - how to construct functions efficiently.
It is in fact possible to start with an empty set and define all of Haskell - first, you construct natural numbers starting with an empty set as we showed in an aside above, then you can define operation of addition on these numbers, invent integers once you realize you need negative numbers, then define multiplication via addition etc. It is a long and winding road.
We won’t be doing that (although it’s a pretty cool exercise to do on your own after you read the Lambda Calculus chapter) - since existing computer architectures provide a bunch of operations, such as addition, multiplication and memory manipulation for us much more efficiently than if we were to implement them from scratch by translating pure functional lambda calculus logic. Haskell additionally defines a bunch of so called primops, or primitive operations, on top of those, and then a bunch of useful functions in its’ standard library called Prelude - so you can obviously use all of them when writing your functions and do things like:
Having said that, a very important concept in functional programming that we need to understand is recursion. It allows you to write concise code for some pretty complex concepts. Let’s start with “hello world” of functional programming - factorial function. Factorial of a number n is defined simply as a product of all numbers from 1 to n, and in Haskell you can in fact simply write
product [1..n] - but it’s too easy, so let’s create our factorial function recursively:
What’s happening in recursion is that a function calls itself under certain conditions - in the case of
fact, when n > 0. Try executing
fact function on the piece of paper with different arguments. E.g., if we call
fact 1 here’s what’s going to happen:
Phew. Now try expanding
fact 10 on paper when you have half an hour to waste. There’s nothing complex about recursion - you (or a computer) simply substitutes function call to the function’s body as normal, and the main thing to remember is that your recursion needs to terminate at some point. That’s why you need boundary cases, such as
fact 0 = 1 in the case of factorial, but it can be completely different conditions in other functions.
That’s in essence all there’s to it.
In a very short time, starting with barely anything but an empty set, we have come up with the concepts of:
- Types, inhabited by their members, also called values, and introduced two very simple types: Int and Char
- Functions, which map values of one type to values of another (or the same) type
- Type Functions, which create new types from other types, and introduced a couple of useful complex types: String and ListInt
- Composition, an essence of a functional program (and, incidentally, Category Theory, but we won’t be going there for quite some time yet)
- Ways to construct functions via currying and recursion
This is pretty much everything we need to gradually build our magical Hask world!
What is currently missing is details on how exactly we can define and use functions such as
length, that give us the length of a String (or, as we have seen above, any other Type constructed with the help of our
List type function!) and
List, that creates new types. We can’t just tell a computer “give me a set of all possible combinations” - we need to be slightly more specific. In the next chapter, we will continue following the adventures of our mage and will focus on card magic, while constructing different types and intimately understanding their internal structure - which is an absolute requirement for designing efficient functions.
Let’s roll up our sleeves and get to it!
Mage’s Toolbox 1: Simple Types, Simple Functions, Recursion, If-Else
Download and install haskell from http://haskell.org or via package system on your OS. Run
ghci to work with repl, or use online repl.
Type names and Type Constructor names always start with a capital letter.
Functions are defined as:
Definition via pattern matching:
Functions of many arguments defined via currying - as a function of one argument that returns a function of one argument that returns a function…:
Chapter 2: Type Construction
In this chapter: * house of cards * algebraic data types * Maybe yes, maybe nothing * Lists and recursive types * Function definition
You got to the “Nobu” right on time, barely past seven. As you were approaching the hostess, a hurricane of a girl ran into you - “Thank goodness you got here on time, Curry!” - Curry, that must be my name? But why, I don’t even like curry?! Must be a different reason… - grabbed your hand and dragged you past the busy tables somewhere deep in the restaurant, through the kitchen, out the back door, down the stairs and into a dimly lit room. In the middle of the room stood a card table - green cloth, some barely visible inscription that spelled “Monoid” in golden letters on it, - surrounded by six massive chairs that looked really old. The girl abruptly stopped, turned around, looked you right in the eye - hers were green - and asked almost irritably, but with a pinch of hope in her voice:
– Well? Are you ready?
– Ahem… Ready for what?! Can you explain what’s going on?
– Did you hit your head or something? And where were you last week, I called like 27 times! And why do you smell like manure - did you suddenly decide to visit a farm?! Ah, no time for this! - she dragged you to the table and pushed you into one of the chairs - she was strangely strong despite being so miniature - so that you had no choice but to sit. BOOM! Suddenly, a small fireworks exploded in your eyes and you felt more magic coming back to you.
Out of thin air, you create a new deck of cards with intricate engravings on their backs, nothing short of a work of art. You feel them - they are cold and pleasant to touch, - but then rest your hands on the table, close your eyes, and.. it’s as if the cards became alive and burst in the air above the table, shuffling, flying around, dancing. You open your eyes, enjoying your newly mastered power over cards, barely nod your head and the deck, obeying your wishes, forms into a fragile house of cards right beside the Monoid sign.
You turn to look at your mysterious companion. She is smiling and there are twinkles in her eyes.
House of cards with a little help from Algebra
Looks like our mage is making friends and remembering new spells, this time without risking any animal’s wellbeing. Let’s follow in his footsteps and learn some card magic!
First, try dealing some cards in our repl. Just follow the link and click “run”. You’ll see some beautiful (well, not as beautiful as the ones Curry created, but still..) cards being dealt: … 9♥ 10♥ J♥ Q♥ K♥ A♥ - with barely more than 20 lines of code. Let’s understand what’s going on here step by step.
To start doing card magic - or card programming for that matter - we also need to create a deck of cards out of thin air. Here’s one way of doing it in Haskell:
We have created 3 new types above. CardSuite is inhabited by 4 values: Clubs, Spades, Diamonds and Hearts - just like Int is inhabited by 264 values - that correspond to playing card suites. CardValue is inhabited by 13 values that represent card face values. All of it is pretty self-explanatory. Type Card represents a specific card and is a little bit more interesting - here we are combining our two existing types into one new type. Don’t mind
deriving statements for now - we’ll explain them down the road, suffice it to say that here Haskell automatically makes sure we can compare values of these types (
Eq) and we can convert them to numbers (
Open the repl linked above again, run it (if you don’t run it first you’ll get an error as the types won’t be loaded into the interpreter), and then play with these types on the right:
Here we bound
val to CardValue Jack,
suite to CardSuite Spades and created 2 cards - Ace of Hearts directly from values and Jack of Spades from our bound variables - both approaches are perfectly valid. Create some other cards in the repl to practice.
Looking at the types definition above, the syntax for type creation should become apparent: to create a new type in Haskell, we write
data <Name of Type> = <Name of Constructor1> <Type of value 11> ... <Type of value 1n> | <Name of Constructor2> <Type of value 21> ... <Type of value 2m> | ... . You can read symbol
| as “or” - it’s used for combining different types together into a new Sum Type, values of which can be taken from a bunch of different types we are combining, but every value is taken from only one of them. Types like
data Card = Card CardValue CardSuite are called Product Types and every value of such type contains values of all of the types we are combining.
Algebraic Data Types
Sum and Product types together are called Algebraic Data Types, or ADT in short (which may be confused with abstract data types that are quite a different matter, but we will call algebraic types ADT), and they form a foundation of any powerful modern type system. Here is the illustration with some more examples:
- TK: picture with product and sum types, some examples
Understanding ADTs is extremely important in Haskell programming, so let’s spend more time discussing them and looking at different ways to define them. Here are several more examples.
Type Person that contains their name and age:
data Person = Person String Int. We are combining a String to represent a name and and Int to represent an age and then we can create people like so:
Person "Curry" 37 or
Now, this is interesting - we have combined 3 types that “store” a String, an Int and a Double inside a constructor and add a simple value “Undefined” as the fourth possible value. It means that values like
JString "hello world",
JDate 12345225 (which is quite a long time ago),
JNumber 3.141 and
Undefined are all valid values of the type JSValues. We are using both Product and Sum types here.
By now you should get a pretty good feel on what sum and product types are. When you create a product type, you combine values of several different types in one value. When you create a sum type, each value of your type can be from a different type, but only one. Here is how it is represented visually in our example types and in the boring computer science notation:
- TK: picture of Product and co-product projections, inl / inr etc.
What if you wanted to extend the type Person to include more information about a person, which would be much more useful in the real world situation? E.g., place of birth, parents, first and last names, education, address etc. If you had to write something like
it would be extremely confusing to use - you’d need to remember the order of fields, you’d confuse fields with the same types etc. Thankfully, Haskell supports records - basically, a Product Type with named fields. We can define our Person type properly like this:
Type Functions Are Functions, Maybe?
Let’s spend some time reviewing a statement we made in the last chapter: type and data constructors are functions. This is extremely important to understand and internalize, so that you do not become confused when writing real world programs that use monad transformer stacks and similar concepts that may look overwhelming, but are in fact quite simple. You need to be able to easily read type signatures and understand their structure at first glance.
Let’s look at a couple of types, renaming type names now to distinguish between types and constructors:
data Cards = Card CardValue CardSuite and
data People = Person String Int. The part on the left is the name of the type, the part on the right is the name of the data constructor and types of the values that this constructor contains. So, in reality Card is a function that should be read in Pascal-ish pseudocode as
function Card (x:CardValue, y:CardSuite) : Cards - i.e., it’s a (constructor) function from 2 variables, one of type CardValue, another of type CardSuite that returns a value of type Cards! Same with Person, which turns into
function Person (x:String, y:Int) : People.
In fact, using so called GADT (generalized algebraic data types) Haskell notation, this becomes even more apparent - below is the solution to the task of extending Card type with the Joker card written first with the familiar syntax and then using GADT:
Looking at the 2nd variant, the point about Card and Joker being functions becomes much clearer. In effect, it tells us that we are defining type Cards which contains 2 constructors: Card, which takes 2 arguments of type CardValue and CardSuite and returns a value of type Cards, and Joker, that takes no arguments (or strictly, an empty Type -
()) and is a value of type Cards.
We can take it one step further, and take the analogy of Product and Sum types to it’s fullest - we can treat the type Cards as type function that is a sum of 2 product types:
typeFunction Cards = Card (x : CardValue, y : CardSuite) + Joker()! Of course
+ here has nothing in common with arithmetic sum but has the same meaning as
| in real Haskell syntax.
So, Card is a constructor that creates a value of type Cards from 2 other values, and Cards, even though we just called it a type function, is in fact a “type constant”. It is a concrete type - you cannot apply it to another type and construct a new one. Unlike type function
List that we hinted at in the last chapter, that actually creates new types from other types - and as such is much more interesting and important for us. We’ll get to it in the next section and we’ll need to understand it to follow along our card dealing program further.
For now, let’s start with the simplest real (non-constant) type function, one that constructs new types from other types: Maybe, which is used ubiquitously in Haskell.
This notation is very often a source of confusion for beginners and even advanced Haskell students - we are using variable
a on both sides of the type definition, but they mean very different things on the left and on the right! In fact, this confusion should be cleared if you read this sort of definition in the spirit of what we’ve described above:
typeFunction Maybe (a : Type) = Just (x : a) + Nothing (). Please dwell on it until you fully understand the issue - it will save you lots of hours of frustration with more complex types down the road. We are in effect saying here: Maybe is a type function that takes a type variable
a and creates a new type from it (
Maybe a) with help of 2 constructor functions -
Just, that takes a “regular” variable of type a and creates a value of type
Maybe a, and
Nothing, a function of zero arguments that is a value of type
Maybe a. So,
a is a variable of type “Type” - it can take a value of any Type we defined - on the left, and it is used in the type signature for constructor function
Just variable on the right.
Take a breath and let it sink in.
Why is the type (which really is a type function) Maybe a useful? It’s the easiest way to handle failure in your functions. E.g., you could define a function
divide like so:
This function would return
Nothing if you try to divide by zero, instead of crashing or throwing an exception, and
Just <result of division> if you divide by non-zero. This is a trivial example, but Maybe is of course very useful in thousands of other more complex situations - basically, anywhere you need to handle possibility of failure, think about Maybe (there are other ways to handle failure and errors in Haskell as we shall see further on).
Note also function definition syntax - a very powerful and concise pattern matching approach. Under the hood, this definition translates into something like:
.. but in Haskell you can avoid writing complex nested
case statements and simply repeat your function definition with different variable patterns, which makes the code much more readable and concise.
So, what if we also have a function
square x = x * x that works on Doubles and need to apply it to the result of our safe
divide function? We would need to write something like:
To do the “somehow extract” part in Haskell, we again use pattern matching, so the function above would be written as:
We pattern match the result of
divide and return
Nothing if it’s
Just square of the result if it’s
Just something. This makes sense, and we just found a way to incorporate functions that work between Doubles into functions that also work with Maybe Doubles. But come on, is it worth such an complicated verbose syntax?! Isn’t it better to just catch an exception once somewhere in the code and allow for division by zero?
Yes, it is worth it and no, it’s not better to use exceptions, but you can rewrite the above as simply
divideSquare x y = square <$> divide x y, or looking at all the function definitions together:
Wow. Isn’t it great - we are using practically the same syntax for both unsafe functions between Doubles and safe functions between Maybe Doubles, and what’s more, we can use the same approach for a lot of other different type functions, not just Maybe a.
TK – some picture that illustrates fmap concept
$ is just function application with lowest precedence, so allows to avoid brackets – without it you’d write
square (divide' x y) – and
<$> is another operator that also applies functions defined for concrete types, but it does so for values built with special class of type functions from these types, e.g. Maybe a or List a - without the need to write nested
case statements. We will look at it in more detail in the next chapter.
In the end, it’s all about making function composition easy - remember Chapter 1 and how to think about solving problems functionally? You break the problem down into smaller parts and then compose functions together, making sure input and output types “fit together”. All the complicated scary terms you may have heard or read about in Haskell - Functors, Monads, Arrows, Kleisli Arrows etc - they ALL are needed (mostly) to make composing different functions easy and concise, so don’t be scared, it will all make perfect sense.
List, Recursion on Types and Patterns
Let’s come back to our card-dealing magic spells, available in the repl here. To (almost) fully understand it, there’s only one extremely important piece missing: List type function and recursively defined types, which are extensively used in functional programming to implement various data structures. If you recall, in Chapter 1 we described List as some manipulation that takes all possible ordered combinations of values of another type and creates a new type from it. Try to define the
List type function yourself before reading further.
Here is how we can operationalize this definition:
Remember how you need to read type definitions as type functions? In pseudocode:
type function List (a : Type) = Cell (x:a, y: (List a)) + Nil() – List a is a type function from the variable
a : Type, or
a : * in real Haskell, that consists of 2 constructors:
Nil, that is itself a value of type List a, and
Cell, that takes a value of type
a and a value of type List a (here is where recursion comes into play!) and returns another List a. Here
Nil is the boundary case of our recursion, and
Cell is a recursive function that constructs a list until it is terminated by
Nil value as the last element.
Let’s construct a list from values 1, 2 and 3. You have a constructor function
Cell that takes 2 values - a value of some concrete type, in this case an Int, and a List of Int. What is the simplest List? Of course it’s a
Nil! So, we can write
Cell 3 Nil - and it will be a List Int! Now, we can pass this list to another
Cell call, like this:
Cell 2 (Cell 3 Nil) - and we have yet another List Int. Apply it one more time, and you get
Cell 1 (Cell 2 (Cell 3 Nil)). Easy, right?
TK – picture of different lists constructed, maybe a tree as well
Basically, if you keep in mind that type functions and constructors are, well, functions, which follow all the same principles as “real” functions, this type building business should become very clear and easy for you.
We looked at the principle of how List a type function can be defined, but since in Haskell it is such a fundamental data structure, it is in fact defined with different constructor names and some syntactic sugar on top:
Nil is in fact
Cell is defined as an operator
:, so that our list of 1,2 and 3 would be written as
1:2:3: or simply
[1,2,3] - much more concise and convenient. You can write
["abc", "hello", "world"] - a value of type List String, or
[1.0, 3.1415926, 2.71828] - List Double, etc.
In the last chapter we introduced the type String as a set of all possible ordered combinations of characters, or simply List Char. In fact, it is exactly how String is defined in Haskell - which is quite logical from the math point of view, but at the same time very inefficient in practice. It’s kind of the same as if we defined our numbers as 0 being an empty set, 1 being a set containing an empty set and so on, and then defined operations of addition and multiplication on top of it etc - instead of using CPU supported ints, floats and operations on them. It would work, and might look very beautiful mathematically, but would be thousands times slower than asking a CPU to compute
2 + 2 via native operations.
In a similar fashion, when you are writing real world programs that do any noticeable amount of string manipulation, you should always use the type Text instead of String. It is represented much more efficiently internally, fully supports Unicode, and will make performance generally better. With lists, the fastest operation is appending an element in the beginning of the list -
x:list. Inserting something in the middle or in the end is a pain that grows proportionally to the length of the list (in computer science we write
To use Text, you should write:
The first line here tells the GHC compiler to treat string literals as
Text. Without it, you’d have to write a lot of annoying String-to-Text-and-back conversion statements. The second explicitly imports the Text datatype for you.
Strings aside, lists are still very convenient for a lot of common tasks, as we will see down the line. Now that we know how to define functions and types, including recursive ones, we have a very powerful toolbox at our disposal already to start building something serious. Let’s practice by defining some useful functions.
Length of a List
Remember this from Chapter 1? Now that you know how a list is built, you can easily write it:
Here we use recursion (length calls itself) and pattern matching: if a
length is applied to an empty list (
), it returns 0 (boundary case for the recursion!), and if it is applied to a list, we return 1 plus
length applied to the remainder of the list.
(x:xs) is pattern matching a specific constructor -
x here is simply the first element of the list and
xs is the rest of the list. It might make more sense if we wrote it via
length (Cell x xs) = 1 + length xs. If you recall,
:) takes 2 values: a value of type
a and a
List a, and creates a list from them. Here we are telling Haskell - if our
length function receives a value that is constructed with the help of
: constructor, take it apart into constituents and do something with them.
We have just defined our first polymorphic function - it works on lists of any type of values! We don’t care what kind of value is stored in our list, we only care about the list’s structure - you will see this as a recurring theme now and again, and this is another powerful aspect of typed functional programming. You define functions that work on types created from other “argument” types regardless of what these argument types are - you only care about the structure that the type function gives to a new type. Just like a “circle” is an abstraction of the sun, vinyl record and a coin, a type function is an abstraction of a lot of different potentially not very related entities. If you already started learning Haskell and got stuck on monad tutorials - this might be exactly the issue, being mislead by false analogies. A circle is not the sun or a vinyl record, but it captures some common quality of both - they are round, even though at the same time the sun is hot and huge and a vinyl record can make you feel sad. The same with Monads - it’s merely an abstraction of some useful quality of very-very different types. You need to learn to see this abstraction, without being lost in and confused by analogies, recognize it as such, and it will all make sense. Just wait till chapter 3.
Map a function over a list of values
Do you recall a mapping example from the last chapter? Here’s how we can define the extremely useful
Type signature tells us that
map takes a function that converts values of type
a to values of type
b, whatever they are, and a list of type
[a]) and gives us a list of type
[b]) by applying our function to all values of the first list. It is likewise defined recursively with the boundary case being an empty list
map gets a value that is constructed with the help of
x of type
xs - remainder of the list - of type
[a], we construct a new list by applying
x and gluing it together with recursively calling
map f over the remainder of the list.
TK – picture of pattern matching and recursion for length and map
Dwell on it a bit, and it should become very clear and easy to use. So much so that you can work on some more exercises.
One other piece of Haskell goodies is worth noting in our card dealing code:
It is called a comprehension, which might be familiar to you from math, and it basically tells Haskell to build a list of Card x y from all possible combinations of
y from the right side of
[Clubs .. Hearts] creates a list of all values of type CardSuite starting with
Clubs and until
Hearts, the same for
[Two .. Ace] for values of type CardValue. You can obviously use the same syntax for Int:
[1 .. 100] would create a list of all values from 1 to 100. You can in fact use this syntax with all types that belong to so called
Enum typeclass - that’s what the
deriving (Enum) statement is about, it makes sure we can convert values of our type to Ints (details about typeclasses in the next chapter). Practice writing some comprehensions yourself - e.g., for pairs of int values, just pretend you want to put some dots on the screen and need to quickly create their coordinates in a list.
Ok, so here’s the full text of the card-dealing program, which you should now be able to fully comprehend:
We looked at how the card deck types are constructed in the beginning of the chapter in detail. Keyword
data is used to define new types and new type functions, as we already learned. Keyword
type defines a so called type synonym. In this case we write
type Deck = [Card], and then we can use
Deck everywhere instead of
[Card] - so it’s mostly a convenience syntax for better readability, not so much useful here, but when down the line you will write
State instead of
StateT m Identity or some such, you’ll come to appreciate it.
instance <Typeclass> <Type name> where ... is used to make a type part of a certain typeclass. We will look at typeclasses in detail in the next chapter, but basically a typeclass is similar to an interface in Java. It defines type signature and possibly default implementation of some functions, and then if you want to make a type part of a certain typeclass, you have to implement these functions for your type. Haskell also provides a powerful deriving mechanism, when a lot of typeclasses can be implemented automatically for your types. In the code above, we are deriving typeclasses
Eq - that allows comparing values of our type - and
Enum - that allows to convert values of our type to Int and we hand-code typeclass
Show to types CardValue, CardSuite and Card. We could have asked Haskell to derive
Show as well, but then our cards wouldn’t look as pretty. Try it out - delete the
instance Show... lines and add
deriving (Show) to all types and run the program again!
Typeclass is just another convenient mechanism to support abstraction and function polymorphism: without it, once you have defined a function
show :: CardValue -> String it would be strictly bound by its’ type signature. Then if you tried to define a function
show :: CardSuite -> String, converting a different type to a string with a function of the same name, our Typechecker would complain and not let you do that. Luckily, there’s a typeclass
Show that has a polymorphic (working on different types) function
show :: a -> String, which lets us work around this limitation. All the power of Haskell in the form of Monads, Arrows, Functors, Monoids etc is implemented with the help of typeclasses.
fullDeck function creates a full 52 card deck with the help of a list comprehension, and
smallDeck is just three random cards thrown together in a list.
main function follows an already familiar logic of break the problem down into smaller pieces and connect functions together making sure the types fit. We are showing the
smallDeck, waiting for a user to press “enter”, and then mapping
fullDeck list to “deal” the full deck.
mapM_ is almost like
map that we already defined - it maps a function over the list elements. The difference is that
mapM_ is constructed differently from
map - even though its’ high-level purpose is the same. We call such kind of manipulation “side effects”. Side effects mess up our cute perfect mathematical world, but real world is messy and all real world programs are about side effects, so we must learn to deal with them!
As we shall very soon see, just like the sun, vinyl record and a coin are all round, Maybe a, List a, procedures with side effects and a bunch of other very useful type functions have something in common as well - something that we will abstract away and which will make writing efficient and robust Haskell code for us an enjoyable and elegant endeavor.
Lift me up!
Recall how we changed this for a function
square x = x * x:
This transformation hints that operator
<$> somehow applies the function
square to any value of type Maybe Double (since that’s what
divide returns) using some sort of pattern matching or
What happens here is that we take a function between values of two concrete types (in case of
square - Doubles, but it can be anything)
b and magically receive the ability to apply it to values of type
Maybe a and return
Maybe b. We can say that we took a function
a -> b and lifted it into
Maybe type function, turning it into a function
Maybe a -> Maybe b.
TK – picture illustrating the concept
By looking at this attentively and thinking hard, we can easily design operator
Maybe like this (note also operator definition syntax):
It takes a function between
b and turns it into a function between corresponding
Maybe a is a type function that you should read as
Maybe (a:Type) = ... What other type functions do we know by now? Of course it’s a List, or
[a]! Can you define operator
<$> that would take a function
a -> b and turn it into a function between corresponding lists -
[a] -> [b]? I know you can. Do it. Do it now.
Good. As they say, one is a coincidence, two is a trend, so why don’t we take it further – what if we had some type function
type function f (a : Type) = ... or, in haskell,
f :: * -> * (a function that takes a type and creates another type from it) that has different constructors, just like Maybe or List – can we define operator
<$> for it? Something like:
We want this operator, just like in case of Maybe and List, to take a function
g :: a -> b and turn it into a function that is lifted into our type function
h :: f a -> f b. Let’s write out full signatures in our pseudocode to make sure we are clear on what means what. Operator
<$> takes a function
g (x:a) : b (takes a value of type
a and returns a value of type
b) and turns it into a function
h ( x : f(a:Type) ) : f(b:Type).
TK – a picture of a Functor
Congratulations, you just invented a Functor. A Functor is merely any type function
f :: * -> *, like Maybe a or list [a] that has operator
<$> defined, which “converts” or lifts functions between two concrete types –
g :: a -> b – to functions between values of types constructed from
b with the help of our type function
h :: f a -> f b. In Haskell, Functor is a typeclass - more on this in a bit in Chapter 3.
Why do we need functors? So that we can write
g <$> lst and be sure our “simple” g function works on complicated values constructed with some type function – instead of resorting to verbose boilerplate nested
case statements for each new type we define. Ah, yes - if you wrote operator
<$> for list above you should have noticed that’s it’s merely the
Most of the confusion in Haskell stems from the fact that the concepts here are named almost exactly as they are in category theory, which is about the only actively developing area of mathematics nowadays, cutting edge of the most abstract of science. I mean, why not call this an elevator or injector or something less scary than a Functor?! But it is what it is: really really simple elegant concept named so as to confuse us simple folk.
Let us open the floodgates!
Chapter 3: I Wanna Be FAMIOus!
Classify Me, Baby, Am-ma-mo-noid
TK – picture of typeclasses - a bunch of types together combined into a couple of different typeclasses