Data structures

Tuples

A tuple is a sequence of a finite length. An empty tuple is called a unit, a singleton tuple is not used, a tuple of two items is a pair and a tuple of three is a triple. Tuples can contain a mixture of types. (5, "Hello", False) :: (Int, String, Bool) is an example of a tuple with multiple types.

Currying and uncurrying

Sometimes function take pairs as arguments but it would be ideal to provide two separate arguments and vice versa.

curry   :: ((a, b) -> c) -> (a -> b -> c)
uncurry :: (a -> b -> c) -> ((a, b) -> c)

The curry function converts functions on pairs to functions on two parameters and uncurry functions convert function on two arguments and uncurry does the opposite.

Lists

Lists are collections of values with the same type. Lists have two constructors, the empty list and the cons operator, (:).

[]  :: [a]
(:) :: a -> [a] -> [a]

The cons operator takes two parameters - the head and tail of the list and it joins the head to the tail. A basic list of integers can be defined as 1 : (3 : (5 : [])), but this is quite inconvenient. Instead, Haskell provides syntactic sugar and the list can instead be defined [1,3,5] which will desugar to the first definition but is easier to work with.

It is possible to pattern match lists. Consider a function removes the head of the list.

removeHead (x:xs) = xs

This pattern matches on the head and tail using the cons operator.

Ranges

It is possible to easily define ranges using the [a..b] syntax. For example, [5..50] is the list containing the numbers 5 to 50 inclusive. It is also possible to specify a step. [1, 3.. 21] is the list of odd numbers between 1 and 21 inclusive. It is not necessary to specify the upper value, [5..] is the list of 5 onwards. This is possible because Haskell is lazy so the list is only evaluated when needed.

List comprehensions

List comprehensions in Haskell work similarly to those in mathematics. A list comprehension consists of an expression and a generator.

squares = [x^2 | x <- [1,2,3]]
        = [1, 4, 9]

It is possible to use multiple generators and they are read left to right.

[(x,y) | x <- [0..2], y <- [0..x]]
[ (0, 0),
    (1, 0), (1, 1),
    (2, 0), (2, 1), (2,2)
]

It is also possible to add guards to list comprehensions. To generate the list of even numbers up to and including 100, you would use evens = [x | x <- [0..100], even x]

Map and filter

The map function is used to apply a function to every value in a list. For example, to double every number in a list, you would use map (* 2) [1,2,3,4].

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

The filter function takes a Boolean function and a list and keeps the elements that satisfy the given function. For example, filter even [1,2,3,4] will give [2,4].

filter :: (a -> Bool) -> [a] -> [a]
filter f [] = []
filter f (x:xs)
    | f x       = x : filter f xs
    | otherwise = filter f xs

Trees

A binary tree can be created using a recursive data type.

data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a)

The first constructor represents and empty tree and the second represents a node with a value and a left and right subtree. It is then possible to define foldable and functor instances for the tree so fmap and foldr can be used with it.