This website houses notes from my studies at the University of Liverpool. If you see any errors or issues, please do open an issue on this site's GitHub.
The entity relationship model is used to express the conceptual schema of a database. It was originally proposed in 1976 as a means to unify the network and relational DB models. Many theoretical extensions and practical applications have been developed including the Enhanced Entity Relationship (EER) model. It is simple...
Uncountable Sets A set that is not countable is called uncountable. The following set is uncountable: \[S = \{ x \in \mathbb{R} \vert 0 < x < 1 \}\] There is no bijective function from this set to the set of all natural numbers. Cantor’s Diagonal Argument Suppose for a...
Countable Sets A set that is either finite or has the same cardinality as $\mathbb{N}$ is called countable. $\mathbb{Z}$ For a set $\mathbb{Z}$ you can count it by starting at zero and then jumping from item to item by the way of a function. In this way you can produce...
Bijections and Cardinality The cardinality of a finite set is the number of element in the set. Sets $A$ and $B$ have the same cardinality $\Rightarrow$ there is a bijection from $A$ to $B$. Let $S=\{1,2,\ldots,n\}$ and let $B^n$ be the set of bit strings of length $n$. The function:...
More Higher Order Functions - Continued takewhile This function takes while a condition is true. > takeWhile (<=5) [1..10] > [1,2,3,4,5] This is different to filter which only removes individual elements. > takeWhile (\ x -> length x <= 2) ["ab","cd","efg"] > ["ab", "cd"] Implementation takeWhile' :: (a -> Bool)...
More Higher Order Functions Scan The scan set of functions is similar to the fold set of functions. However instead of outputting a single value it outputs a list showing the accumulator at each step in the function: > scanr (+) 0 [1,2,3,4] > [10,9,7,4,0] The function scanr is implemented...
Power Sets The power set $\text{Pow}\{A\}$ of a set $A$ is the set of all possible subsets. This includes the null set $\emptyset$ and the full set. Each set in the power set follows this definition: \[\{x\vert x\subseteq A\}\] Example The power set $\text{Pow}\{A\}$ of a set $A=\{1,2\}$ is: \[\{\emptyset,\{1\},\{2\},\{1,2\}\}\]...
Fold Continued A fold output can be a different type to the input list. to_csv list = foldr (\x acc -> show x ++ "," ++ acc) "" list > to_csv [1,2,3,4] > "1,2,3,4," By using foldr you cannot get the desired outcome as it applies the same rule to...
Fold Some functions take lists and turn them into a single value. This type of computation is called a fold. The things that you can change are: The base case. The operation applied to the list. foldr foldr' :: (a -> b -> b) -> b -> [a] -> b...
Theorem of Friends and Strangers Show that in any group of six people there are either three who all know each other or three complete strangers. On this graph blue is people who know each other and red is people who don’t. From the graph you can see that only...