133 lines
4.9 KiB
Markdown
133 lines
4.9 KiB
Markdown
|
|
## 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))$
|
|
|
|
```haskell
|
|
(.) :: (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:
|
|
```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:
|
|
```haskell
|
|
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[^1]
|
|
```haskell
|
|
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.
|
|
```haskell
|
|
map :: (a -> b) -> [a] -> [b]
|
|
map f [] = []
|
|
map f (x:xs) = f x : map f xs
|
|
```
|
|
|
|
<p align="center">
|
|
<img src="folds.png" alt="folds" width="700"/>
|
|
</p>
|
|
|
|
`foldr` is a right fold. It is used to reduce a list to a single value.
|
|
```haskell
|
|
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.
|
|
```haskell
|
|
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.
|
|
```haskell
|
|
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.
|
|
```haskell
|
|
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.
|