exercises5.txt

Programming in Haskell by Graham Hutton Exercises - Chapter 5

1. Using a list comprehension, give an expression that calculates the sum 1^2 + 2^2 + ... 100^2 of the first one hundred integer squares.

sum [x ^ 2 | x <- [1..100]]
>338350

2. In a similar way to the function length, show how the library function replicate :: Int -> a -> [a] that produces a list of identical elements can be defined using a list comprehension.  For example:
> replicate 3 True
[True, True, True]

replicate' :: Int -> a -> [a]
replicate' n a = [a | _ <- [1..n]]

eg
replicate' 7 'a'
"aaaaaaa"


3. A triple (x, y, z) of positive integers is pythagorean if x^2 + y^2 = z^2. Using a list comprehension, define a function pyths :: Int -> [Int, Int, Int)] that returns the list of all pythagorean triples whose components are at most a given limit. For example:

> pyths 10
[(3,4,5), (4,3,5),(6,8,10),(8,6,10)]

pyths :: Int -> [(Int,Int,Int)]
pyths n = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [1..n], x ^ 2 + y ^ 2 == z ^ 2]

Not optimal because z will always be larger than x or y.

This version slightly more efficient:
pyths n = [(x,y,z) | x <- [1..n], y <- [1..n], z <- [x..n], x ^ 2 + y ^ 2 == z ^ 2]

4. A positive integer is perfect if it equals the sum of its factors, excluding the number itself. Using a list comprehension and the function factors, define a function perfects :: Int -> [Int] that returns the list of all perfect numbers up to a given limit. For example:

> perfects 500
[6,28,496]

perfects :: Int -> [Int]
perfects n = [x | x <- [1..n], sum (take (length (factors x) - 1) (factors x)) == x]

It is somewhat inefficient because it calculates factors twice for each iteration.

Bah, why did no one tell me about init.

So here is a better version.

perfects n = [x | x <- [1..n], sum (init (factors x)) == x]

This takes about a minute to run:

perfects 10000
>[6,28,496,8128]


5. Show how the single comprehension [(x,y) | x <- [1,2,3], y <- [4,5,6]] with two generators can be re-expressed using two comprehensions with single generators. Hint: make use of the library function concat and nest one comprehension within the other.

I must admit I was totally confused over this one.

[[(x,y)| y <- [4,5,6]] | x <- [1,2,3]]
>[[(1,4),(1,5),(1,6)],[(2,4),(2,5),(2,6)],[(3,4),(3,5),(3,6)]]

The trouble is of course that this is a list within a list.  The hint mentions concat which concatenates a list of lists so lets try that.

concat [[(x,y)| y <- [4,5,6]] | x <- [1,2,3]]
>[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]


6. Redefine the function positions using the function find.

positions' :: Eq a => a -> [a] -> [Int]
positions' x xs = find x (zip xs [0..n]) 
    where n = (length xs) - 1


7. The scalar product of two lists of integers xs and ys of length n is given by the sum of the products of corresponding integers.

n=1
--
\ (xsi * ysi)
/
--
i=0

In a similar manner to the function chisqr, show how a list comprehension can be used to define a function scalarproduct :: [Int] -> [Int] -> Int that returns the scalar product of two lists. For example:

> scalarproduct [1,2,3] [4,5,6]
32

scalarproduct :: [Int] -> [Int] -> Int
scalarproduct xs ys = sum [x * y | (x,y) <- zip xs ys]

8. Modify the Caesar cipher program to also handle upper-case letters.

let2int' :: Char -> Int
let2int' c = ord c - ord 'A'

int2let' :: Int -> Char
int2let' n = chr (n + ord 'A')

shift' :: Char -> Int -> Char
shift' c n  | isLower c  = int2let (((let2int c) + n) `mod` 26)
            | isUpper c  = int2let' (((let2int' c) + n) `mod` 26)
           |otherwise  = c

encode' :: [Char] -> Int -> [Char]
encode' xs n = [shift' x n | x <- xs]

And it works:
*Main> encode' "Haskell is fun" 3
"Kdvnhoo lv ixq"
*Main> encode' "Kdvnhoo lv ixq" (-3)
"Haskell is fun"


Admittedly there is quite a bit of duplication between the upper and lower case conversion variants.