Assignment 1

CPSC 521: Foundations of Functional Programming

Author: Robin Cockett
Date: 5th January 2022

Due: 28th January 2022

Assignment #1: Getting going in Haskell.

Do questions 1, 4, 5, 6, 7, 9, 11, 12, 15, 19 (and 18 for fun!). The (other) questions will be discussed in class and labs!

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 where it came from ... credit will be apportioned appropriately.

Write your own function for appending two lists and for reversing a list: app:: ([a],[a]) -> [a], rev:: [a] -> [a]. Now define your own datatype 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.
Develop a merge sort in Haskell:

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]].
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 becomes its righthand neighbor unless it is at the end of a sublist in which case it goes to the first in the sublist. Give the list of all permutations represented by their cyclic decompositions.
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 normalizing, adding, and multiplying multivariable polynomials. You may represent the polynomials as lists of real numbers paired with a list of powers, [(Float,[Int])], for each variable so [(1.5,[0,0,0]),(3.2,[0,1,1]),(4.7,[2,2])] = 1.5 + 3.2yz +4.7x^2y^2. To normalize a polynomial one places entries so the power lists are in lexicographical order and one amalgamates any repeated terms: normpoly:: [(Float,[Int])] -> [(Float,[Int])]. To add polynomials we have addpoly:: [(Float,[Int])] -> [(Float,[Int])] -> [(Float,[Int])] and to multiply polynomials multpoly:: [(Float,[Int])] -> [(Float,[Int])] -> [(Float,[Int])].
Write a function which given a multivariate polynomial (as above) and a list of real number evaluates the poynomial at those numbers (possibly leaving some variables unassigned): evalpoly:: [Float] -> [(Float,[Int])] -> [(Float,[Int])].
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 with values at the auguments of the nodes ( data Rose a = RS [(a,Rose a)] ) use a fold to calculate the width of a Rose Int tree (that is in the undirected graph of the tree with weighted edges, the width is the length of the longest path), width:: Rose Int -> Int.