Exercise 1

In a similar manner to the function add, define a recursive multiplication function mult :: Nat -> Nat -> Nat for the recursive type of natural numbers:

Hint: make use of add in your definition.

data Nat = Zero | Succ Nat
deriving stock Show

add :: Nat -> Nat -> Nat
add Zero     n = n
add (Succ m) n = Succ (add m n)

mult :: Nat -> Nat -> Nat
mult Zero     _ = Zero
mult (Succ m) n = add n (mult m n)

8.1 Type declarations

We can introduce new names for types that we already have by means of the type keyword. As an example, if we wanted to think of an ordered pair of integers as some position, we could do so by writing type Pos = (Int, Int) and we might declare a transformation as a function which maps a Pos to another Pos: type Trans = Pos -> Pos.

Note: the name of the newly declared type must be capitalized.

Exercise 1

Show how the list comprehension [f x | x <- xs, p x] can be re-expressed using the higher order functions map and filter.

applyFilterAndFnToList :: (a -> Bool) -> (a -> b) -> [a] -> [b]
applyFilterAndFnToList p f xs = map f (filter p xs)

7.1 Basic Concepts

Functions with multiple arguments are defined with currying (which is part of why we have right-associative groupings for parameters). As an example, we can rewrite

add :: Int -> Int -> Int
add xy = x + y

as

add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)

which makes it clear that add is a function that takes an integer and returns another function which takes an integer and maps to the sum x + y.

6.1 Basic Concepts

Functions can be defined in terms of themselves. When a function is self-referential, we say that it is recursive. Consider the explicit and recursive definitions of the factorial function:

facExplicit :: Int -> Int
facExplicit n = product [1..n]

facRecursive :: Int -> Int
facRecursive 0 = 1
facRecursive n = n * facRecursive (n - 1)

Exercise 1

How does the recursive version of the factorial function behave if applied to a negative argument, like  − 1? Modify the definition to prohibit negative arguments by adding a guard to the recursive case.

facRecursive :: Int -> Int
facRecursive n
    | n < 0     = 0
    | n == 0    = 1
    | otherwise = n * facRecursive (n - 1)

5.1 Basic Concepts

In mathematics, we can construct a set with a generator. If we wanted to create the set of all odd numbers, we could use the set-builder notation {2k + 1|x ∈ ℤ⁺}.

Haskell presents a similar opportunity, but it calls it a list comprehension. If we were to want to build a list of the first 10 perfect squares, we could do

> [x^2 | x <- [1..10]]
[1,4,9,16,25,36,49,64,81,100]

5.7 Exercises

Exercise 1

Using a list comprehension, give an expression that calculates the sum 1² + 2² + … + 100² of the first one hundred integer squares.

sum100ConsecSquares :: Int
sum100ConsecSquares = sum [x^2 | x <- [1..100]]

4.1 New From Old

Function composition is an extremely powerful tool and should not be overlooked. If it works for Unix, it’ll probably work for you.

Exercise 1

Using library functions, define a function halve :: [a] -> ([a],[a]) that splits an even-lengthed list into two halves. For example:

> halve [1,2,3,4,5,6]
([1,2,3],[4,5,6])

halve :: [a] -> ([a],[a])
halve xs = splitAt (((length xs) + 1) `div` 2) xs