Hand in: email your solution (as a plain text file) to barak+cs351@cs.nuim.ie

Due: 09:00 on Mon 24-Dec-2007.

Teamwork is encouraged. Please work in teams of up to three (3) people. Just turn in one (1) solution set, with the entire team listed at the top, sorted by how much each person contributed. (The order will not affect grades; it will be used only for my own consistency checking of scores at the end of the course.)

NUIM/CS351 Assignment 6

Fun with Haskell

The objective of this assignment is to get a taste of Haskell.

Please put explicit type signatures in your file for all definitions.

  1. Implement our old friend noah, which takes a list with an even number of elements and returns a list of lists of pairs of elements from the original list. Type:
    noah :: [a] -> [[a]]

  2. Implement our old friend hackHunks which takes a positive integer and a list and hacks the list up into hunks of the given size. Type:
    hackHunks :: Int -> [a] -> [[a]]

  3. Define perms which takes a list and returns a list of all permutations of the given list. Eg: perms ["a","b","c"] returns a list (perhaps in some different order) [["a","b","c"], ["a","c","b"], ["b","a","c"], ["b","c","a"], ["c","a","b"], ["c","b","a"]] or perms "ARE" = ["ARE","RAE","REA","AER","EAR","ERA"]

  4. Define a data type MyTree a which is a binary tree with elements of type a on the leaves.

  5. Define fringe :: (MyTree a) -> [a] which returns the fringe of a tree, in order.

  6. Define makeTree :: [a] -> (MyTree a) which takes a list and returns a tree with the given elements as its fringe, in the same order. Note that there are many possible trees that might be returned; you need to choose one. Also note that fringe . makeTree would be the identity function on lists. (For style points, make sure this builds a tree that is (a) roughly balanced, and (b) that it works on an infinite list.)

  7. Define infMerge2 which takes two lists, each potentially infinite, of the same type, and returns a list containing all the elements of both lists. In other words: if some element is in one of the input lists, it will at some point appear on the output list.

  8. Define infMerge :: [[a]] -> [a] which takes a potentially infinite list of potentially infinite lists, and returns a single list which contains all elements in all the lists it was passed.