add notes (unfinished) for lecture 1

1 files changed, 159 insertions, 0 deletions

diff --git a/lec01/notes.md b/lec01/notes.md
new file mode 100644
index 0000000..87b1f8c
--- /dev/null
+++ b/lec01/notes.md
@@ -0,0 +1,159 @@
+# Lecture 1: Haskell basics
+
+## What's Haskell?
+
+Haskell is a programming language created in the late 1980's by academics. It is lazy and functional, but so were many programming languages at that time. Haskell was born from the necessity of a language that could easily communicate ideas, which was difficult with all those existing languages.
+
+Four fundamental concepts shape the Haskell programming language.
+
+Haskell is **functional**: functions are said to be *first-class* which, in other words, means that they are treated and can be used as other values. Another aspect of this is that Haskell programs mainly *evaulate expressions*, instead of *executing instructions*.
+
+Haskell is **pure**: no value can mutate, no expression can have side effects, and functions evaluated with the same arguments produce the same output.
+
+Haskell is **lazy**: the evaluation of expressions is delayed until their result is used. This makes it possible to, for example, work with infinite data structures.
+
+Haskell is **statically typed**: every expression has a type and all types are checked during compilation, not run-time.
+
+## Themes of the course
+
+### Types
+
+In other programming languages, static types are often annoying to work with. However, Haskell's type system is much more flexible, expressive, and readable. It helps reasoning about the program's structure and design, it documents code, and it translates potential run-time errors in compile-time errors.
+
+### Abstraction
+
+Haskell does a good job when it comes to abstraction, its features make repetitions very infrequent. Some of those features are: parametric polymorphism, higher-order functions, and type classes.
+
+### Wholemeal programming
+
+The idea of wholemeal programming is to *think big*, to think of something in its entirety rather than focusing on every piece that composes it. The problem is first solved at a distance by identifying the expression that makes a general solution. Then, the thinking shifts to the cases that don't behave like the rest.
+
+## First steps in the language
+
+### Declarations, variables, and comments
+
+	x :: Int
+	x = 3
+	-- This is a single-line comment
+	{- This is a
+		multi-line comment -}
+
+What does the code above do? It first declares a variable named `x` with type `Int` (`::` is pronounced as "has type"). Then, its value is set to 3. The variable `x` will keep this value forever, until the program is no longer running. Trying to assign another value to `x` later will result in the compiler giving an error.
+
+As we said above, variables are immutable and therefore they are just names for values. In fact, in the program above, `x` was not actually *assigned* a value, it was *defined as* a value.
+
+### Basic types
+
+Haskell basic types can be summed up like this:
+
+- `Int` is a machine-sized integer
+- `Integer` is an arbitrary-precision integer
+- `Double` is a double-precision floating point
+- `Bool` is a boolean number (`True`, `False`)
+- `Char` is a unicode character (delimited by single quotes)
+- `String` is a list of characters (delimited by double quotes)
+
+The exact dimension of `Int` depends on the machine. However, they are guaranteed by the language to be at least 32 bits in size. The exact range can be found like this:
+
+	biggestInt, smallestInt :: Int
+	biggestInt = maxBound
+	smallestInt = minBound
+
+On the other hand, `Integer` can be indefinitely large, as long as your available memory permits it.
+
+### GHCi
+
+GHCi is an interactive Haskell prompt or REPL (Read, Eval, Print, Loop) bundled with GHC. It enables the evaluation of expressions by loading Haskell files with `:load` (or `:l`) and `:reload` (or `:r`). It can also provide the type of an expression with `:type` (or `:t`). Typing `:?` lists available commands.
+
+### Arithmetic
+
+Arithmetic operations work similarly to other programming languages: the operators use the [infix notation](https://en.wikipedia.org/wiki/Infix_notation) and they are written with familiar symbols.
+
+One neat feature is that new infix operators can be implemented using just functions with two arguments. Those functions will then need to be wrapped in backticks so that they can be used as infix operators. An example below, which assumes the `mod` function to be defined with two integers as arguments.
+
+	ex1 = mod 19 3
+	ex2 = 19 `mod` 3
+
+One downside, however, is that negative numbers need to be wrapped between parentheses, since their "minus" is also an operator and Haskell has no operator precedence.
+
+Another thing to note is that Haskell does not implicitly convert between types. If we have an integer value and our function expects any other type, we can use the `fromIntegral` function. Similarly, if we have a floating point value and we need an integer, there are functions such as `round`, `floor`, and `ceiling`, which have the same meaning as in math. Although this may sound annoying, it's actually useful as implicit conversions are a source of errors.
+
+Another little downside is that the slash symbol (`/`) only performs floating point division and for an integer division we must use the `div` function, optionally as an infix operator.
+
+#### Boolean algebra
+
+Boolean operators include the classical double-ampersand "AND" (`&&`) and the double-vertical-bar "OR" (`||`). The "NOT" operator is simply `not`.
+
+Equality and order comparison follow the usual operators (`==`, `<`, `>=`, etc.) with the exception of the inequality operator, which is made of slash and equal symbols `/=`.
+
+Haskell provides `if` expressions as part of its syntax. They are written as: `if b then t else f`, which evaluates to `t` if `b` is `True`, `f` otherwise. Differently from imperative languages, `else` and the expression that follows it are not optional: the expression must always result in some value. Although Haskell provides `if` expressions, they are not used much in favor of *pattern-matching* and *guards*.
+
+### Function definitions
+
+Functions can be written by cases.
+
+	sumtorial :: Integer -> Integer
+	sumtorial 0 = 0
+	sumtorial n = n + sumtorial (n-1)
+
+First of all, let's look at the type of `sumtorial`: `Integer -> Integer`. It means that the function takes an integer as input an it outputs another integer.
+
+Secondly, we call *clauses* what's between the function name and the equal sign (`=`). They can be any valid pattern, including constants. Every time a function like this is called with a value, that value is compared to each clause until it either matches one of the provided constants or ends up in a variable name. Patterns are checked in order, starting from the top clause and going down to the bottom. After the first matching clause is found, it is chosen for the expression evaluation. This is important for recursive functions: the base cases always go on top, otherwise we may create an infinite loop.
+
+There is another way of writing functions, using **guards**:
+
+	hailstone :: Integer -> Integer
+	hailstone n
+	  | n `mod` 2 == 0 = n `div` 2
+	  | otherwise      = 3*n + 1
+
+In this example, `n` is our only clause and it has two *guards*.
+
+In guards, after entering a clause due to its matching pattern, conditions are evaluated from top to bottom and the first which evaluates to `True` is chosen. `otherwise` is matched when none of the above evaluated to `True`, `otherwise` always evaluates to `True`. Each clause of a function definiton can be associated with any number of guards, but each guard must evaluate to a Boolean expression. Boolean expressions in guards can evaluate to a constant which does not depend on any of the function's arguments.
+
+### Pairs
+
+Pairs are simply pairs of values.
+
+	p :: (Int, Char)
+	p = (3, 'x')
+
+Values are not required to have the same type, as the example shows. The notation with parentheses and a comma is used for both the type and the value of a pair.
+
+Pairs are valid patterns for clauses.
+
+	sumPair :: (Int,Int) -> Int
+	sumPair (x,y) = x + y
+
+### Functions with many arguments
+
+Functions can have more than one argument. In these cases, the function type grows with the additional types separated by arrows while the clauses can simply add variables to patterns.
+
+	f :: Int -> Int -> Int -> Int
+	f x y z = x + y + z
+
+Since function application has higher precedence over any infix operator, infix operations whose result is passed as function argument must be wrapped in parentheses.
+
+	f 3 (n+1) 7
+
+### Lists
+
+Lists are a basic data type in Haskell. They are written as their type surrounded by square brackets.
+
+	nums :: [Integer]
+	nums = [1,2,3,19]
+
+Haskell provides **list comprehensions**.
+
+Strings are lists of characters, `String` is the same as `[Char]`, which use special syntax for their values: instead of writing lists of characters, they are simply written with double quotes. This is useful because it allows to process Strings just as any other list.
+
+Lists can be empty. The empty list is the simplest list.
+
+	myList = []
+
+By using the **cons operator** (`:`), we can build lists on top of the empty list. The cons operator, provided an element and a list, produces a new list with that element as first elements, followed by all the other elements in the list. For convenience, we can use `[1, 2, 3]` instead of `1 : 2 : 3 : []`.
+
+It's important to note that *lists are not arrays*. Lists are, in fact, singly linked lists.
+
+### Functions on lists
+