CPSC 521: Foundations of Functional Programming
Author: Robin Cockett
Date: September 2016
Due: 13th September 2016
Assignment #1: Getting going in Haskell.
Do questions 1,2,4,6,7,11,12,14,17,21 (and 24 if you are keen). You
should do the other questions in class, labs, and on your own!
Recall: if you use code you have encountered somewhere you
must document where it came from -- you are expected to
understand your code and to document it clearly.
- Write your own function for appending two lists and for
reversing a list: app:: ([a],[a]) -> [a], rev:: [a] ->
[a].
- Write your own function for flattening a list of lists to a
list: flatten :: [[a]] -> [a].
- Write a function which given a number and a list of numbers
returns those numbers greater than the first number: greaterinlist::
Integer -> [Integer] -> [Integer].
- Write a function to determine whether its first argument, a
list of integers, is lexicographically larger than its second
argument: lexInt::[Int] -> [Int] -> Bool.
Now modify it to work on any type in class Ord. Finally can you modify
the Ord class to
include lexicographical orderings of lists.
- Write a function to do "run length encoding" of a list: encode:: (Eq a) = [a] ->
[(a,Int)] which has encode
[a,a,b,c,c,c] = [(a,2),(b,1),(c,3)]. Write a
decoder as well!
- write a function to "rotate" a list n places to the left: rotate:: [a] -> int -> [a] where
rotate [a,b,c,d,e] 2
=[c,d,e,a,b].
- Write a mergesort for integers: mergesortInt ::
[Integer] -> [Integer]. This involves writing a
function which splits a list into two lists (the first
containing the odd indexed elements and the second containing
the even indexed elements) msplit:: [a] -> ([a],[a]), and a function to merge
two lists of integers, taking the least first element at each
step: mergeInt :: ([Integer],[Integer]) -> [Integer]
. Can you write the mergesort for an arbitrary
ordered type.
- Write a quicksort for an arbitrary ordered type: quicksort::
(Ord
a) => [a] -> [a].
- Write a function which determines whether an element (of
equality type) is in a list: member:: (Eq a) => a ->
[a] -> Bool.
- Given a relation rel:: a -> b -> Bool and a list
of a-elements and a list of b-elements write a
function which returns a list of pairs of an a-element
and the list of b-elements from the second list to which
it is related: relgrp:: (a -> b -> Bool) -> [a]
-> [b] -> [(a,[b])]. For example if the
relation is the divide relation then relgrp divide [2,3]
[1,2,3,4,5,6] = [(2,[2,4,6]),(3,[3,6])]].
- Program the "group" function: given a predicate pred:: a
-> a -> Bool and a list the group function breaks
the list into a series of (maximal) sublists such that any two
consecutive elements satisfy the predicate pred.
The type of the function group is group:: (a -> a ->
Bool) -> [a] -> [[a]]. An example of its use
is as follows: suppose that the predicate nbr determines
whether the absolute difference of two integers is at most 1
(i.e. they are equal or they differ by one) then group nbr
[2,1,3,4,5,5,4,7,4,3,3] = [[2,1],[3,4,5,5,4],[7],[4,3,3]]
: program up this example to make sure your group works.
What is group nbr []?
- Given a Rose tree ( data
Rose a = RS a [Rose a] ) use a fold to calculate the
width of the tree (that is in the undirected graph of the tree
the length of the longest path).
- Write a function which given a list returns a list of all the
subsets of the list: subset:: [a] -> [[a]].
- Write a function which given a list returns the list of all
permutations of that list: perm:: [a] -> [[a]].
As a bonus: given a permutation it is possible to give its
cyclic decomposition. For example the permutation [2,4,5,1,3]
of [1,2,3,4,5] can be represented as [[1,2,4],[3,5]]
where this indicates that each element goes to it neighbor
unless it is at the end of a sublist in which case it goes to
the first in the sublist.
- Write a function to turn decimal numbers into roman
numerals and a function for the reverse translation (here
is one solution,
here is another).
- Write programs to do basic matrix addition and multiplication.
For this excercise I want you to regard a matrix as
a list of lists of numbers and to define the operations in terms
of the following primitive functions. You will need a
function to xzip two lists together which reports an
error if they are not the same length (there is a zip in
the prelude which does not report an error). You will need
the map function in the prelude. You will need to
write a function which transposes a matrix transpose:: [[a]]
-> [[a]] and to form the dot product of two
vectors. You should be able to paste these basic
functions together to define matrix multiplication.
- Write a function for adding and multiplying polynomials.
You may represent the normal form of polynomials as lists
of real numbers so [1,0,3,4.2] = 1 + 3x^2 +4.2x^3.
Thus addpoly:: [Float] -> [Float] ->
[Float] and multpoly:: [Float] -> [Float]
-> [Float]. Can you modify show to display the polynomials clearly?
- Write a function which given a list of (real) roots of a
polynomial produces a (real) polynomial in (in the form a_n
x^n + ... a_1 x + a_0) with those roots.
- Write a function which given a polynomial (as above) and a
real number evaluates the polynomial at that number: evalpoly:: [Float]->Float ->
Float.
- Write a function to differentiate a polynomial: diffpoly:: [Float]->[Float].
- An expression tree (or term) is the datatype data ETree =
Var String | Opn String [ETree]. A typical
element is Opn "add" [Var "x1",Var "x2"] (which is
an internal representation of x1 + x2 ). Write a
function varsof:: Etree -> [String] which collects
the set of variable in the expression (or term). Thus, varsof(Opn
"add" [Var "x1",Var "x2"]) = ["x1","x2"]. Be
careful to ensure that variables only occur once in the output
list.
- Calculate the factorial of 1,891 or explain six
different ways of
programming factorial.
- (Harder) Write a function to determine whether in a relation
(specified by r::[(a,a)])
two elements are connected (i.e there is a path from one to the
other) connect :: (Eq a)
=> [(a,a)] -> a -> a -> Bool. Can
you modify this to find the shortest path between two elements?
- (Harder) Write a function to determine whether a graph can be
colored with at most n
colors, color :: (Eq a) =>
[(a,a)] -> Int-> Bool. Can you return the
coloring?