Haskell 101

Hello, everyone. Welcome to Haskell 101. My name is Antoine. I’m a Cloud Bigtable
SRE in Dublin. And I use they/them pronouns. Welcome. So you’re trapped in this
room for three hours with me. So what’s the point of today? Well, Haskell is known to
have a steep learning curve. So other people have tried
to learn the language on their own. And you might have realized
that there is a lot to cover before you
are able to write your own first hello world. So the point of this 101 is
to help you get started– as in, I’m not try to
cover all the things you need to know in
order to be able to write your own programs. So the way, this is structured. I have roughly an hour
of slides and an hour and a half of exercises
that could be asked to do the notes before the session. The point is to
make you write code, because that’s the only
way to make any progress. There is quite a
lot of you today. But please do ask questions. Please do interrupt me. Please do ask questions. The best sessions are the
ones in which a lot of people ask questions because I can talk
about more things than what is covered by the lesson itself. So with that, let’s begin. So I said that
the point of today was to help you get started. So this is what
I’m going to cover. I’m going to talk about what
makes Haskell what it is, all the concepts that are the
core of the language, which is going to be mostly a
functional programming 101. I’m going to talk
about the syntax, because the syntax of Haskell
is quite different from what you may already know– how
to read function types, how to read the thing. Data structures,
what do they look like in a purely
functional language? And at the end, how do we
write our own functions? So this is what we’re
going to talk about today. This is what we are not
going to talk about. I am not going to talk about
anything related to project environment, like what’s Cabal? What’s Cabal hell? How do you avoid it? Should you use
Stack or Stackage? What’s the difference? All of that I’m not going to
talk about, mostly because it’s boring, as in it’s
just project management and build management,
and that it’s not what makes the language interesting. I’m also not going to talk about
anything related to Haskell at Google, Haskell in Google 3. And the reason for that
is there is already some very good resources put
together by the Haskell team regarding how to write
Haskell at Google. There is the Haskell code
lab at go/haskell-codelab, which is all about writing
Haskell code at Google. It has only one
drawback, which is it requires knowing
the language, which is what we’re trying to do here. I’m also not going to talk
about the advanced stuff. I am not going to
use the F word. I am not going to
use the M word today. And the reason for that is those
things are in the language, those infamous things
are in the language, because they solve
a practical problem. But if you have never faced the
practical problem they solve and if you’re not used to read
the weird syntax of Haskell, it’s just going to look
like abstract gibberish. And I know because I’ve tried. The very first
version of this lesson covered everything which
is in 101, everything which is in 102, all the
way up to the M word, and I try to fit
that in two hours. My four teammates went through
this, and I’ve promised them I would mentioned their sacrifice
every time I [INAUDIBLE] 101. So yeah, you need to first be
used to the syntax and see what problems you face
in this language before you can see
the use of the M word. Yeah? AUDIENCE: [INAUDIBLE]. ANTOINE LEBLANC:
Perhaps towards the end. The thing is, you
actually don’t need it to be to start writing
your own programs. So I might talk about it a bit. Not today. Clearly not. So that’s the topic for today. The prerequisites, I’m assuming
programming knowledge from all of you because I’m going
to compare Haskell to a lot of other languages, mostly
C++, Python, Go Java. And of course, if you already
know a functional language– if you already know
[? Ocamel, ?] for instance– it’s going to be easier
for you to follow. And you will need to
install the compiler and the Haskell platform to be
able to compile the code lab and do the exercises. If you have installed
the Haskell platform, you now have GHCI
on your computer, and GHCI is your
new best friend. So GHC is the Glasgow
Haskell compiler. It’s the one true
compiler for Haskell. It’s the only one we use. It’s so ubiquitous
that its nickname is the glorious Haskell compiler. And GHCI is the
interactive version. It’s the rebel for Haskell. And you can use it for almost
anything– inspect types, look up the type of
functions, type expressions, see them, debug your
code, step in it, like profile code, everything. So basically, opens
GHCI whenever you start writing anything in Haskell. You can even open it and
try typing the stuff which is on the slides. It might not always work,
but could be interesting. So let’s begin. What’s Haskell? Well, if I read
the slide, Haskell is a strongly statically
typed, purely functional, lazily evaluated general
purpose programming language. That’s quite a mouthful,
so let’s break it down. I think two of those I
don’t need to explain. General purpose is something
you all know what it means. It’s important to stress
because some people have this idea that Haskell is
only good at background computations,
scientific computations, crushing numbers,
that kind of stuff. And sure it’s good at that,
but it’s not only good at that. It’s also being used for video
games, window environments, front end servers,
back end servers. It’s a general purpose language. It can be used for
anything you want. In the same way, I think
strongly statically typed, it’s not something
I need to explain. It’s one of the main
features of the language, but it’s not one I
need to explain to you. I think all of you know
what those words mean. However, purely functional
and lazily evaluated are the interesting
ones, and the ones I’m going to talk about. Before that, this
is what Haskell is. Let’s talk about what it’s not. Firstly, it’s not
a silver bullet. This thing here,
those three hours, are not a way for
me to bring you into a kind of
cult or something. I am not trying to give
you fuel for flame wars. I am not trying to
say Haskell is better than all the other languages and
you can forget all the others. It’s a tool. It’s a language. It has upsides and downsides. I just happen to like it. The other thing is, you might
have heard this legend of, you need to have a PhD in
math and know category theory to be able to write
anything in Haskell. And that is simply not true. It’s true that it borrows a lot
from IDs from category theory, but you don’t need to
know category theory to write Haskell. Of course, if you know
one, learning the other is going to be easier. But again, you don’t need to
know one to learn the other. I mean, and the
proof of this, I know nothing about category theory
and here I am teaching Haskell. So yeah. And last but not least,
clearly, Haskell is not hard. You might have heard it’s hard. It’s not. It’s just extremely
different from everything you already know if you only
know imperative languages. If you only know
imperative languages, you’re going to be stuck
at hello world, which is kind of frustrating. But it’s not because it’s hard. It’s just because it’s a
completely different way to approach programming. A few years ago,
there was a poll in which people that
write code for a living were asked to rank languages
in different categories and Haskell ranked
first in two of them. The first one was learning
that language changed the way I program in other
languages, and the other was learning that language
made me a better dev overall, because it makes you learn a
completely new way to approach programming. So what does it mean to
be purely functional? Through the slides,
I’m not going to try to go too deep in theory. I’m going to try to stick
at the programming level. What does it mean
for you to write code for a language like
Haskell to be purely functional? Well, to start with,
everything is a function. It’s not object oriented. We don’t have inheritance. We don’t have all those
classes and stuff. I mean, we have data
structures and functions. So far, it’s fine. We’ve all written
some C and survived. So the idea of having
only functions and structs is something we kind of know. The syntax, we’re going
to talk about it later, but it kind of looks
like the syntax of math. On the right, you have
the mathematical function f from the set of all integers
to the set of all integers. That’s to an integer x,
associates the integer x plus 1. On the left, you have
the Haskell version that takes the function f and
takes an int, returns an int. And f of x is x plus 1. So pretty similar. We’ll talk about the
exact syntax later. So purely functional means
everything is a function. So far, so fine. Well, it also means
everything is immutable. If you know C and C++, it means
every single thing you use is const, no exception. If you look at this example,
I’m saying let a equals 3 in a equals a plus one. And that thing
doesn’t even compile. It’s not that it doesn’t
compile because I’m trying to assign n plus 1 to a
and if I were to try to assign it to b it would work. It’s because this assignment
operator doesn’t even exist. When I say let a equals 3,
it’s a mathematical truth. So trying to say a equal
a plus 1 would be absurd. When you create something,
it never changes again. You never mutate
anything in place, which also means if
you have a big struct and you want to make
a modification to it, you have to create an
entirely new struct that [INAUDIBLE] modification. That sounds completely
inefficient, but we’ll talk about
performance later. So OK, we have only functions. They can never mutate
anything in place, which means we only transform
data and create new variables instead of mutating anything. That’s kind of weird, but OK. Let me crank it up one notch. Everything is an expression. If you think about
it, to have loops, which is the usual
control flow thing, we need to have variables,
things that change over time. Since everything ensconced,
well, we can’t have loops. And indeed, we don’t. We have only recursion. There’s no loops in Haskell. And to go even further,
there is no statements. You used to have
statements line by line, separated by semicolons. That’s not the case here. Here, the core of your function
and the body of your function is an expression. That’s all it is. So the if construct of Haskell
is itself an expression, like the ternary
operator of C++, or the weird value if condition
else of the value of Python, which means we can assign
the result of an if. You can do transformation
[INAUDIBLE].. And if you’re
thinking, well, that lets a equal something in
something construct, that’s a statement, right? Well, nope. That’s an expression, as well. Of course, saying let b equals
2 in b is completely useless. The point is just
to showcase you can use that let’s
in construct anywhere you have an expression,
because it is an expression. Even the switch case
statement is an expression. So purely functional
so far means we have only functions
all the way down. They never mutate
anything in place. And everything is an expression. We have no loops. We have no usual control flow. That’s kind of weird. But this slide is
not finished yet. There is one more thing. We have no side
effects in Haskell. What does that mean? Well, it means if you
look at this function foo, its type means it takes
an int, returns a string. Having no side effects means
it cannot write to database, it cannot reach from data input,
it cannot depend from some global mutable state because
there is no such thing as a global mutable state,
which means it has some very interesting properties. Since it cannot depend from
anything outside of it, because there is no such thing
as side effects or mutable state, it means if you call foo
twice with the same argument, you will get the same
value of it twice, which means testing
foo is trivial. You cannot forget to initialize
something outside of it because there’s not a thing. If you refactor
code that uses foo, testing that refactored code
behaves just like before is trivial as well. It makes reasoning about code
and testing your code trivial, which is great. We love that. There is just one
drawback, though. We kind of like side
effects at some point, because if our programs are just
able to compute stuff in memory but are never able to
read from the comment line or write to a file or something,
they’re kind of useless. And the thing is,
I’ve lied to you. It’s not that we don’t
have side effects. We do. But when we do have them,
they are explicitly stated. If you look at this
function, readFile, it’s part of the default
function, the prelude module, which is always
loaded by default. And readFile, the type
informs you what it does. It takes a path to
a file and returns the contents of the file,
which is something which is full of side effects because
the file might have changed between two calls to
the function or the file may not exist. But you can’t guarantee
that coding it twice would give you the
same result all of it twice, of course. But if you look at
the type, the argument which is the path to
a file is a string. But the output, the content of
the file, is not the string. It’s an I/O string. When you see types separated by
spaces, think of I/O of string, it would be brackets in C++. I/O is a generic type, and the
string is its type arguments. So it’s an I/O of string. And what’s I/O? Well, I/O is a special
type given to us by the language and the
compiler and has one very important property. Every single side
effect is an I/O, which means that if you have
codes that don’t use I/O, that doesn’t touch I/O, we call
these pure because it still has all the benefits I mentioned. Code that is outside of I/O
does not have side effects. If you call a function twice
with the same argument, you will get the
same value twice. Testing it is easy. Refactoring it is easy. Same thing. However, as soon as you
enter the I/O realm, well, you’re in
the impure realm. And side effects might
happen, but at least they’re restricted to this I/O part. Yeah, sure. AUDIENCE: Was I/O a part of the
result type and not some kind of namespace for the
rates training function? ANTOINE LEBLANC: Basically, it
works kind of like a container, as in it wraps your
value to contain– to limit what you
can do with it. And since you can only
access stuff within I/O, we have a very specific
set of functions which are provided to you,
but you can’t extend it, and forces at compile time
that you can only do what you’re allowed to do with I/O. Basically what this
means is that when you write your own programs,
the core logic of the program is usually pure. Like, you do all
your business logic in pure code, which means
you can easily test, easily refactor it, easily
prove assertions on your code, which is nice. And the outer layer,
like main, is impure, and connects your logic,
your core programming, to the outside world. This idea is not completely new. If you think about it, in
object oriented languages, the pattern of
dependency injection is kind of similar, in
a way, as in your logic, your module, is
completely independent, knows nothing about
the outside world, completely testable
in isolation. And your outer layer connects
it to the rest of the world by injecting the dependencies. It’s kind of the same idea here. The core of your logic is– the
core of your program is pure. The outer layer is impure. The main difference
is this logic here is enforced by the compiler. And the way it
does that, what I’m trying to say with pseudo
mathematical notation here, is that we have
functions provided to us that take something which is
not in I/O and put it in I/O, take something pure
and make it impure. But there is no function that
takes something impure and make it pure. We can never get out of
I/O. So think about it. Pure is a strong requirement. Pure means there was no
side effects involved in making this value, while
impure means they may or may not have been side effects. It’s a lack of requirements. So taking something
which is pure and saying it meets a lower
bar is easy, is doable. Taking something which
is impure and pretending it meets the strict requirements
of being pure is impossible. If that seems weird to
you, think about the member functions in C++. When you write a
member function in C++, you can mark it as const. If you do, so you’re
telling the compiler this function will not mutate
the state of the object, which is a strong requirement. If you do so, you cannot call
non-const member functions. Even non-const member
functions that would not mutate a state of the object
because that would violate the requirements you’ve asked
the compiler to check, which means if you have to call a
non const number function, then your non-const
number function becomes non-const as well. I/O is the same. I/O corrupts. If you’re writing
a function and you have to call something which
is in I/O, since the result you will get is in I/O that you can
never extract that stuff out of I/O, it means the
result of your function will also be in I/O. OK, roughly, so far? We are not going to
cover much of I/O today. Most of the exercises
of 101 are going to focus on only pure code,
getting used to the syntax, because dealing with the
I/I is its own thing. So that’s basically what
it means for a language to be purely functional. Let’s talk about laziness. I mentioned that Haskell
was lazily evaluated. So what does that mean? Well, basically what
is on the slide, as in we are used when you,
in most languages, for stuff to be evaluated right away. For instance, in
Python, if I say a equals a gigantic computation,
the [INAUDIBLE] is performed. The result’s stored in memory. And that part of the
memory is named a. And if I print A, it doesn’t
need to compute anything, just reads A from
memory and prints it. In Haskell, not so much. If I do a equals a
gigantic computation, it returns immediately. And then when I
do print a, well, now it needs the value of a,
so now it does the computation and now it prints a. Everything is deferred
until it’s actually needed, which has the
interesting side effect, if I may say so, that something
which is not used will end up not being computed. One of the main
drawbacks of laziness is that it’s super weird. We are not used to thinking
of computation that way. We are not used to have
to think of everything being delayed and deferred. However, there is one
thing, one basic thing, which is the same in C++,
in Java, in Go, in Python, in bash, even– the same in all
those languages which behaves kind of lazily by default, as
in it defers some computations until they are actually needed. And it’s the same in
all those languages. Can someone guess what
exactly, because that’s not the core part of the language,
and it differs from language to language. I’m thinking about a thing
which is literally the same in all of them. Yep? Sorry, by a what? By a conjunction, do you mean,
like Boolean operators or– yep. That is absolutely the
answer I was expecting. We’ve all written that kind
of stuff in C++ where we test whether a pointer is null. And if it’s not null, some
condition on the value inside the pointer. If that end operator
were a normal function, both arguments would
be evaluated and passed to the function. And it would crash every single
time the pointer is null. The only reason
why this works is because it short
circuits, which means if the first part
of the and operator is enough to complete the
results, it does not compute. It does not evaluate
the second part, which means the evaluation
of the second part is deferred until it
is actually needed. Think of this logic
of short circuiting of waiting until we actually
need the thing to compute it, apply it to every
single function, and that’s what Haskell does by
default, which I know is weird. So let’s talk about the
pros and cons, because I’ve been saying it’s weird. I’ve been saying it’s not
intuitive, and I think it is. So why do we want it? What are the pros and
cons of having laziness by default in a language? Well– oh, sorry. I forgot I had that slide. I always forget it. I try to keep light on
theory, but basically, in most languages, eager
languages in which evaluation happens immediately, when
you call the function, arguments to the
functions are computed and then the function is called. In lazy languages, first
you in line the function, and then when you need them
you evaluate the arguments. So the pros and
cons of laziness. Let’s start with the cons– memory pitfalls. As a beginner, it’s something
that’s going to hurt you. Since laziness makes memory
usage a bit harder to predict, at some point you
will try to reduce on the gigantic list of things. But you will forget that
your accumulator during the reduce is actually itself lazy. So instead of having
an accumulator that is getting updated while you go
through the list you’re trying to reduce, your accumulator
is just a gigantic expression which is growing in
memory and you end up with a stack overflow. There are, of course,
ways to avoid this. But as a beginner,
it’s something you will see at least once. The thing is, some purists
deem that Haskell is not a true lazy language because
it’s not always lazy. It’s just lazy by
default. We have ways in a language to say,
I want this thing here to be strict, because
I know what I’m doing and I know I want to avoid
a cycle of flow here. And usually, the
way you approach programs is to let
laziness do its things, because most of the time
it does great things. I’m going to cover that later. But sometimes, at
some precise points, you want to make
things non-lazy. May need to avoid that
kind of memory pitfalls. The other kind of pitfalls
as a beginner you will see is parallelism pitfalls,
because imagine you have a bunch of
computations to perform. You spawn 10 threads. You do all the computations. You join. You print. But you forgot that
the whole thing is lazy and when you do the print is
when the computations actually happen. What your friends did was just
to create the expressions. Whoops. Of course, the way to fix
this is to use those escape hatches we have in the
language to say, well, I want that thing to be
strict here in the threads to make sure it happens
when you want it to happen. Basically, we can’t
force the evaluation to happen when we need it. But by default, it just waits
until the last possible moment. OK, I’ve been talking
only about the [INAUDIBLE] weird, non-intuitive, and
the pitfalls for beginners. Why do we want laziness? What’s the good
that’s coming of it? So my slides read
huge optimizations and it’s quite an
understatement. Basically, laziness is
not the strong guarantee that the compiler will
wait until the very last possible moment to
compute your expression. It just means there is no
strong guarantee as to when the computation will happen. It will just happen before
you need it, probably at the last possible
moment, which means the compiler– it gives
the compiler a lot of freedom. The compiler is able
to rearrange your code to make the computation happen
wherever it’s efficient, because it doesn’t need
to compute it immediately. So I’ve been talking
about the fact that when you have a gigantic
struct you need– if you want to make a change to it, you
need to make a copy of it, because we never mutate
anything in place, right? Well, in an eager language,
that would be horrible, because we would create lots
of copies of a struct which would have to be
committed in memory because computations have
to happen immediately. But here in Haskell, if
I have the function that creates a struct
and then modifies it 10 times, by the
end of the function, only returns a
field of the struct and that function is pure
and has no side effect, well, the only thing that
matters is the field. And since the compiler
is not required to make the computations
happen immediately, what the compiler can do
is inline all your code, remove everything, never
commit the struct in memory, and just generate the
equation which generates the field that you want. That’s all. And remove everything else. So basically, the compiler
has a lot of freedom thanks to laziness because
it removes most of the constraints that are
associated with computations in other languages. And basically, purity and
laziness work together. As in laziness–
sorry, I’m just going to finish this and
take your question. Laziness gives the
compiler a lot of freedom, and purity informs the
compiler, as in purity gives the compiler
so much information to know what [INAUDIBLE]
doing that it has both the information and the liberty
to tier through your code and optimize it in a way. Yes? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Yeah. In practice, it
really does that. And you will have– like, one of my
favorite examples is one of the first chapters of
a parallel program in Haskell, same example of
spreading mutable threads and forgetting about laziness. The author of the book spawns
several thousand threads to compute Sudokus, and at
the end of the functions just prints the length
of the list of results. The compiler realizes that the
length of the list of results is the same length as
the list of inputs, removes the entirety
of the code that does all the
parallel computations and prints the correct
results without spoiling a single thread. Optimize all your code
away because the compiler is able to verify that
the result you want only requires that small
computation and none of all the things you’ve written. The compiler will tear
through your code. In the end, Haskell is
quite a fast language. I wouldn’t say it’s a
selling point, like you want row performance use Haskell. But it’s pretty fast. It’s in the same ballpark as C
and C++ rather than being close to Python. And the thing is, I’ve been
saying like purity and laziness work together,
because both of them inform and let the compiler
choose what it wants to do, and optimize your code heavily. But it also works
the other way around. Laziness enables
purity, as in, we get all the benefits of
purity without having to pay a huge performance
cost for them, because again, in the legal language, having
to make copies of structs all the time would be horrible. And the other– yeah, sorry. Yes, go ahead. AUDIENCE: So can you spell– because everything is
computed, everything that you can compute
at compile time is computed before
compile time– ANTOINE LEBLANC: More because
the compiler has such freedom and so much information that it
can optimize your code heavily, because again, in
C++ for instance, if you have the function
everything’s void, you can’t just remove the
function call entirely because you never used
the function result, because it might
perform side effects. But here, if you never used
the result of the function, you can just remove
the code entirely. Yes. There used to be a
way to compile it to C and see what the C
generated code looked like. Usually not really. Performance tuning and
inspecting what your code does is another subject entirely. Yep. AUDIENCE: Question, so what is
the team behind the compiler? Is there lots of people
Yeah, it’s mostly– the thing is, there
is just like C++, they like new versions
every 10 years or something. But since GHC is
the only compiler, the team that works on it
has a lot of new features that keep happening. Like, there’s serious
work being done on it. And more interestingly, in
the last five years or so, at the FP complete foundation
has been doing a lot of work towards making Haskell
more mainstream and more enterprise-oriented. And they’ve changed the entirety
of the package ecosystem. It used to be only Cabal
and Cabal was a mess. And they’ve released Stack
in the last three years, more or less, which is great
and works perfectly well. They’ve really used
the new editor modes for most of the common editors. They’re working on
a new IDE for it. They’re working on
clinging some old packages. There’s a lot of work being done
towards making Haskell a better language. So yeah, it’s well-maintained,
heavily supported, and actually increasing in
size rather than diminishing in size. Yeah, there was another
question, I think? No? OK, perfect. So there’s one last thing,
one last bonus of laziness. There’s a few
theoretical results regarding eager evaluation
and lazy evaluation. One of them which is interesting
is that as long as you have good caching you will have not
more reduction steps between your evaluation and lazy
evaluation, but a more fun one, and sometimes useful, is
that there are things you can express in lazy languages that
you cannot easily express, or sometimes not express
at all, in eager languages. And one thing we get
to express easily in Haskell that would be harder
to express in eager languages is infinite structures. What this silly example does–
and again, it’s very silly, but it’s mostly for fun– is on the first time I’m
creating the infinite list of all the numbers, all of
them, the infinity of them. It’s the infinite list
of 0, followed by 1, followed by all of them. And this returns immediately
because we do not need to compute the list right away. We have the expression
that generates it. That’s good enough. In Python, generating
the list of all integers would take quite some
time because there is quite a lot of them. This is big ints, not integers,
so it grows to infinity. On the second line, I’m
creating the infinite list of all the numbers squared. And I’m doing this by applying
the function to the power of 2 on the entirety of all
the infinity of numbers. And something it returns
immediately because we do not need to compute
anything right away. And the third line, I am taking
the five first squared numbers, but taking the five
first does not require computing the entire list. So this works. If you have tried
typing this [INAUDIBLE] and you have tried evaluating
one of the infinite list, well, then [INAUDIBLE] has
to evaluate the entire list and is now shouting
numbers at you and [INAUDIBLE]
control to stop it. So that covers mostly the
functional programming part, what it means to be
purely functional, what it means to be lazy. Let’s talk about function types. So those are the red slides. Those are the most
important slides of today. You can forget everything
I’ve said before. Forget everything that
comes after, as well. Those slides are the
only one that matter. If you remember one
thing from today, remember this slide, because
this slide is about how to read function types. And since everything in
Haskell is about functions, if you know how to
read function things, you’re mostly good to go. So we’ve seen
function types before. I’ve used– the colon
colon operator in Haskell is used to mean the thing on
the left, the name on the left, has the type on the right. It’s used for two things. It’s used for declarations,
when you declare something new, or when you have an
expression which is ambiguous and you want to tell
to the compiler, I want it to be of this type. So in the slides I
use it quite liberally to mean getting the same thing. The thing on the left has
the type on the right. So here we have a function f
whose type is int, arrow, int, arrow, list of int. The bracket is the
built in list type. Of course, in
actual Haskell code, you would type dash
angled brackets. But I have it prettified
out for my slides. So we’ve seen the four functions
that have an inputs and output. They have only one arrow. Here we have two
arrows does that mean that this is a
function that takes a function as an argument? Is it a function that
returns a function? Is it a function
of two arguments? Or is it on two things? Why do you think this is? What do you think
this type means? There are two different
answers I will accept. AUDIENCE: A function
that returns a function that’s [INAUDIBLE]. ANTOINE LEBLANC: Yes. That is one of the
two good answers. I would also accept
a different answer. Yeah? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: It’s indeed
a function of two arguments. So how can both be
true the same time, being a function of two
arguments and the function that returns a function? Well, the name Haskell
comes from a guy, a logician, Haskell Curry. And his first name
was used for language. His last name was given to a
thing he theorized, though I’ve seen some people claim that
he was not the first one to theorize it, but history
has remembered his name. And clarification is
the idea that in math, a function of
several arguments can be expressed as a chain of
functions of one argument, as in a function
of two arguments can be expressed as a function
that take one argument and returns a
function that takes the second argument, which
itself returns the end result. And that’s the way
functions are implemented in Haskell under the hood. Of course, the
language allows us to think of functions such as f
as a function of two arguments. And you will hear me talk
about functions of two, three, four arguments all the
time because it’s easier for us to reason about them that way. But under the hood,
every function only takes one argument, which
is why the arrow for functions is take one thing,
output one thing. What I’m trying to say is
saying that f takes two int and returns a list of int and
saying that f takes one int and returns a function
from int to list of int, as far as the
compiler is concerned means the exact same thing. The compiler will not
distinguish those two lines. They mean the same thing to it. OK with that more or less? What we gain from this– except from having only arrows
because all functions take only one thing and
output one thing– is we get partial
application for free. Since function that look like
they take several arguments actually only take
them one at a time, it means we can give the
arguments one at a time. So f takes two arguments,
but I can call f on only one. So function
application is space. You don’t need to surround the
arguments with parenthesis. So if I call f on one, well,
I just gave only one argument to f. And the type of this
expression, f of 1, is function from
int to list of int, which means I can use
this expression, f of 1, as a function itself
and call it on 2. And I would get the list of int. But again, since
the language allows us to think of f as a
function of two arguments, I can just write f 1, 2. And that’s what I
would do in most cases. If that helps– if it
doesn’t, you can ignore this– the function arrow is
right associative, a space. The function application
is left associative. Is that clear for everyone? Yes. AUDIENCE: What about
zero arguments? ANTOINE LEBLANC: Well, it would
be constants, more or less. You just evaluate the
thing by calling its name. Like, if a is an
int, you could see it as a function of zero arguments. Any question on this? This is the most
important slides. We will stay on this
one until everyone has asked all of their questions. Please do ask questions. You’re all fine? Yes, go ahead. AUDIENCE: [INAUDIBLE] that
I wanted my first argument be a function. ANTOINE LEBLANC: We are going
to see that in the next slide, but basically your
surround– you surround the arrow
with parenthesis to make it explicit. We’re going to see
it in the next slide. OK, perfect. No other question? You’re all fine with this, this
idea of functional [INAUDIBLE] one argument? We can give them
over time, and so on? Fine? Well, perfect. It’s time for a quiz, then. I’m going to show you
some function types. And I’m going to ask a
volunteer to explain to me what the function type
means and what would be a good name for that function. I’ve seen people
already guessing names. If you are already
guessing names, it means you’re already in
the answer, and it’s not you I’m interested in asking. Just as more
information, when you see lowercase letters
in function types, they’re type parameters. You can think of
this as template type and a typed language. A main difference
between C++ and Haskell– I mean, one of the
main differences– is if you write a template
function in Haskell that expects any type name a, you can
depend on some properties of a, like being able to be
default constructed or being able to be
compared for equality or being able to call plus
on the value of type A. And you should only
require to declare it. If you just try to instantiate
that function type a, it doesn’t meet requirements,
it will just fail to compile. In Haskell, not so much. If we require something
out of the type A or B in this function, it
needs to be explicitly stated at the type level. Here, there is no
preconditions whatsoever, which means this function here
works for absolutely any type A, any type B. We know
nothing about those types. Maybe we can’t
[INAUDIBLE] and maybe we can’t default construct them. Maybe we can even
instantiate them. Maybe there is no possible
value of those types. We know nothing about that. So someone who doesn’t
[INAUDIBLE] guess yes? It’s [INAUDIBLE]. Is that clear for everyone? OK, perfect. Good session today. Perfect. So yes, the first argument
is a function from A to B. This is how you would take a
function as a first argument. You surround the function
in these parenthesis and surround the arrow
function with parenthesis. I hope it answers your
question more or less. So yeah, the first argument is
itself a function from A to B. The second argument is a
list of values of type A. And the end result is a
list of values of type B. And what this function does– I mean, of course, you could
create such a function that ignores the two first arguments
and returns the empty list. But yes, the most commonly known
function that has this type is map. And what it does is transform
the list of A’s and a list of B’s by applying the
transformation function on every single element. Yes? AUDIENCE: I’m guessing
the answer is no, but I’m asking anyway. Is there a way to express
further constraints and the [INAUDIBLE],, such
as, for instance, the return list probably has the same size
as the second argument list? ANTOINE LEBLANC: So you
can express the type level constraints on the types,
not on the values, by default. So it’s saying, I require
type A to have such methods. Yes. Saying that list must
have this given size, which is a constant
in the value, no you can’t, by default.
There are language extensions, which are non-standard, that
give the ability to express such conditions at
the type level– I mean, at the comment
level, more or less. And then the
compiler checks them, but it’s completely non-standard
and not covered in today. There’s a thing called
liquid Haskell, which allows you to prove assertions
on the values themselves instead of just proving
assertions on the types. But it’s completely
non-standard. It’s fascinating, though. I recommend checking it out. OK, so if you’ve
all guessed not– this one is going to be
trivial to guess, right? Sorry? Yes. It is, indeed, filter. Is that clear for everyone? This is a function that
takes as a first argument a function from a to Boolean,
takes a list of a’s, and return the list of all the A’s
that passed the predicate. Of course, it could be also
filter not, but bear with me. Again, the point
of the slide is not to make you guess what
function do magically. It’s to make you practice
reading function types. At this point in the
slides, I am sorry to say, I have to talk about
the curse of Haskell. There is a curse which
plagues beginners, and even experienced developers. In Haskell, you can
create your own operators. And sadly, sadly, people do
create their own operators, which means you have
to reuse some code, some of it written
by you, that contains horrible operators
which are completely unreadable, because you can. And because you can,
doesn’t mean you should. But you can. And people will. So there is a lot of operators
in Haskell code in the wild. And I’m going to use these
slides to make your guess two of the most commonly
used ones, because you will need to know about them. Because if you try to read any
kind of source code in Haskell, you will see them. So the difference between
operators and functions in Haskell is just the name,
as in operators are just functions. The compiler treats
them as functions if they contain letters. And the compiler treats
them as operators if they contain symbols. That’s all. If you want to use an
operator as a function– to give it as an argument
to another function, for instance– you need to
surround it with parenthesis. That’s also the case when
you declare its type. So if we were to declare
the type of the $ operator, which already exists, we
would have to surround it with parentheses, which
is what we do here. Can someone guess
and explain to me what this operator
does based on its type? Sorry? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: That is right. If you see it as a
function of two arguments, it takes a function from A to
B. It takes a value of type A and returns a value of type
B. And since we know nothing of the arguments, the
only thing it can do is apply the function
to the value. If you see it as a function
of one argument that returns a function, it
takes a function from A to B and returns a
function from A to B. We don’t need dollars. We apply functions to values. We have seen the
space to do that. So what’s the point of dollar? It looks completely
useless, right? Well, it’s syntactic sugar. Let me show you an example. Here in this example, I’m
trying to apply the function fun to the sum x plus y. Since function application has
the highest priority and binds first, if I were to remove the
parenthesis in this example, it would be fun of x plus y,
instead of being what I want, which is fun of x
plus y, which means I have to surround the
argument with parentheses to make sure it
gets computed first. But the thing is, Haskell don’t
like parentheses that much. This is Haskell, not Lisp. We can use dollar
to remove them, because basically dollar is
simply function application, but with the lowest priority. So everything on
the right of it is to be computed as an argument. Everything on the
left of it is going to be computed as a function. And then the
function on the left is going to be applied to
the argument on the right. It is simply syntactic sugar
for functional application without parentheses. It is used absolutely everywhere
in Haskell code, which is why you need to know about it. It has one nice
property, though. If you’re calling
several functions on the result of the
previous function, if you use parenthesis, you will
have five or six parenthesis, closing parenthesis at
the end of the line. If you use dollars,
you just have a chain of proper functions
from right to left, but still. OK with this? We’ll see a lot of it
during the code lab. Yes? AUDIENCE: [INAUDIBLE] one
plus two and both functions again use two
some point, there is only a few limited
things that dollar can do. We’ll see– I mean, the best
way to answer your question is, I think, to wait
for the code lab, because you will see
how to use this function and how to use dollar. And we, again, show you
some examples of this. Yes? AUDIENCE: [INAUDIBLE]. ANTOINE LEBLANC: Not
completely, sadly, because of those
pesky parentheses. But you can remove a
lot of them already. Usually when it’s not
the last argument, we can’t, because dollar is used
for a function and an argument, which means it can only be
used for the last argument of the function. So you can not remove
all parenthesis. A lot of them, though,
but not all of them. The other operator I
want you to try to guess is the dot operator,
which is completely unrelated to the dot in
object oriented languages because, again, this is not
an object oriented language. Can someone guess
what this does? There is a formal word
for it, but I would accept any non-formal word. Yeah? Composition is indeed the
formal word I was expecting. OK, good class today,
which is great. So indeed, this takes a function
from B to C, a function from A to B. And what it does is
return the new function, which combines both. We talk about function
composition and we take an A and apply the functions and
give you a C at the end. The point of this is we
can create new functions by just combining existing
functions without having to use lambda
functions or declare new functions explicitly. For instance, we
have seen filter. But if you want to try
to filter at list to keep the elements that do not match
a predicate instead of having to introduce a
new predicate that does the opposite
of the other one, or do a lambda that is
not the other predicate, you can just say
not dot predicate. And it composes the functions
together and gives you something that’s return
true if the element does not match the predicate. Why it’s named dot
is because it’s inspired by the circle operator
of math where f circle g of x is f of g of x. And basically what I mean is,
if you have a function show that takes some stuff,
returns a string, you have length which is a
function that takes a string and returns an int. If you compose them by
saying length dot show, it’s going to– this expression itself is a
function of type take a stuff, returns it. OK with this? Basically, both with dollar
and dot, we build pipelines. We are able to say, well,
apply this transformation. Then apply this transformation. Then apply this information. And so on. And yeah? AUDIENCE: [INAUDIBLE] combine
the dot and then dollar sign? ANTOINE LEBLANC: You could. One thing you could
do, for instance, is create the chain of
functions on the left hand side of the dollar
operator, have the dollar, and then apply the argument
to this chain of functions you’ve just created. However, you could also just
have a [INAUDIBLE] of dollars. It’s uncommon to combine
both, but it might happen. Again, we’ll see examples
of this during the code lab. And if that idea of, we
build pipelines of changes by chaining functions,
transforming arguments, seems weird to you, well,
if you think about it, things that take only one
input and return one output and chaining them to
create better programs out of simple functions
that do one thing and do one thing well,
it’s kind of a thing we do every day, more or
less, except pipes in bash go left to right and both dollar
and dots go right to left, which I know is [INAUDIBLE]. But that’s basically the idea. OK with this? Those were the red slides. Those were the important slides. You can forget everything else. And since you’re absolutely fine
with reading function types, well, there’s one more quiz. This one I do not expect
everyone– except, well, this is a good class
today, so most of you might guess what this
function actually does. But the point is not for
you to guess what it does. The point is just to make
you practice reading function types again. Can someone explain to me
what the function type means? You don’t have to explain
to me what it does. If you do, it’s perfect. That’s not what I’m expecting. Just expecting someone
to read the function type and explain what it means
to me, because again, being able to read
function types is the most important thing. Go ahead. Mm-hmm. But what does a
function type mean? OK. Go ahead. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: That
is a way better answer than I was expecting. This is, indeed, a
very good class today. Yes, the first
argument is a function that combines an a
and a b into a new a. The second argument is
a, initial accumulator. We have a list of values. And what fold L does
is left to right it combines this initial
a with the first b using the function we have provided,
which creates a new a. It combines a second a
with the second b, which creates a third a,
and so on until we have been through the list. It is, indeed, reduce. Again, if you haven’t guessed
what it does based on the type, it’s fine. I was not asking this. It was just to make you practice
reading function types again, because again, being able
to read function types is the most important
skill we learned today. OK, so done with function types. Let’s talk about
types themselves. There is a lot to say about
type theory of Haskell, but I’ve promised I would
stay clear of theory. So let’s see some actual
concrete examples. First, we have type,
the type keyword, which is basically typedef,
and a weak typedef at this. So here I am saying that
type point is simply a tuple of two ints, which
means a function that expects a point will also gladly
accept a tuple of two ints. A function that accept
a tuple of of two ints will also gladly accept a point. It’s a weak typedef. We can say the same
thing with lists. A polygon is just
a list of points. And interestingly,
unlike C++ before C++ 11, we can have templates typedef,
if you allow me to say that– I mean, to phrase it that way,
as in I can say the type map has two type arguments, k
and v, and the map of k and v is just an alias for a
list of tuples of k and v. That’s not the most efficient
way of representing a map, but just to show you that
I can use such a type alias decoration to
then use map of int to string or map of
string to anything. OK with this? OK. So that’s not very interesting
because it’s just type aliases. How do we create
actual new types? Well, before talking about
this, let’s think of it. What does it mean to be
a data type in a language which is purely functional
and in which we have no member functions because we have
no inheritance, no classes, no differentiation, anything. We have no setters because
we never mutate a thing after it has been created. We have no private members
versus public members, because again, no
objects, really. What do we have? What matters in a type
in such a language? And the answer is– sorry, I wasn’t asking
for input on that slide. Sorry, I should have
made that clear. But if you have a suggestion– AUDIENCE: Naming? ANTOINE LEBLANC: Name
is important, yes. AUDIENCE: [INAUDIBLE]. ANTOINE LEBLANC: Not exactly. The only thing that
matters is constructors, as in how do we
create the value? Since after it’s created, it’s
never going to change anyway, the only thing that matters
is how do we create it? And to go even further,
since the compiler has complete freedom as to how the
thing is represented in memory, or even not
represented in memory, the question is not
even how the layout is. The question is, what
makes an expression a valid expression of the type? So the way we do
declare the data types is by listing the
constructors which are either constants or
functions that create an expression of our type. Let’s see some examples. To create new type,
use the data keyword. And the way you do this
is to say data and then you give the name of the type. And then, after
the equal sign, you list the name of the
constructors and the arguments, if it takes some arguments. So here we are
seeing the type none, which has only one
constructor, name none, which takes no arguments. It’s a– what’s the word? It’s a convention
when you have only one constructor in the type to give
it the same name as a type. But you are absolutely
not forced to do this. So here, what we’re saying
is that the only way to create an
expression of type none is to call the none expression,
which doesn’t take arguments, which means the only possible
value of type none is none. The type looks completely
useless, and indeed, it is. It could be used to represent
the lack of information, because if a function
returns you a none value, you know it’s only going to
be none because it cannot be anything else. And that’s kind of how the none
type in Python is implemented. The only possible value of
type none type in Python is the constant none. So let’s see a bit more
of an interesting example. Constructors can take arguments. So here I am saying the way to
create a value of type Minutes, the type Minutes, is to call
it its only constructor, which is also named Minutes,
which takes an int. So minutes, despite
being a constructor, you can see it as a
function which take an int and returns an expression
of type minutes. And minutes 42, would be a valid
expression of type minutes. This kind of type could be used
if you have a datetime library and you want to make sure that
every function takes minutes or seconds or hours
instead of just taking int and have people make
mistakes using it. So again, this gives
you no information about the actual
layout in memory. It just tells you minutes
42, easy valid expression of type minutes. How do we get the
42 out of minutes? We’ll see that in
the few next slides. So that’s it. This is the way we declare
a constructor which actually takes arguments. Let’s see a type that takes
more than one constructor, because we have seen only types
with one constructor so far. The Boolean type, a Boolean
type– a Boolean value can be created only with the
two Boolean constructors, which are the two constants
false and true. I hope this surprises
no one so far. But basically, yes
it means whenever you encounter a value
of type Boolean, it has been created with one
of the two constructors, which means there is no such
thing as a null value. If you have a Boolean,
it cannot be null. It’s going to be
always false or true. So we have no null pointers. There is no such thing as
you expected false or true and it’s actually null,
then your thing crashes. So how do we represent the fact
that we might not have a value? Well, we use, I think, what
is the most interesting type of [INAUDIBLE] today,
the maybe type. C++ used to have boost optional
until I think it’s C++ 14 they introduced std optional
instead, inspired by [INAUDIBLE] optional. But that’s basically
the same thing. An optional value may or may
not contain a value of a type. And this is the same thing here. This is a generic type. You can see that it
takes a type argument. It’s a maybe of a. And since there
is no precondition of a, that a can
be anything, can be ints, strings, lists
of lists of lists of ints, anything you want. And the expression
of type maybe a is either constructed with
the nothing constructor, which takes no argument and
therefore wraps nothing, or with the just constructor
that takes an argument and therefore wraps
a value, which means if you want to construct
a value of type maybe int, nothing is a valid way
of constructing it. Just 42 is also a valid
way of constructing it. And whenever you encounter
in your code a value of type maybe int, it’s either
nothing or just an int, which means it is
an optional value and you will have to handle
the case of the missing value explicitly because you have to. We’ll see how to use
that in a few slides. Yes? AUDIENCE: These words– nothing,
just also true [INAUDIBLE]?? ANTOINE LEBLANC: What
do you mean, sorry? AUDIENCE: So these are not
keywords of the language, so you could– [INAUDIBLE] ANTOINE LEBLANC:
Yeah, absolutely. You are completely free to name
those constructors as you wish. Of course, the Boolean type
and Maybe type already exists. But if you were to recreate
them, you could try a maybe 2, in which the constructors
are named Foo and Bar and it would do the
exact same thing. And the thing is,
of course you can have the same name of the
constructor between two different types. That’s the only thing. I mean, at the very least,
not in the same module. So if you have
already a type that has a constructor
named nothing, you can’t have a constructor
named nothing and another type to create. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Yeah, exactly. I mean, none is a silly
example I’m showing, but yes. If nothing didn’t exist, I
could have made it nothing. But since nothing already exists
and is a construct for maybe, I had to choose another name. Yeah. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC:
Oh, they’re just me using the colon colon
thing quite liberally. They’re not part
of the declaration. You don’t need to declare them. They are just me showing what’s
the type of the things are. So nothing is a
valid value of type maybe a for any a,
just the constructor is a function that
takes an a and returns something which of type maybe a. And just 42 is an
example of maybe int. AUDIENCE: So the
first two [INAUDIBLE].. ANTOINE LEBLANC: There would
be, but not for declarations because you don’t declare
the constructors explicitly– you don’t declare the type
of a constructor explicitly. They are derived from
the type declaration. Yeah, well except you can
[INAUDIBLE] the lowercase, uppercase things is
meaningful in Haskell. Types have to start
with uppercase. Constructors have to
start with an uppercase. And type parameters,
like the a of maybe a, have to be lowercase,
and normal functions have to start with a
lowercase, as well. But assuming you have
this restriction, yes, you could declare nothing being some
kind of maybe a, and nothing with a lowercase n, for
instance, just written the maybe n, which
is a written nothing, would be a valid way of
declaring a function. We’ll see more [INAUDIBLE]
when we start writing functions and [INAUDIBLE]. Yes, of course. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Yeah,
the way my [INAUDIBLE] for the slides works is it
transforms all the values and constants it knows
being part of the language in green and all the
types it knows being part of the language as
blue, which gives you a strong hint as to which
types I have made up and which types are actually
part of the language. So nothing, the
type of nothing, is maybe a, which means
for any type A, whether A is int or
strings or anything, if you were an
expression, a function expects a maybe something,
you can give it nothing. Yeah. OK so far? One last example, the list type. Let’s imagine we want to build
a very simple linked list type. How do we express
this in Haskell? Well, an expression
of type list of a, for again whatever a there is. We don’t care but we
stored it with an artist, is either nil, the empty list,
or a cell contains a given value, and the rest of the list. The cell constructor takes
two arguments, the value, and the rest of the list,
which can itself be either nil and we have reached
the end, or a cell that contains the value and the
next element of the list. So nil is a constructor
which is a valid expression of type list of a. Cell– the constructor
is a function that takes two arguments,
the current value, the rest of the list, and
returns an expression which is itself a valid list with the
value appended at the beginning instead of at the end. And cell 0, 4 by cell
1 followed by nil is a valid example of
a linked list of it. Of course, we can use dollars
to remove the parentheses. So why am I showing this
weird linked list type? Because this idea of we
append values at the beginning is kind of weird. This idea of the cell
constructor that takes two arguments is kind of weird. Why am I showing this to you? Well, first because
it’s interesting. It should generate type that
has two constructors, one of them being a constant,
the other being a function. Whose arg– one of
the arguments is also the same value as the type. And also because that’s the
way the built in list type is implemented. This actual line,
this fifth line, would not be valid syntax,
because the bracket syntax is reserved by the compiler. But if we open our mind
a bit, what I’m saying is the type list of a that
you will see in the code is either the empty list,
empty brackets, or the column operator, because
yes, operators can be constructors,
which appends a value at the beginning of a list. So empty brackets is an empty
list for any type of list. Column is the constructor
that appends a value at the beginning of a
list, take a value, a list, and just appends them. So 0, colon 1 colon the empty
list will be a valid list, but of course we will
write it 0 comma 1. The syntax of list
is super weird, which is why half of
the exercises we’re going to do today are
going to be about lists. OK, basically with
this idea of we list constructors
which should give us the list of ways we can create
a valid expression of our types, if that’s OK I’m going to
how we actually use them. OK so far? OK, so one more thing before I
move on to actually using them, sometimes what we want is
just a good old C struct. We don’t care about
having many constructors. We just want one constructor
and a list of fields, because sometimes that’s
just all we need, right? So we could just use this. I’m saying user has
only one constructor, which is also named user, which
takes a string and an int. So the user constructor would
take a string and an int and return a valid
expression of type user. The thing is, we don’t
know what the string is. We don’t know what the int is. We don’t know yet
how to access them. And there is, thankfully,
a struct like syntax that allows us to just write this. User is still the same. It’s still a simple type that
has one constructor, user, that takes two arguments,
a string and an int. But here we name them. And this does two things. One, it makes the declaration
a bit more readable, and also it creates
two functions for us, user name and user age,
which are kind of getters. They take an
expression of type user and they extract
the field out of it, which is also why I’ve named
them user name and user age. They are created in
the same namespace, and I didn’t want to overload
the name and the age names. OK with this more or less? We’ll see examples in
the code lab again. Yeah, absolutely. You can have functions as– what do you mean? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Oh, no,
I mean you could always– we’ll see pattern matching
right after [INAUDIBLE].. You can always access the fields
without ending the functions. But when you name the fields, it
just creates a function for you to extract the field
out of the object. So if object itself,
the field is itself a type that has fields,
you could call then the function that extracts the
field that you want out of it. You can just change,
with dollars, the different
extraction functions until you get the
thing that you want. OK, so let’s talk
about actual functions, because I’ve been talking for
roughly an hour at this point, and we have still written
not a single function yet, which reminds me I wanted to
showcase some examples of how the actual one argument thing
works, but since all of you seem fine with it, I think it’s
fine if I didn’t show this. Too bad. OK, so let’s write
some functions. How do we write
functions in Haskell? Well, first we start
by giving their type. This is optional. I think the compiler is able
to figure the type by itself. It doesn’t need your help. However, if you write
a bunch of functions without ever giving the
type and if you just let the compiler infer the
types for you, and at some point you use all of these
functions together, if there’s a type mismatch
because we did something wrong somewhere,
the error will be when you use them because
they’re incompatible together, which doesn’t help you much. However, if you mark the type
of every single function you write, when you make a
mistake, the compiler will be able to pinpoint
where you made the mistake. So it both makes the
code more readable and it makes the compiler
able to give better error diagnostics, which
means it’s a Warning to write the function
without writing its type. Some IDEs are smart enough
to just run the compiler, parse the warning, and insert
the function type for you, because again, the compiler
is able to figure out the type just well. There’s just– for
the code itself, it’s better to write a type. So we do write the
type of the function, and then we write
its implementation. So here we are
writing not a function that takes a Boolean value,
returns the other Boolean value. So what is the null of x? How do we actually
write the code? Well we could use an if, right? I could say if x
then false else true. But that’s kind of ugly. A thing we can do is we can
write several implementations of our function. We can write several
expressions to be used. And what we can do
is we can choose which expression to
use based on and how the value x was constructed. We know that x is
a Boolean value. We know that the Boolean type
has two constructors, which means there are only two
possible values for x– true and false. So we can use pattern matching
and then write the two cases. Not in the case where
the argument is true it is false, not in the
case of when the argument is false we can strip. OK with this? Pretty simple, right? Let’s imagine the and
operator doesn’t exist. Of course, it does. But let’s imagine it doesn’t. And let’s re-implement it. So first we declare its type. It takes two Boolean values,
returns a Boolean value. What is x and y? Again, we can just write ifs
and say if x then if y then true else false, else false,
that’s disgusting. So let’s not do this. We know we can do
pattern matching, right? So let’s do pattern matching. False and false is false. False and true is false. True and false is false. True and true is true. And that’s quite verbose
and not much better. However, what we can
do is we don’t need to list every single pattern. Patterns are tested in
order by the compiler, which means what we can do, we say,
well if true and true matches, then the answer is true. If it doesn’t, fall
to second pattern. And if it’s x whatever x
is and y whatever y is, the answer is false. There is one minor drawback
to this version, though. It does not short
circuit, because to test whether the first
line matches, it needs to check whether both
the arguments are true. But the thing is, we don’t
need to much explicitly all the arguments. We can also write, well,
true and y is just y, as in if the first
argument is true, the answer is just the second
argument, whatever it is. And we can defer the evaluation
until the y is actually needed. And if we don’t match
that first line, whatever matches on the second
line, we don’t care. Whatever is true and false,
false and false, false and true, we don’t care. It’s just going to be– the
answer is going to be false. Yes? AUDIENCE: It’s false? ANTOINE LEBLANC:
Yeah, of course. Yeah, it’s a true as a
possibility, but yeah. X is never going to be true. We could write false
here instead of x. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: It would
change almost nothing. I mean, if you prefer, yes. There’s nothing
wrong with doing it. There’s just one more thing. In most programming languages,
declaring an argument, giving it a name,
and then not using it is a warning because
you’re giving a name and then you don’t use it. In Python, the convention
is to prefix the name with an underscore to mean I
know this argument needs to be here, but I’m not using it. In Haskell, underscore
itself has a special meaning. You can have more than one
underscore per [INAUDIBLE] 9, and underscore
means I don’t care. And if you don’t use it,
like if you’re giving name to those arguments
you’re not using, the compiler is going to give
you a warning of you named it but you don’t use it. Underscore means I don’t
care where this thing is. You cannot use underscore
in the expression, which means you’re discarding
the value, whatever matches, I don’t care. OK, roughly, with
[INAUDIBLE] matching? Yes. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Not really. The compiler will not
generate a line for you, which is all the
arguments with underscore, because you still need
to specify what happens in that case, what
is the written value, so the compiler is
not able to say, well, I will insert the
cache all in the [INAUDIBLE] function. The compiler will,
however, give you warnings if you do not match
all the possibilities, as in if your function matches
true but doesn’t match false, or for more interesting types
doesn’t match one of the cases, the compiler will give you
a warning of your function does not have an output
for all its input values. AUDIENCE: [INAUDIBLE]. ANTOINE LEBLANC: It will give
you warning, yes, like, hey, you’ve named it
and it’s not used, just like C++ would give you
a warning of argument not used in the function. Then you have to either comment
it or remove it completely, where Python would do–
like, a [INAUDIBLE] would do the same for an
unused arguments unless you prefix
them with underscores. Kind of the same thing. You name something,
you don’t use it, maybe something is weird. So let’s see other
examples of where pattern matching is useful. I have talked about
this minutes type. It’s a simple thing. It has one constructor,
takes an int and wraps it. How do we get the
value out of it? Well, let’s take
a small example. You’re writing an
add function that takes two value of type
minutes and adds them, computes the sum of them. It returns a new
value of type minutes that just contains a
sum of the two values. So how do we add two values
of type minutes, mx and my? Well, we could try mx plus my. But if we haven’t
made our type minutes, what would be the operator plus? That’s too material. So we can’t do this. The thing is, we know that
the value of type minutes was constructed with the
only constructor of minutes, which is, itself, minutes. So we can use pattern matching,
even though there’s only one pattern, because we know
that the first argument was constructed by using the
minutes constructor on something that we will name x. And the second minutes
arguments was constructed by using the minutes
constructor on something we’ll name y, which means we can
just return the results, which is minutes of x plus y. And of course, we can use dollar
to remove the parenthesis. OK with this basically? Pattern matching allows us to
choose implementation based on the values of our arguments. It also allows us to
deconstruct the arguments to know how they were
built and to access the fields inside them. One last example, length– because again, the syntax
of list is super weird, and the more you’ll
see it, the easier it’s going to get
for you to read them. So again, lists are either the
empty list, empty brackets, or a cell, which is a value,
column, the rest of the list. Let’s write length. We want to write
length, which takes a list of any A. We don’t care. And there’s an int, which
is the length of the list. So we know that the
value of type list is either the empty list or
a list containing some value for the rest of the list. So we just write
the two patterns, length of the empty list is– so one said one once– is indeed zero. And length of a list which is
made of the element x appended at the beginning of the
length of the list xs is– indeed. You’re a good class. It’s easy for you. And yes, that’s how
we do things on lists. We pattern match whether
the list is empty or not because list,
just like any other type, has two constructors. Yes? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Sorry, it’s– AUDIENCE: I have a list. I can length a
of the time, yes, it’s going to be cached, yes. Depends on how much
the compiler knows that you’re trying to compute
the length of the same list. But yes, if you guys
will cash it, yeah. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Yes. Your competition is not
terminated because the compiler doesn’t know enough. If it needs to try
to compute the length to compare it to 42,
however, what you could try is to take the first 42 elements
and try to see if that has 42. You could try such a thing. But just try putting length
on the infinite list, yes, will never terminate, sadly. And I think that’s all
mean, you can’t just do it by calling
length on the list and then comparing
the results to 42, because calling
length would take an infinite amount of time. However, going through the list
and stopping at the [INAUDIBLE] and saying [INAUDIBLE] more than
42 is fine, because that thing doesn’t require going
through the entire list. And that’s what I have
for you in the slides. I’m going to show you
a quick links for you, and then I’m going to take
a quick break in which I can answer all the
questions that remain, and then we’ll
start the exercises. So links I have for you, I
have two questions [INAUDIBLE].. So the first, the slides,
if you want to have them are at go/haskell-101-slides. If you want to try a
GHCI in your browser because you don’t want to
[INAUDIBLE] on your computer for some reason,
try tryhaskell.org has a GHCI in the browser. If you prefer to read
books, well, there’s three of them I
would recommend– “Learn You a Haskell,”
which is written by someone that has a background
in imperative languages. So it’s very oriented
towards you know C++ or Java, here’s how Haskell works. It’s a pretty good book. It has a few
problematic examples. But if you ignore those, it’s
otherwise a pretty good book. “Real World Haskell”
is a great book, also. I really like it because every
chapter has a small project with it that you can
download and try. And every project is
not an abstract thing, like re-implements
[INAUDIBLE] numbers or like weird containers. It’s an actual useful thing. So each chapter
shows you how to use the things you’ve learned in
an actual useful way, which is nice. And the Haskell
book is pretty new. I haven’t read it yet, but all
the reviews I’ve seen so far are extremely good. So I put it in
the slide as well. And the last thing is Hoogle,
and I have to show it to you. So as you can imagine, Hoogle
is a search engine for Haskell which allows you to
search for stuff. Like, if I want
to search length, well, I would get that length
takes a list of A’s [INAUDIBLE] and is defined in both
prelude and data.list. But Hoogle has one
more feature which makes it absolutely amazing. You remember that maybe
type I mentioned before, which is the optional type. So if I have a maybe int, I
may or may not have an int. If I want to extract an
int out of a maybe int, I need to provide some
kind of default value, in case there is nothing
in the maybe int. Well, what function does this? Let’s imagine I
have some maybe int. Oops. I have an int and
I want a function that combines both
and gives me an int. Well, there’s from maybe. It takes an A, a maybe A, and
an A. The from maybe function takes a default value, a
maybe value, and so on. Hoogle can search by type. And for beginners,
this is a blessing, because I have those two
things, how do I combine them? Search for type which takes
those two things and returns what you expect and you will
get all the functions that match what you search for. That is just– Hoogle is amazing. And with that, I think it
concludes the slides part. It’s 11:20. Let’s say we’re going to
start the exercise at 11:30. And in the meantime, I
can take your questions. You had a question? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC:
to showcase the minutes thing that we extract– we use pattern
matching to extract the value of the constructor. I think it was the thing
I wanted to showcase. Oh, so yes, no, this
was something else I wanted to show. I wanted to show this in GHCI. Is it big enough? Is it big enough, or do
I need to make it bigger? I wanted to show– I completely forgot
I usually show this. I usually show
that we can create an add function that adds an
x and a y, and adds of x and y is just x plus y. And I’m going to
make this an int because I don’t want to
deal with generic functions just yet, so that it declares
a function of two arguments, even if under the hood it’s
only a function of an argument. So the type of ad is just
takes two ints, returns an int, and adds 4 and 8 is 12. But the thing, is since adds
only takes one argument under the hood, I can
completely create add 5, which is a function add
partially apply it to 5, and the type of this is–
sorry, I can’t type– function from int to int. And add five out of six is 11. Because what happens
under the hood is that I’ve declared add
as being a function that takes two arguments. But as far as the
compiler is concerned, it’s exactly the same thing. It makes no difference,
as adds being a function that
makes one argument and returns a lambda function– [INAUDIBLE] backslash, because
backslash kind of looks like lambda– which takes y and will
return the x plus y. This declaration where ad
only takes one argument and returns the function
is the exact same thing and the compiler sees
absolutely no difference. That’s the thing I wanted
to showcase which I forgot. But since most of you are
completely OK with math filter and everything, I think
that was OK for most of you. And anyway, we’ll see
that during the exercises. Yeah, sure. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Yep, this one? AUDIENCE: [INAUDIBLE]
So we define the dollar type as they are full of holes. What happens that– ANTOINE LEBLANC: Oh,
makes it what if if? AUDIENCE: Yeah, like
how does this type– ANTOINE LEBLANC: Yeah. Basically, the Boolean
type is pre-defined. Like, I’m showing its definition
that it already– of course already exists. The compiler knows about it
and expects the arguments to the if– to be of type Boolean. That’s very specific Boolean
type that already exists. AUDIENCE: So [INAUDIBLE]. ANTOINE LEBLANC: It’s
not exactly a function. It’s more of a– it’s
actually a keyword. There’s a [INAUDIBLE]
of keyword in Haskell– if then else is
actually a few of them. But it requires, I think,
to be a type Boolean. You cannot give an int and
expect that int to be converted to Boolean. There is never implicit
conversions in Haskell– well, never is a strong
word, but almost never implicit conventions,
and never to Boolean. Yeah? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: You’re saying– AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Haskell, no,
it’s clearly a Boolean value. It will not try to reason
anything about the type. It’s Boolean value of nothing. The two cases I know where
there is implicit conversion performed is from
integer literals, like if you take zeros
and think it can convert to any of the number
types it knows, either int or integer,
which is it begins. That is kind of an implicit
conversion rate’s fine. And the other case is when
you enable a specific language extension you can convert
string laterals to one of the different string types. That’s the two only cases I know
where an implicit conversion is performed. And it’s from a literal. So it doesn’t matter much. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Usually fine. AUDIENCE: You just
made [INAUDIBLE].. ANTOINE LEBLANC: Exactly. Otherwise, I don’t
think I know of a single implicit conversion. So if you have done the code lab
file and you have unzipped it, whether on your laptop
or in your workstation, you will see that it contains
a code lab file, a main file, and a solution file. If you compile it using make
or build, it will [INAUDIBLE],, it creates two binaries. One of them is the
solution binary, which runs the tests on
the solution file, which contains the same
thing as a codelab file but with a solution. Don’t peek into it. That ruins the fun. So of course, all the
tests on a solution file should pass, which confirms
that installation is correct. And of course,
running the code lab binary will run all the
tests on the code lab file. And of course, all of them
will crash because we haven’t implemented anything yet. If you open the
code lab file, which is the one in which
you have stuff to do, it explains to you
how to test your code and how to compile it. You can either run make and
run the code lab binary, or if you prefer
and that’s actually the way I would recommend
you do it, you can open GHCI, do the magic set thing– that’s
because I do horrible things in main, don’t worry about it. Load the code lab. Load main. Column L is to load something. Just run main, run tests. And [INAUDIBLE] is the way
to recompile something. It reloads all the things
that had been loaded before. So if you have made changes
to the code lab, just type [INAUDIBLE] if it will
reload the things, and just run main
again to run the tests. The code lab is
divided by section. Section zero you have
nothing to do in it. It’s just to do a setup. I introduced the code lab
thing, which is of type A. So it works anywhere. But it uses the
built in error thing, which just panics the
program if evaluated, which means every time the code
will try to evaluate something named code lab, it
will crash, which is why all the tests fail. It starts with
section one, which is about deconstructing lists. All of the exercises are the
form I give you a function, I give you its
type, and I– oops. Sorry. Don’t have a look. I forgot to unzip the– unzip– codelab.zip. Oops. The file that I was showing
to you contains the solution. Where is– OK, we’ll need
to redownload it because– OK, let me– give me one second. go/haskell-101/codelab,
which downloads a zip file, which I’m going to move here. Oh, because I’m in
the wrong folder. That’s why. OK. And hopefully– no,
that should be– sorry. I still need to
unzip codelab.zip. OK, yes. And now– yes, there
is no more the solution in the codelab file. Perfect. I can show you the section one. Codelab’s putting the answer. So the way this works,
exercise is mostly I’m giving you a function. I’m giving you
[INAUDIBLE],, what it does, and I ask you to implement it. It’s divided by section. There’s four sections in total. Feel free to move
onto the next section if you’ve already finished. There’s some bonus
things for people that go faster than the others. What I’m going to do
while you write code– while you work
and I do nothing– is I’m going to roam the room
and look at your screens. Beware. And the point is, please do ask
me all the questions you have. If you’re blocked on the thing,
please do ask me for help. The point is for you to
try to write your own code. And every now and then I will go
back here and give the answers to the [INAUDIBLE]
questions and showcase different elements of syntax
that I didn’t want necessarily to show during the slides. If you have questions
on the setup, if it doesn’t compile
for you, if you are lost, please do ask me. I will try to show– for the section one, not much– but I’m going to try to
show more interesting things like several different
versions I’ve seen. For instance, for
null, I’ve seen several people try–
not today, but I’ve seen people try it–
saying, well, null of l is l equal equals the empty
list, which is interesting, right? Because it could work. It could be– well, if it’s
equal of the empty list, it’s true. Otherwise, it’s not
true and it’s perfect. Except this doesn’t work. And the error message here
will be super cryptic. So let me explain why
this doesn’t work. The equal equal operator,
to work on lists, I mean, is only defined on lists if the
type A inside the list also has the equal equal operator,
because you cannot compare lists for equality if you
cannot compare the elements for equality, which means if you
wanted to implement null that way using equal equals, we would
need to say at the type level, actually, a has equality since
we’re using equality on lists. Here, we’re not saying
that a has equality. We don’t know if it has. Maybe it has not. Therefore, we cannot
use equal equal, even just to compare
with the empty lists. So what I was expecting
here is, of course, to use pattern matching. Null of the empty list is true. And null of a list
which, again, the pattern is written right
here, is a value x followed by the
rest of the list xs. It’s a convention another rule. If you are matching the
pattern of the cell containing the value in the rest of the
list, if you name the value x, you name the rest of the list
xs, x plural, if you will. It’s a convention. You’re going to
have to follow it. Of course, if we
match this, which is the other
constructor, then false. Of course, we
don’t use x and xs. We can just use underscore,
instead, for both of them, because we can use more
than one [INAUDIBLE].. And we don’t even need to
match the pattern because we know that if we didn’t
match the empty list, we know this is the
only other pattern. We actually don’t care about it. We can just use underscore and
say whatever the best list is. If it didn’t match the empty
list, then the answer to null is false. So head is an interesting one. It’s considered by
design, but it’s here for historical reasons. It’s what we call the
partial function, which means it doesn’t have an
output for every single input to the function. For some of the
input, it crashes. It chooses the error thing
to just panic your program. So head of the
empty list panics. We usually dislike
partial functions because we dislike this
idea of your code can crash. But this is how it was
implemented historically, so I kept it that way
for the exercises. So [INAUDIBLE] doesn’t work. What’s the other possible
way to construct the list? So what’s the other
possible argument– it possible case for
an argument to head? It’s a list that
contains some x followed by the rest of the list that
we actually don’t care about, because since head returns
the first argument, the first element of the
list, head just returns x. And finally, tail, tail
is the exact same thing, as in it panics
on an empty list. And tail of something
which is not empty, which has some elements
we don’t care about, and the rest of the list,
is the rest of the list. Some people think that tail
returns the last element, but it’s made obvious it’s
not the case by the type. It returns a list
of a, not an a. Let me just check I didn’t
make mistakes for section 1. It’s unlikely, but for the
rest it will definitely happen. OK. That’s it for section 1. Oh, where’s section
two, recursion? So length, I’m not going
to spend a lot of time on it because it
was in the slides and most people go
back to the slides and copy it from the slides. So I will have a lot of
interesting things to say. Length of the empty list is 0. And length of– some
people have tried something which I find interesting. It’s not wrong by any means. It’s just not what
I was expecting. To say, well, for a given this
L, which we know is not empty, it’s one plus length of tail of
l, where we remove an argument. It’s perfectly fine. It’s just, I wasn’t
expecting this, but it works. It just uses tail, which
I always find a bit icky because we can just hear– oops, sorry, I can’t type– we can here explicitly
match the fact that we know it’s a
cell that contains a value and the
rest of the list. And then it writes 1 plus
length of the rest of the list. The tail version
is perfectly fine and I have no problem with it. It’s just not the
one I was expecting you to write because the
point of those exercises is to make you practice
pattern matching on lists. And I’ve made a typo here. That should work. So and and or, there’s
two different ways to implement them. I want to showcase both of them. There is one that I prefer. But again, it’s up
to you to decide which one you think is better. So there is, of course,
we have to choose– we have to match the empty
list, because again, we have to have a base
case for our regression. And n of the empty
list– so is it supposed to be true or false? The way I reason
about it– and I don’t know if theoretically
it sounds, but something which is true for every single
element in the list is true, then when there
is no element in the list, something which is true for at
least one element in the list will not be true
for an empty list. So end of the empty list is
true and or of the empty list is false. So what– whoops. Sorry, I can’t type. What some people choose
to do for and and or is not to write the second
pattern as a generic pattern but to much explicitly
what Boolean value we have in the
list, and say, well, if the first value
is false, we don’t care about the rest
of the list because we can stop the recursion
immediately and return false. Otherwise, if we have
something else which has to be true as
a result, then we can take the rest of the
list and go recursively and say it’s end of
the rest of the list. This works perfectly
fine, but you are doing pattern matching on
the first element of the list through recursion. Another version, which I
would personally find better, but it’s completely up to
you, is to actually match the generic gaze– you may have noticed I’m not
a native English speaker. And the first time I give this
lesson, I named them b and bs. I have been told bs means
something else in English. I don’t care. Would be to say, well, how
do we combine b itself, which is a Boolean value,
with the recursive call of or on the rest of the bs? Well, we use the or operator. And since it short
circuits, then if B is true, it’s not going to compute
the rest of the recursion. I find this one slightly
better because it takes– it’s slightly shorter,
and still is [INAUDIBLE].. But which one you prefer
is completely up to you. And finally, you
can get [INAUDIBLE].. You need a few more
minutes, or you OK with me spreading the answer? I think that silence
is a yes, you’re OK with me spreading the answer. So concatenation, the
trick is, again, we are creating a new
list because we never mutate anything in place. And the way we create new list
is by using the colon operator, because yes, it’s
an operator, which is a constructor,
by appending values at the beginning of a list. We never append on the
end of a list, which means we are going to append
stuff at the beginning of L2 instead of appending stuff
at the end of L1, which means we don’t need to break down L2. We absolutely don’t. The recursion we
need to do is on L1. So there is two possible
cases, either L1 is empty or L1 is not empty. In the case where L1 is empty,
well, the answer is easy. It’s L2, right? In the case where L1
is not empty, well, we know we’ll have to append
that x at the beginning of the results that
we’re going to do. It’s a recursive
function, right? And what’s the rest of the list? What’s the rest of
the concatenation to which we append that x? Well, it’s simply a
recursive call of xs. The rest of list one
concatenated to L2. This goes recursively
through L2, and then appends the element
of L1, one by one, back to L2. OK, perfect. So section three,
higher order functions. Let’s start with map. So map takes a
function from A to B. A list of As returns
a list of Bs. So far, so fine. If we have an empty
list, we have no value on which to append a function. And transforming an empty
list into a list of odd values will still be the empty list. No surprise here. So how do we apply a function
f on the non empty list? Well, if we trust the types,
f is a transformation function that takes an A,
transforming into a B. So if we apply f on an a
element, we’ll get a b element. We don’t take things
in place, so we have to create a new list. The way we create a new list
is by using the colon operator to append values at
the beginning of lists. And then what’s the
list to which we want to append that new b value? Well, it’s the recursive
call of map itself with the same
transformation function on the rest of the list as. OK so far? Since function application
binds first always, we can use the operator here
without needing parenthesis around the arguments,
because that’s thing is going to be complete first– I mean, [INAUDIBLE]
with laziness, but in terms of
operator precedents, this is a higher priority,
and this is a higher priority than the operator itself,
because function application binds first. So in filter, we– Yeah, of course. Sorry. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Oh,
you’re just saying– AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Oh, yeah. Full [INAUDIBLE],, using–
implementing map [INAUDIBLE] is non-trivial,
choice, yes, in this case. But– AUDIENCE: The question
is [INAUDIBLE],, so I’d have to find
another function that just takes one [INAUDIBLE]. ANTOINE LEBLANC: You could use
it in that function probably, no? Like, you could probably
write map of f and lf. Never tried to write
it as a folder. So lets me try to
improvise here. I mean, it’s going
to be a full r. The base case– so the
combination function is going to be a
lambda, which takes the current value of the
list and our accumulator l and appends f of a
at the beginning of l. The base case is going
to be the empty list. And I’m going to
name it different, so as not to be
confused with the one we have an arguments
to the function. And the list on which we do the
recursion is going to be– it should look like
something like this. I’m not sure this– let
me check if this works. To be honest, if it
works I’m super happy. It compiled. No, it doesn’t work. Why doesn’t it work? Oh, because it uses fold,
which I haven’t committed yet. Of course. But yeah, I wasn’t expecting
you to write it using fold. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC:
Yeah, absolutely. This is something I’m
going to talk about later. But yes, you could absolutely
define it that way. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Well, map
is something you would never implement because it already
exists, but in this case, I would definitely
go for this version. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Oh, that
I’m going to mention later. But my recommendation
is choose whatever makes the code more readable. And in most cases– not always, but in most cases– naming the arguments makes
the code more readable. When you’re dealing on
lists, yeah, of course, the list argument is a list. You name it l, it
doesn’t add information. Maybe you can omit it. But otherwise, naming
arguments is always better. And then it proceeds
to the others. So filter, I introduced
the guard syntax because pattern
matching is nice when you want to know how the
value was contracted. But sometimes you want to do
some more interesting tests on the value you
have on your hands. So what the compiler
does is the same thing as for pattern matching. It tries all the
guards one by one, and saves the first one for
which the expression evaluates to true, otherwise it’s just
a constant of type Boolean whose value is true. You could write true
instead of otherwise, or one is greater
than zero here. Like, anything that evaluates
to true would be the same. But otherwise, it’s
just more readable. For once, we have chosen letters
instead of symbols for Haskell, so that’s nice. So what’s the case we want here? Of course, filtering
an empty list is going to always be the
empty list, because there is no element to filter. So we have two cases when we
encounter some x in the list in our regression. Well, either x passes our
predicate f, or it doesn’t. So if I type f of x here, what’s
going to happen is if f of x is true the compiler
is going to select this implementation of filter. Otherwise, if f
of x was not true and we fell down with
that line, the compiler is going to select this line. Both of them are going
to be mostly the same, as in we need to go recursively
through the rest of the lists. We need to call filter
on the rest of the list. So if both of them are going
to have filter of f on xs. There is one key difference. In the case where x
passed our predicate f, we want to append
x at the beginning of that list on the
way back to reconstruct a list that contains x. OK with this? Finally, fold l and fold r. OK, so if you’re
lost with those, the hint I was giving to
people is trust the types. Some purists hate
me for saying that, but sometimes just
making something that compiles by trying to see
how you can make the types work together leads you
towards the right answer. So here, what we
want is to combine the accumulator, the
original accumulator, with the first
element of the list and then pass it as
the new accumulator for the next argument, for
the next element of the list. So, well, first we
have an empty list. What they want to
return is, of course, the accumulator,
which means we have reached the end of the list. And also, we have no x element. So even if we wanted to
create a new a element, we can’t use the function. So the only thing
we can do anyway is just return the accumulator. How do we do the
recursion, though? Well, we know we want to
combine the accumulator we have with the first
element of the list. So we know we have to
call F-A-X. That we know we have to do. Probably what we
want to do is use it as the new accumulator for
the next element of the list. So what we do is simply
call for the l recursively with the same
combination function with that new
accumulator that we got by combining
the a and the next together as the new accumulator. And we go recursively
through the rest of the list. For some people, it
helps to realize– I said any operator can be
transformed into the function. The other way around is true. Any function can be
transformed into an operator. If you surround a
function by back quotes, you can use it in fixed syntax,
which means this f function, I can use it kind
of as an operator. In this case, I think it adds
absolutely nothing whatsoever in terms of readibility. But for some people, since my
example was using an operator as the combination
function, maybe it helps reason about
which element– which one is the accumulator,
which one is the element. If it doesn’t, there’s
absolutely no problem with this, just saying
if ax is perfectly fine. And sadly, no, we cannot
remove those parenthesis with a dollar. I know people have
tried, but no, we can’t. Sadly. So for the r is almost the same. In the case where
the list is empty, we just return the accumulator. And when we have
a non-empty list, well, we know in the
case of for the r, we’re going to pass the
accumulator untouched until the end of the
list, because we are accumulating on the way back. The accumulator
is first combined with the last element, which
means our recursive call for the r is going to be
with the same function f with the same a on
the rest of the list xs. This is going to give
us an a value, which is the accumulator
on the way back. And how do we
combine x element we have here with the
accumulator on the way back? We simply use the F
functionality you have, which takes first the x and
then the a on the way back. And yes, in this case,
we can use double. Let me check I didn’t
say anything wrong here. I can use that also double check
that my map as a fold works. Compiles the list. Ooh, it works. I made the map with
fold on the first try and I have no idea
how I did that. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Oh, of course. So lambda is introduced
by the backslash, because backslash kind
of looks like a lambda. And I’m sorry, it’s
the actual reason. And then you list the arguments,
here a and z, then in that row, and then the expression
of the lambda. So here are accumulation
function on the way back, because it’s for
the r, right to left, is to say, well,
if we have a value a in this list of a’s
and an accumulator z which is our result list,
because the result of the fold is the type of the accumulator,
we transformed the A into a B and we accumulated– we
appended at the beginning of the accumulator. But this fold version of
map is clearly not what I was asking you to do here. OK, so I was suggesting at
the end of section three to go back to section
two and re-implement some of them using fold. I’m not going to do length,
because it requires a lambda and it’s not the most
interesting ones. I want to showcase and or
and concatenation as folds, because the point
of fold is we’ve spent all the codelab so far
doing pattern matching on lists and doing– what we have on
the list is empty. What kind of recursion do we
do when the list is not empty? And that is, 90% of the
time, fold error R and L cover those cases. So instead of writing
those recursions ourselves, we can just use fold. And let me show
you how that works. So we want to rewrite and
as an f function, which does the same thing using the fold. Let’s say we use a fold l
because it’s when we meet– that’s the [INAUDIBLE]
we’ve been doing here by going left to
right in the list. We need a combination function. We need a way to combine
our accumulator, which is going to be with
the m, because it’s the result of a function. We have a Boolean of the list. What’s the function
that we need for end to combine two Booleans? Absolutely. We need a default accumulator
for when the list is empty. This is going to be– and on which list do we operate? And we’ve just written
that whole thing as a fold. Most of the time when you’re
doing a reduce on the list, you don’t need to write
recursion yourself. That’s the point of fold. How do you combine the
accumulator and the value? What’s your default value
when the list is empty? And there you have it. The question I was asked before
is, if you look at the type of and if– let me write it in the comments
to make it more explicit. So and if– type of this
thing we’ve been writing– takes a list of Booleans. And I write capital B
because it’s faster. And it returns one Boolean. Thing is, we don’t need to
write, in this case, the name l, which is the list
on which we operate. This works perfectly, as well. Why? Because it’s a partially
applied fold l. Let me show you what I mean. In this case, the type
of fold l is a function that combines two Booleans. This is the reason why
I’m using only capital B because I have a lot to type. The default Boolean to use
when the list is empty, the list of Booleans, and
returns a B at the end. If we partially
apply this with and, we have given the
first argument. So the type of list is
going to be function that takes one Boolean, the list
of Booleans, returns a Boolean. If we partially apply a
second argument, which is going to be the default
value when the list is empty, true, oops, one too many. Then the type of list
becomes functions from list of Boolean values to
Boolean value, which is also the type of end if, which means
I can just say this function, end if, is the partially applied
fold l with and and true. I don’t need to name the
list on which it operates. In most cases, I would
recommend naming the arguments, because in most cases,
having explicitly named arguments is
better, because you know what you’re talking about. In the case of lists,
yeah, I think this is OK. This style of writing
functions by just combining other functions without
naming the arguments is called point free style, despite it
using often the dot operator, because we don’t name the point
of data on which we operate. It’s a controversial topic. Sometimes it makes
things easier to read. Most of the time it doesn’t. But it’s very fun
to play with, and I encourage you to play with it. So same thing for or. I have only eight minutes,
so I’m going to speed up. How do we write or as a fold? Well, it’s a fold l
because we’ve been going through the list left to right. What’s the combination
function for our accumulator? It’s the or operator. What’s our base case
when the list is empty? It’s false. Simple. We have written or as a fold. Again, every simple
recursion through a list and the base case when the
list is empty is a fold. Even concatenation,
let’s write it as being plus, plus, byte,
byte, plus, plus, because I can. So what’s l1 plus plus
byte byte plus plus l2? Well, in this case,
we’re going to also fold r because we are going right
to left through the l1 list. What’s the combination function? How do we combine
an element of l1 with our accumulator, which is
the list we’re constructing? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Nope. That’s not our
combination function. That’s the recursive call, which
we’re not going to do here. How do we combine a value
of l1 with the r accumulator which is a list? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Absolutely. The way we combine on the
way back of our recursion here is by appending the
value to the accumulator using the column thing. So the column constructor
is the function we give to for the R. What’s
the base case of the recursion? What do we do when L1 is empty? We just [INAUDIBLE]. What’s the list on which
we do the recursion? It’s L1. That one is slightly
more tricky, but my point here
is to say, again, whenever you have to do
a reduce on the list, most of the time,
90% of the time, actually fold is enough for you. So the question of
which one should you use between fold l for
the r, for the prime– whoops. Doing– yeah, sure. AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: Oh, it’s just– I can create my own operators,
and since plus plus already exists, I just create that and
then name that one [INAUDIBLE] because I can. I could name it five, five,
plus, plus, dollar something if I wanted. That would be
horrible, but I could. Remember the curse. What else did I want
to say about this? There was something else I
wanted to say about this. Yes. There is a very good
page in the Haskell wiki about the difference between
the different folds on which one you want to use in which case. I mean, one goes left to right,
the other goes right to left. So if that matters
for you, then that is an important thing
to take into account. But for the r, works
on infinite list because it only
happens, the value– we can read the values without
evaluating the whole thing, while for the l it’s
[INAUDIBLE] optimizable and it was usually better
for performance reasons. So whether you want to deal
with infinite constructs or you want performance
also informs your choice between for
the r and for the l. Again, the Haskell wiki has
a very good page on this. So section 4 was about to maybe,
that fascinating name of type I’ve been talking about. And I’m going to see
more of it tomorrow. So basically, maybe, as you
remember, is a generic type. It has two
constructors, nothing, which does not wrap the
value, and just that does wrap the value. We can use it to
implement safe head, because head against the spatial
crashes an empty list, which is terrible. Safe head is a safe
function that just does not crash on an empty list. It already exists. There is a module
named safe that redefines safe versions of
some of the partial [INAUDIBLE] functions. But here we’ve
already implemented. What do we return for
heads of an empty list? Well, there is no
value it can return. So the only thing we
can return is nothing. In the case where we have some
x, then yes, we can wrap it. We can return something. And we can just return just x. Make sense? That’s the two constructors
to our maybe value. That’s the two different
ways we create something when we have nothing to wrap,
when we have something to wrap. OK, so how do we
deal with maybes? Well, just like with anything
else, pattern matching. So how do we write is nothing? Set of things. Some people have tried
to say, well, maybe is nothing of maybe a. We can do ma equal
equals nothing. And same thing, it doesn’t
work because for it maybe a to have
equality it needs a itself to have the equality,
which is not guaranteed here. So what we need to do
is pattern matching. Is nothing of nothing
is, of course, true. And is nothing, what
else could it be? Well, it could be
the just constructor applied on some element x,
in which case, of course, it’s false. We don’t need to name the
x because we don’t use it. And we don’t even need to name
the thing, because of course, if it’s not a thing,
then we don’t care. Yes? AUDIENCE: [INAUDIBLE] ANTOINE LEBLANC: OK, perfect. Yeah, I go through the steps
because for some people it’s better to hear or to
see the whole reasoning before we go into kind
of score directly. So from maybe, from maybe
is the way we get out. We want to take the value of
it, but since they might not be a value, we need
to provide the default to be used in the case we have
nothing, literally nothing. So we can do, if we have some
default value and nothing, well, simply, we
return the default value, which is of type A, which
is what our function returns. From maybe, if we
have just something– sorry, I can’t type– if it has just some x, we do
not care about the default value because we will not use it. The only thing
that matters is x. That’s the thing you want to
get out of the [INAUDIBLE].. And maybe is almost the same,
except sometimes extracting something and then applying
a function on the thing makes no sense, because applying
the function of the default value of your maybe
makes no sense. Sometimes you want
to apply a function on the things and
the maybe, and just get the default value for
the result of the function instead of extracting first
and then applying a function, because sometimes
it makes no sense to apply the function
on a default value. For instance, if you
have a maybe of a list and you’re trying
to do something with head, for
instance, you don’t want to have the from
maybe with empty lists and then apply head to it
because that would be absurd, and that kind of stuff. So how do we write this? Well, we have two things. In the case we have nothing, we
want to create a value of type B. We cannot use the function
from A to B because we have no A value. But if we have a B value,
which is our default, we can use that one. In the case when we
have just some A, then we don’t need
the default value. We can just apply the
transformation function that goes from A to B on the
A value to get our B value. [MUSIC PLAYING]

