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).

  1. Write your own function for appending two list: append :: ([a],[a]) -> [a].
  2. Write your own function for fattening a list of lists to a list: flatten :: [[a]] -> [a].
  3. Write a function which given a number and a list of number returns those numbers greater than the first number: greaterinlist:: Integer -> [Integer] -> [Integer].
  4. 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]).
  5. Write a function to merge two lists of integers, taking the least first element at each step: mergeInt :: ([Integer],[Integer]) -> [Integer] .
  6. Write a mergesort for integers:  mergesortInt :: [Integer] -> [Integer].
  7. Generalize the merge sort to arbitary ordered type.
  8. Calculate the factorial of 1,279 or explain six different ways of programming factorial.
  9. 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 []?
  10. 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.  
  11. 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.