CPSC 417: Foundations of Functional Programming
Author: Robin Cockett
Date: 12th September 2006
Due: 28th September 2006
Assignment #1: Getting going in Haskell.
Do questions 1,2,5,6,7,10,14,17,18,20. You should do the other
in class, labs, and on your own! Recall: if you use code you have
must document where it came from.
- 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 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]) ->
- Write a mergesort for integers: mergesortInt ::
[Integer] -> [Integer].
- Generalize the mergesort to 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] ->
-> [(a,[b])]. For example if the relation is the divide
then relgrp div [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],,[4,3,3]] :
program up this example to make sure your group works. What is
group nbr ?
- 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]] ->
and to form the dot product of two vectors. You should be able
paste these basic functions together to define matrix multiplication.
- Write a function for adding and multiplying polynomials.
You may represent the polynomials as lists of real numbers so [1,0,3,4.2]
1 + 3x^2 +4.2x^3. Thus addpoly:: [Float] ->
[Float] and multpoly:: [Float] -> [Float] -> [Float].
- Write a function which given a list of (real) roots of a
polynomial produces a (real) polynomial with those roots.
- Write a function which given a polynomial (as above) and a real
number evaluates the poynomial at that number: evalpoly:: [Float]->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