Due: 26th September 2017

Do questions 1,2,5,6,7,8,11,12,17,20,21 (and try 22 for a bonus point!). You should do the other questions in class, labs, and on your own!

Recall: You must document your code. You should develop the code for these functions yourself: if you use code you have found you must document

- Write your own function for appending two lists and for
reversing a list:
*app:: ([a],[a]) -> [a], rev:: [a] -> [a].*Now define your own data type for lists and write the append function for this datatype.

- Write your own function for flattening a list of lists to a
list:
*flatten :: [[a]] -> [a]*. Write a flatten function for your own datatype for lists.

- 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 (using the class system).
- 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.
- 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).