Homework 6 — Programming Language Paradigms

Objective

Develop basic familiarity with function definitions, pattern matching, and recursion in Haskell

Due Date

Beginning of class session 15.

Tasks

  1. If you have not done so already, install the Haskell Platform. Instructions are posted here.

  2. Make sure you have a working install of TortoiseSVN (on Windows) or some other svn client.

  3. Use your SVN client to check-out your individual SVN repository:

    http://svn.cs.rose-hulman.edu/repos/csse403-201110-username

    where username is your Rose-Hulman username.

    You may need to enter your SVN (not Kerberos) password if your SVN client hasn't already cached it.

  4. Your programming for this assignment must be done in the folder HaskellFunctions within your local copy of your SVN repository. Using your favorite text editor, open the file functions.hs within the HaskellFunctions folder.

  5. Within your functions.hs file, implement and test the functions described below. You must use exactly the given function names or we'll deduct 50% from your homework score. This is so we can efficiently grade your and your classmates’ work.

    Note well:

    You do not need to worry about validating the input to any of these functions. You can just assume that only well-formed input will be provided.

    Test code for the functions is provided, though it is commented out. Uncomment the lines in test as you make progress on your solutions.

    Please read all the comments in the file. I wrote them to help you!

    I'm reassigning several of the same problems on this homework as on earlier ones. My intent is that you can focus on the differences between the languages in the context of problems that should be familiar. I hope you find this to be a good use of your time. If the problems seem too easy, please let me know.

    1. Simple recursive fibonacci n function, that returns the nth Fibonacci number.
    2. Fast, recursive fastFib n function, that uses helper functions and pairs to calculate the nth Fibonacci number in O(n)
    3. A function firstN n xs that takes a number n and a list xs and returns a list consisting of the first n items of the list xs. (Haskell has a built-in function to do this. Don’t use it. Instead write the recursion yourself.)

    4. A function haar xs that uses helper functions to calculate the 1-dimensional Haar wavelet on the list xs. See homework 2 for a description of the Haar wavelet.

      NOTE: At some point in your implementation, you're likely to write:

      log (length xs),

      where xs is a list. You'll get an error about (Floating Int). The trouble is that the length function returns an Int, but the Int type doesn't "implement" floating point operations, and so cannot be used as an argument to log. Here's what you want to write instead:

      log (fromIntegral (length xs))

Turn-in Instructions

Turn in your work by committing it to your SVN repository.