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 GHC version of Haskell. 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-201010-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 HaskellHomework within your local copy of your SVN repository. Using your favorite text editor, open the file functions.hs within the HaskellHomework 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.

   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 n^th Fibonacci number.
   2. Fast, recursive fastFib n function, that uses helper functions and pairs to calculate the n^th 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))

   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.

   I don't have a particular format in mind for testing. You might find something like the following code useful:

   -- Imports the IO library for printing
   import IO
   
   -- Factorial example
   fact 0 = 1
   fact n = n * fact(n-1)
   
   -- DEFINE YOUR FUNCTIONS HERE
   
   -- Defines the no-argument "test" function to run the tests, you
   -- still need to invoke it in the interpreter.  You'll need to 
   -- comment out lines below for functions that you haven't yet 
   -- implemented.
   test = do
       putStrLn "Factorial"
       putStrLn ("fact 5 = " ++ show (fact 5))
       putStrLn "Fibonacci, the slow way"
       putStrLn ("fibonacci 0 = " ++ show (fibonacci 0))
       putStrLn ("fibonacci 1 = " ++ show (fibonacci 1))
       putStrLn ("fibonacci 10 = " ++ show (fibonacci 10))
       putStrLn ("fibonacci 20 = " ++ show (fibonacci 20))
       putStrLn ("fibonacci 25 = " ++ show (fibonacci 25))
       putStrLn "Fibonacci, the fast way"
       putStrLn ("fastFib 0 = " ++ show (fastFib 0))
       putStrLn ("fastFib 1 = " ++ show (fastFib 1))
       putStrLn ("fastFib 10 = " ++ show (fastFib 10))
       putStrLn ("fastFib 20 = " ++ show (fastFib 20))
       putStrLn ("fastFib 25 = " ++ show (fastFib 25))
       putStrLn "firstN"
       putStrLn ("firstN 10 [] = " ++ show(firstN 10 []::[Int]))
       putStrLn ("firstN 10 [1] = " ++ show(firstN 10 [1]))
       putStrLn ("firstN 10 \"cat\" = " ++ show(firstN 10 "cat"))
       putStrLn ("firstN 2 \"cat\" = " ++ show(firstN 2 "cat"))
       putStrLn ("firstN 0 \"cat\" = " ++ show(firstN 0 "cat"))
       putStrLn ("firstN 0 [] = " ++ show(firstN 0 []::[Int]))
       putStrLn "Haar wavelet"
       putStrLn ("haar [8,5] = " ++ show(haar [8,5]))
       putStrLn ("haar [5,8] = " ++ show(haar [5,8]))
       putStrLn ("haar [8,5,7,3] = " ++ show(haar [8,5,7,3]))
       putStrLn ("haar [8,7,5,3] = " ++ show(haar [8,7,5,3]))
       putStrLn ("haar " ++ show [0..7] ++ " = " ++ show(haar [0..7]))
   
   -- putStrLn is the function to display a string on a line
   -- The '++' operator does list, or in this case string, concatenation
   -- The show function converts values to strings.
   

Turn-in Instructions

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