When pattern matching on lists, parenthesis must surround the pattern. For example,

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)

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

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

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.

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

- 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`

. - 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]`

. - 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`

? - When the list of primes were defined, the only case for the
`sieve`

function is one where the list is not empty. Why?