9 thoughts on “Haskell 101

  1. It’s amazing, that even if Antoine has a French accent, the presentation was very clear. This is one of the rare times when I turn off the subtitles because the voice clarity is superior. I must not forget to mention that this kind of introduction to Haskell is what the world needs—filled with energy and passion! ❤️

  2. I think the speaker has it backwards. The reason for Currying, is that its easier for a human to reason about functions one argument at a time. A computer can easily evaluate functions with multiple arguments simultaneously.

  3. Hello how can in resolve this in Haskell?

    import java.math.BigInteger;

    public class If {

    //The first prime number
    public static final BigInteger INIT_NUMBER = new BigInteger("2");

    public static void main(String[] args) {

    //Initialise n and p
    BigInteger n = new BigInteger("77");
    BigInteger p = INIT_NUMBER;

    //For each prime p
    while(p.compareTo(n.divide(INIT_NUMBER)) <= 0){

    //If we find p
    //Calculate q
    BigInteger q = n.divide(p);
    //Displays the result
    System.out.println("(" + p + ", " + q + ")");
    //The end of the algorithm
    //p = the next prime number
    p = p.nextProbablePrime();
    System.out.println("No solution exists");

  4. He confuses implicit type conversion with overloading. E.g. the literal '0' is not implicitly converted to e.g. Double. It is just overloaded for all numeric types which can be seen by checking its type in ghci:
    λ> :type 0
    0 :: Num p => p

Leave a Reply

Your email address will not be published. Required fields are marked *

Copyright © 2019 Explore Mellieha. All rights reserved.