learning-languages/haskell/sessions/13_03/notes.md

Progress report - confidence scale

In the first meeting, we went through the structure of my exam on a very surface level. I reached the conclusion that, although I have a vague idea of what the topics are, I don't have a deep understanding of them. All of my knowledge is very superficial.

Hence, this progress report will be a preamble of each session, where I will list the topics and the corresponding confidence I have in them.

The scale of my confidence in the topics:

1. 😎 - Very confident
2. 😊 - Confident
3. 😐 - Can solve, no intuition
4. 😕 - No idea

Topic	Description	Confidence
Signatures	Checking whether the expression types are correct	😊
Programming	Writing code to solve an algorithmic problem	😐
Higher order functions	Demonstrate understanding of higher order functions, usually by chaining them	😐
List comprehensions	Demonstrate understanding of list comprehensions	😐
Recursion/infinite lists	Infinitely generating lists, usually by recursion and/or list comprehensions	😕
ADTs	Algebraic Data Types, usually defining a data type and writing functions that operate on it	😕
Proof on lists	Proving properties of functions that operate on lists	😕
Proof on trees/ADTs	Proving properties of functions that operate on trees or ADTs	😕

Basics

Signatures

Example given - the . operator a.k.a. f \circ g = f(g(x))

(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)

Why? Because the type of f is b -> c, the type of g is a -> b, and the type of x is a. Hence, the type of the output is c.

Stack and heap

What's the stack?

The stack is a data structure that stores information about the active subroutines of a computer program. It is used to store the return address of the function, the local variables of the function, and the parameters passed to the function. This is like CPU registers, but for functions.

What's the heap?

The heap is a region of memory that is not managed automatically for you. This is a large pool of memory from which you can request blocks of memory. This is like the RAM of the computer.

What's the difference between the stack and the heap?

The stack is used for static memory allocation and the heap is used for dynamic memory allocation, both stored in the computer's RAM. i.e. in C:

int main() {
    int x = 5; // Stack
    int* y = malloc(sizeof(int)); // Heap
}

What's the difference between the stack and the heap in Haskell?

In Haskell, the stack is used for function calls and the heap is used for storing data. This is because Haskell is a lazy language, so it doesn't evaluate the function calls immediately. Instead, it stores them in the stack and evaluates them when needed. The heap is used for storing data because Haskell is a functional language, so it doesn't have mutable variables. Hence, it stores the data in the heap. This is why Haskell is a pure language.

Recursion

Recursion in Haskell is very similar to recursion in other languages. The only difference is that Haskell is a lazy language, so it doesn't evaluate the recursion immediately. Instead, it stores the recursion in the stack and evaluates it when needed.

Tail recursion is a special case of recursion where the recursive call is the last thing in the function.

Example of non-tail recursion:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

To make the fib function tail recursive, we can use an accumulator¹

fib :: Int -> Int
fib n = go n 0 1
    where
        go 0 a b = a
        go n a b = go (n-1) b (a+b)

map, foldr, foldl, filter, zip

These are higher order functions in Haskell. They are used to operate on lists.

map applies a function to each element of a list.

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

foldr is a right fold. It is used to reduce a list to a single value.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

foldl is a left fold. It is used to reduce a list to a single value.

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

filter is used to filter a list based on a predicate.

filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs) = if p x then x : filter p xs else filter p xs

zip is used to combine two lists into a list of tuples.

zip :: [a] -> [b] -> [(a, b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x, y) : zip xs ys

---

1. This is a common pattern in functional programming. The idea is to pass an accumulator to the function and update it in each recursive call. This is to "circumvent" immutability by introducing a way to store the "state" of the function. ↩︎