PSAS/ HaskellProgramming

You'll want to look over the Haskell Tutorial for C Programmers and some of the other tutorials that are linked from that one, but here are some basic concepts.

This declares a function named double that takes a numeric argument and returns that argument times 2:

double x = x * 2

This expression is an anonymous function that takes a numeric argument and returns that argument times 2. This kind of thing is apparently called a "section".

(* 2)

So you can use double and (* 2) interchangeably. In fact, you can define double using (* 2):

double = (* 2)

Most of the time, a list can be written like so:

[1, 2]

However, this is syntactic sugar for the following expression.

1 : 2 : []

The value [] is the empty list, and the operator ':' is called "cons" -- it takes a value on the left and a list of values on the right, and returns a new list resulting from sticking the two things together.

The list concatenation operator is '++':

[1,2] ++ [3,4] == [1,2,3,4]

Haskell provides a convenient notation for lists of particular patterns.

[1 .. 6] == [1, 2, 3, 4, 5, 6]
[1,3..6] == [1, 3, 5]

This notation includes infinite lists:

[1..]   == [1, 2, 3, 4, ...
[1,3..] == [1, 3, 5, 7, ...

It's often useful to look at the first several values in a list, especially when working with infinite lists. You can use the take function for this:

take 5 [1..] == [1..5]

Higher-order functions are those that accept functions as parameters. One standard example is map:

map (* 2) [1, 2, 3] == [2, 4, 6]
map (* 2) [1..] == [2, 4..]

(Your computer can't check that second example, because it will run forever. An inductive proof using the definition of map is left as an exercise for the reader.)

You can write the list of all positive integers yourself, recursively:

nat = 1 : map (+ 1) nat

This is a common enough way of defining lists: identify a base element, and a function from one element of the set to another; then map the function across the list that you're defining.

Function declaration allows you to pattern-match on the function's arguments. Here's a function that works like map, except it only affects the first element of the list. (We call that element the "head".)

mapHead f [] = []
mapHead f (x:xs) = (f x) : xs

So:

mapHead (* 5) [1, 2, 3] == [5, 2, 3]

Functions can be used like infix operators by surrounding the function name with back-quotes.

10 `mod` 4 == 2

But you can also define your own infix operators, and you can use all sorts of symbols for names:

a <-~/ b = if a < b then a `div` 2 else (a `div` 2) <-~/ (b * 2)
map (<-~/ 2) [1..30]

Exercises

Here are a few exercises, with solutions. They illustrate lazy evaluation (including infinite data structures), higher-order functions, parametric polymorphism, pattern matching, sections, and some common list manipulation tools.

As you do these exercises, think about how you'd perform the same tasks in an imperative language like C, C++, or Java.

1) The quicksort algorithm goes like this: given a list to sort, select and remove a "pivot element". Partition the remaining list into those elements that are less than the pivot, and those that are greater/equal. Recursively sort the two partitions. Your sorted list is: the sorted "less-than" partition, then the pivot element, then the sorted other partition. The recursive base case is that the empty list is already sorted.

Write a function "quicksort" that implements this algorithm. The "List" module provides a function called partition that you may find helpful.

2) Two sorted lists with no duplicates can be merged into a combined list that's still sorted and still has no duplicates, in O(n) time. Implement an operator named ~~ that does this.

3) The "Hamming numbers" are those numbers that can be written as

2^i * 3^j * 5^k

where i, j, and k are non-negative integers. You can define the list of all Hamming numbers by making these observations.

Write a value "hamming" that is an infinite list containing all the Hamming numbers. If your solution produces the list in sorted order, then this expression will be True:

take 9 hamming == [1,2,3,4,5,6,8,9,10]

Try evaluating

hamming !! 100000

and see how long it takes. Then evaluate it again -- it should respond instantly. If the first time wasn't noticeably slow, try adding a 0. :-)

Beware: If your solution attempts to concatenate an infinite list with another list, your code probably won't work. Testing whether this list:

[1..] ++ [0]

contains 0, for example, will never halt -- so effectively it does not contain 0.

4) Consider this data type declaration for trees:

data Tree a = Tip | Branch (Tree a) a (Tree a)

Write a function "inorder" that returns a list of "a"s resulting from an in-order traversal of such a tree.

5) Write a function "treeEqual" that tests whether two trees have the same elements, in the same order, regardless of whether the trees have the same structure.

For example, this should be True:

(Branch (Branch (Branch Tip 1 Tip) 2 Tip) 3 Tip) `treeEqual` (Branch Tip 1 (Branch Tip 2 (Branch Tip 3 Tip)))

Resources