CS 3040, Exercise 3: Haskell Functions

Write functions as described below. Note you will want to name the file as "Ex3.hs". The code will not be graded for style issues. Use if or pattern matching to write the functions, but do not use higher order functions like map and filter and do not use list comprehensions. You may work with others on this exercise, but each must submit their own work.

1. Implement the (two-argument) Ackermann Function as ack. Note you probably won't want to test it on examples like ack 4 2. If you've already started it, Control-C will quit :-)!
• The notation on the website is a little different. The case A(m + 1, 0) = A(m, 1) is equivalent to saying that if m is greater than 0, then recursively call ackerman's function with m - 1. For example, it could be interepreted as A(p, 0) = A(p - 1, 1).
2. Write a function first_two which takes a list of items and returns a pair containing the first and second. You must either use patterns or head and tail in your answer; do not use !! or take. You can assume the list has at least two elements.
3. Write a function first_even which takes a list of numbers and returns the first even number. You can use even in your solution. Your solution must be recursive; that is, do not use operations like filter or find. Assume the list has at least one even number. Note that your returned value must be a single number, not a list containing a number.
4. Write a function swapPairs which takes a list of items and swaps every other pair. If the list has an odd length, leave the last item alone. For example, swapPairs [1, 3, 5, 8, 13] would return [3, 1, 8, 5, 13]. Again, you must implement your own recursive solution; do not use list library operations and do not use list comprehensions. That is, the only operations you can use on lists are ++, :, head, and tail.

Submit your solution to esubmit as ex3haskell. See below for details.

Hints

• A common problem students encounter in this lab is determining where to put parentheses in function calls. The key is to think of parentheses as surrounding the call, not surrounding the parameters. For example, given

          max a b = if a > b then a else b
          sqr x = x * x
  

  then the following expressions all generate errors:
  • max sqr 3 sqr 9 -- tries to apply max to 4 arguments
  • max(sqr 3, sqr 9) -- applies max to a single argument, a pair (9, 81).
  However, the following expressions do work:
  • max (sqr 3) (sqr 9)
  • max (max 9 10) 2
  • if max (max 9 10) 2 > 9 then "a" else "b"
  • sqr(4) -- this works because the parens aren't affecting anything; it's like writing 3 + (5) vs. 3 + 5 in C++.
  In general, think of parentheses in Haskel as only being used to group expressions just as you use them in code like (a + b) * c so a + b is computed first. It's a good practice to never put the parenthesis right after the function name so you avoid falling into the trap of thinking you need to use them for function calls.
• If you are having challenges about where to start, start by implementing factorial:

          fact n = if n <= 0
                   then 1
                   else n * (fact (n - 1))
  

  Then fact 5 should return 120.
• Common question: how to check multiple conditions with if.

          if p
          then x
          else if q
               then y
               else z
  

  Note how indentation is used to ensure every then has an else.

Submitting

Place your code in the Ex3.hs and put at the top (before any functions you define) the line

        module Ex3 where

Esubmit already has the file with a main in it, and this line allows the main file to "include" your file. The magic line says you're defining a module named "Ex3" (the capitalization is important in both the filename and the module declaration!) and that you are exporting all definitions.