Functional Programming Homework

length [] = 0
length (x:xs) = 1 + length xs

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

fac 0 = 1
fac n = n * fac (n - 1)

More Infinite Lists

Infinite lists can be used to produce values, one of which may then be selected. To select elements, we use take, defined as

take 0 l = []
take n [] = []
take n (x:xs) = x : take (n - 1) xs

Primes

The infinite list of primes, using the Sieve of Eratosthenes, is

primes = sieve [2 ..]
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]

Where y `mod` x produces the remainder of dividing y by x.

Selecting the first five prime numbers is, thus,

take 5 primes

Factorials

There exists a function, zipWith, that takes a function of two arguments, and two lists of arguments, and applies the function to the elements of the list in turn, producing a list. This is defined as

zipWith f [] [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

For example,

listSums l = out
             where
             out = 0 : zipWith (+) l out

Here, listSums can be used to produce the running sum of a list of numbers of any length, including infinite length lists (if you have the time).

Using zipWith, we can define the infinite list of factorials thus:

facs = 1 : zipWith (*) [1..] facs

And, using the infinite list, define the factorial function, fac, as

fac n = last (take 5 facs)

Where last returns the last element of a list.

Function Composition

There exists an infix operator, ., pronounced "compose", defined such that

f . g x = f (g x)

For example,

twice f = f . f
add1 = (1 +)

Such that evaluating

(twice add1) 12

Produces

(twice add1) 12
(add1 . add1) 12
add1 (add1 12)
add1 13
14

Homework

1. Define iter, which takes an integer, n, a function of one argument, f, and a base value, x. iter applies the f to itself n-1 times, then applies f to x. For example, iter 3 f x produces f (f (f x)), and iter 0 f x produces x.
2. Define minValue, which takes a function, f, that takes an integer and returns an integer, and an integer, n. minValue determines the minimum value of f when applied to all the integers from 0 to n. For example, minValue add1 5 produces 1, which is the smallest value add1 produces when applied to each number in [0,1,2,3,4,5].
3. Observe map add1 (map add1 ls), map fac (map add1 ls), and other maps over maps. Can you conclude a general property about map f (map g ls) that can be written using only one map?
4. When the list of primes were defined, the only case for the sieve function is one where the list is not empty. Why?