Assignment #1

Due February 8.

  1. Install GHC Haskell -- download site

  2. Read the paper 'Why Functional Programming Matters' by John Hughes, and read 'Why Haskell Matters'.

  3. Define three functions, fib1, fib2 and fib3, which use tree recursion, a linear algorithm, and De Moivre's formula in Haskell. Each function will take a single integer parameter and return the corresponding fibonacci number. You can get quick performance measurements in Haskell by using the +s switch, which can be toggled interactively like this 
    	> :set +s
	> :unset +s
    and you can apply a function to successive members of a list like this: 
    	gen f n = map f [1..n])
    The function gen could then be called by, e.g., 
    	> gen fib2 2000
    which would list the first 2000 fibonacci numbers using the linear algorithm. There are more powerful profiling tools built into GHC -- see Chapter 5 of the The Glorious Glasgow Haskell Compilation System User's Guide.

  4. Implement Ackermann's function in Haskell.

  5. The function max returns the maximum of two numbers. Write a function using a fold that will return the maximum value in a list (and zero if the list is empty). So, when applied to [5,10,2,8,1] it will return 10. Assume that the values in the list are always &ge 0.

  6. Write or find a Haskell function that will transpose the rows and columns of a matrix given as its argument.

  7. In Haskell a list of pairs can be construed as a relation. Write predicates symmetric? and transitive? that will indicate whether an argument relation is symmetric or transitive.

  8. Write a Haskell function that will use Eratosthenes seive to generate all prime numbers less than or equal to its argument.

  9. Write a complete user program in Haskell, i.e., something that prompts for input from a user, does something with this input, and produces suitable output. Compile it.

  10. Write a Haskell quine.

  11. Write a Haskell function to produce all possible permutations of its argument list.

  12. Write map and concatMap in terms of foldr. The Prelude Tour has exact definitions of these functions.

  13. Write a Haskell function to determine the maximum subsequence of a list of integers. The maximum subsequence is the contiguous subsequence with the largest sum. You do not need to return this subsequence itself--only the sum of its elements. For convenience, assume that if all integers in the list are negative the sum is 0. Make your function as efficient as possible. What is the order of growth of your solution? Confirm this experimentally.

  14. Start working on 99 Haskell problems.

Enjoy!