Haskell track: assignment 2: basics

Goals

In this assignment you will continue learning the basics of Haskell by writing a lot of simple functions.

Language concepts covered this week

• recursion
• higher-order functions
• pattern matching
• lists and list functions
• algebraic data types

Reading

Read the first four chapters of the Gentle Introduction to Haskell if you haven't already.

Program to write

For this week, you will be solving a number of simple problems by writing a bunch of simple functions in a file called lab2.hs. We've provided a template for your code in this file. What you have to do is to fill in the function definitions marked "TODO". In each case, we supply the type signature of the function which your code has to adhere to.

Here are the problems you have to solve:

• Summing a list of integers recursively.
• Summing a list of integers in terms of foldl.
• Multiplying a list of integers in terms of foldr.
• Appending lists in terms of foldr. The resulting list's elements should be in the same order as the original lists i.e. this function should have the same semantics as the "++" operator.
• Insertion sort on a list of integers.
• A "map" function map2 that works on two lists. This is trivially done using the zipWith function, so don't use that.
• An infinite list of factorials, using map2.
• An infinite list of prime numbers using list comprehensions.
• Some functions on a tree data structure (supplied):
  • Counting the leaves in a tree.
  • Mapping over a tree.
  • A fold function on a tree.

To hand in

Your program lab2.hs.

Supporting files

• The template for your code. Just fill in the parts marked "TODO" with your code. Make sure you adhere to the function signatures as written.

References

• A Gentle Introduction to Haskell, by Hudak, Peterson and Fasel, chapters 1 to 4.