Pretend that Haskell does not have a built-in list type.
a) Implement lists using a data type List a.
Comparison operators (e.g. ==, /=, >, <) should work on your
class and should compare lists lexicographically.
b) Declare that List is an instance
of the type class Functor.
c) Write a function that performs a right fold
over a List a. It should have this type:
foldr :: (a → b → b) → b → List a → b
a) Declare a type class Queue that represents a queue of elements of type 'a'. It should have an empty queue value, plus operations to enqueue and dequeue values.
b) A list can act as a queue, though it is not particularly efficient. Declare that the built-in list class is an instance of Queue.
c) Implement a more efficient queue type using a pair of lists. Declare that it is an instance of Queue. Also declare that it is an instance of Functor.
a) Declare a type class Dictionary that represents a mapping from element of type 'k' to type 'v'. It should have an empty dictionary value, plus operations to set or get the value for a given key. Retrieving the value of an absent key should return Nothing. Assume that keys are orderable.
b) Declare a datatype Assoc k v representing an association list, i.e. a list of key-value pairs. Declare that Assoc is an instance of Dictionary. Also declare that it is an instance of Functor. fmap should affect the values (not the keys) stored in the association list.
c) Declare a binary tree type that can map keys to values. Declare that it is an instance of Dictionary. Also declare that it is an instance of Functor. fmap should affect the values (not the keys) stored in the tree.
Write a Haskell program that reads a rectangular matrix of integers from standard input. For example:
3 9 8 2 5 12 1 7 4
The program should print out the matrix rotated 90 degrees to the right:
1 2 3 7 5 9 4 12 8
Write a Haskell program that takes three command-line arguments, which are the names of two input files and one output file. The input files are sorted files of integers, with one integer per line. The function should merge the contents of the files and write them to the output file, again with one integer per line.
Write a Haskell program that is like the command-line utility 'grep'. It should take two command-line arguments: a string to search for, plus a filename. It should print out all lines in the file that contain the given string.
Recall that Pascal's triangle looks like this:
1
1
1
1 2 1
1 3 3 1
1 4 6 4 1
.
. .
Construct Pascal's triangle as an infinite list of lists:
[[1],
[1,
1],
[1,
2,
1],
[1,
3,
3,
1],
...]
Construct an infinite list of all prime numbers using the Sieve of Eratosthenes.