CPSC 417: Foundations of Functional Programming
Author: Robin Cockett
Date: 19th January 2003
Due: 27th January 2003
Assignment #1: Getting going in Haskell (This is now
a complete set: discuss the last three questions in the labs).
- Write your own function for appending two list: append ::
([a],[a]) -> [a].
- Write your own function for fattening a list of lists to a list:
flatten :: [[a]] -> [a].
- Write a function which given a number and a list of number returns
those numbers greater than the first number: greaterinlist:: Integer
-> [Integer] -> [Integer].
- Write 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]).
- Write a function to merge two lists of integers, taking the
least first element at each step: mergeInt :: ([Integer],[Integer])
-> [Integer] .
- Write a mergesort for integers: mergesortInt :: [Integer]
- Generalize the merge sort to arbitary ordered type.
- Calculate the factorial of 1,279 or explain six different ways
- 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],,[4,3,3]]
: program up this example to make sure your group works. What is
- Write programs to do matrix 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.
- 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.