CPSC 521: Foundations of Functional Programming

Author: Robin Cockett
Date: September 2011

Due:  23th September  2011

Assignment #1:  Getting going in Haskell.

Do questions 1,2,6,7,11,12,14,16,21,22. 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.
  1. Write your own function for appending two lists and for reversing a list: app:: ([a],[a]) -> [a], rev:: [a] -> [a].
  2. Write your own function for flattening a list of lists to a list: flatten :: [[a]] -> [a].
  3. Write a function which given a number and a list of numbers returns those numbers greater than the first number: greaterinlist:: Integer -> [Integer] -> [Integer].
  4. 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.
  5. 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!
  6. 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].
  7. 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.
  8. Write a quicksort for an arbitrary ordered type: quicksort:: (Ord a) => [a] -> [a].
  9. Write a function which determines whether an element (of equality type) is in a list: member:: (Eq a) => a -> [a] -> Bool.
  10. 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])]].
  11. 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 []?
  12. Given a Rose tree ( data Rose a = RS a [Rose a] ) calculate the width of the tree (that is in the undirected graph of the tree the length of the longest path).
  13. Write a function which given a list returns a list of all the subsets of the list: subset:: [a] -> [[a]].
  14. 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.
  15. Write a function to turn decimal numbers into roman numerals and a function for the reverse translation (here is one solution, here is another).
  16. 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.  
  17. 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]. Can you modify show to display the polynomials clearly?
  18. Write a function which given a list of (real) roots of a polynomial produces a (real) polynomial with those roots.
  19. Write a function which given a polynomial (as above) and a real number evaluates the poynomial at that number: evalpoly:: [Float]->Float -> Float.
  20. 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.
  21.  Calculate the factorial of 1,891 or explain six different ways of programming factorial.
  22. (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?
  23. (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?