Due: 28th September 2006

Do questions 1,2,5,6,7,10,14,17,18,20. 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

- 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]) -> [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] -> [b] -> [(a,[b])]*. For example if the relation is the divide relation 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],[7],[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]] -> [[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 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]*. - 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 ways of programming factorial.