Programming Languages, Fall 2013
HW1 - Basic Haskell
Due electronically on Blackboard on Monday Sep 9, 11:59pm.

Expected Amount of Work for an average student: 6-8 hours.

Textbooks for References:
[1] Learn You a Haskell for Great Good:
http://learnyouahaskell.com/chapters

[2] CLRS: Introduction to Algorithms, MIT Press:
http://en.wikipedia.org/wiki/Introduction_to_Algorithms

Before you start, download and install GHC on your own computer.

You can also install Emacs Haskell mode (optional but recommended):
http://www.haskell.org/haskellwiki/Emacs/Installing_haskell-mode

0. (trivial) Implement the gcd function recursively.

   ghci> gcd 10 15
   5

1. (trivial) Write two simple implementations of the builtin length function:
   a) using recursion (and pattern matching)
   b) using list comprehension and sum

2. (trivial) Implement a forall function which checks if a property holds for 
   every single element of a list. It takes a predicate p (a one-argument 
   function returning a boolean) and a list l, and returns a Bool:

   ghci> forall (>=3) [10, 11, 15]
   True

   ghci> forall (\x -> x<3) [5, 1, 2]
   False

3. (easy) Write a function app that is equivalent to the built-in list 
   concatenation function ++.
   a) make sure your implementation runs in linear-time
   b) what's wrong with the following implementation? what's the time complexity?
   
   app a [] = a
   app a (x:xs) = app (a++[x]) xs

4. (easy) An interleaving of two lists contains all elements from both lists, 
   with the constraint that any two items from the same list are still in the same order.
   
   ghci> interleave [1,2] [3,4]
   [[1,2,3,4],[1,3,2,4],[1,3,4,2],[3,1,2,4],[3,1,4,2],[3,4,1,2]]

   ghci> interleave [1,2] []
   [[1,2]]

   ghci> length (interleave "ab" "cdef")
   15

5. (medium) Write a function that takes a list as argument and returns a list
   containing all permutations of the input list:

   ghci> perm [1,2,3]
   [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

6. (easy-medium) Implement mergesort.
   
   ghci> mergesort [2,4,1,5,3]
   [1,2,3,4,5]

   hint: you'll need to implement a recursive mergesorted function:

   ghci> mergesorted [1,2] [3,4,5]
   [1,2,3,4,5]
   
   What is the (average case and worst case) complexity of your code?   

7. (easy) Implement quickselect: return the kth smallest element of a list.
   (see CLRS, Section 9.2, for details if you're not familiar with this).

   ghci> qselect 2 [3,10,4,7,19]
   4

   What is the (average case and worst case) complexity of your code?   

8. (easy-medium) Implement a recursive but linear-time fibonacci function using 
   the idea of "tail-recursion" as in the reverse function from the slides.

9. (in your own words) Compared to imperative programming, what aspects of 
   functional programming do you like the most, and what do you dislike the most?

Debriefing (required!): --------------------------

1. Approximately how many hours did you spend on this assignment?
2. Would you rate it as easy, moderate, or difficult?
3. Did you work on it mostly alone, or mostly with other people?
4. How deeply do you feel you understand the material it covers (0%–100%)? 
5. Any other comments?

This section is intended to help us calibrate the homework assignments. 
Your answers to this section will *not* affect your grade; however, skipping it
will certainly do.