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

3.1 Basic Concepts

A type is a collection of related values.

Excerpt From: Graham Hutton. “Programming in Haskell” (2nd ed.).

This means that the set-theoretic definition of the type Bool could be thought of as Bool = {True, False} and the type Bool -> Bool would be Bool->Bool = {f: Bool -> Bool}.

Exercise 1

What are the types of the following values?

• ['a','b','c'] :: ?
  • [Char]
• ('a','b','c') :: ?
  • (Char, Char, Char)
• [(False,'O'),(True,'1')] :: ?
  • [(Bool, Char)]
• ([False,True],['0','1']) :: ?
  • ([Bool], [Char])

2.3 Standard Prelude

Haskell has a large standard library. A portion of the standard library, called the Prelude, is included by default in all Haskell packages. Prelude includes many useful and commonly used functions, so it serves as a core part of the standard library. It includes functions such as + and * as well as several functions used on lists (like head, tail, take, and drop).

1.1 Functions

In Haskell, a function is a mapping that takes one or more arguments and produces a single result, and is defined using an equation that gives a name for the function, a name for each of its arguments, and a body that specifies how the result can be calculated in terms of the arguments.

Excerpt From: Graham Hutton. “Programming in Haskell.”