List comprehension
Using a list comprehension, give an expression that calculates the sum
12 + 22 + . . . 1002.
let ss100 = sum [ x^2 | x <- [1..100]]
replicate
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]
It's like generating n times the same input.
replicate :: Int -> a -> [a] replicate n x = [x | _ <- [1..n]]
Here are some examples:
*Ch5> replicate 10 'a' "aaaaaaaaaa" *Ch5> replicate 10 1 [1,1,1,1,1,1,1,1,1,1]
pyths
A triple (x, y, z) of positive integers is pythagorean if x2 + y2 = z2.
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)]
We search all the triplets (x, y, z) such as (x,y,z) in [1..n]3 and x2+y2=z2:
pyths :: Int -> [(Int, Int, Int)] pyths n = [(x, y, z) | x <- m, y <- m, z <- m, x^2 + y^2 == z^2 ] where m = [1..n]
perfect numbers
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]
We are first given the definition for a perfect number so we implement it:
perfect :: Int -> Bool perfect m = sum [ y | y <- factors m, y /= m ] == m
Note We can iterate over the perfect implementation and change it using the init function (drops the last element of a list):
perfect :: Int -> Bool perfect m = sum (init (factors m)) == m
Note
- The implementation is litteraly the definition.
- we have the factors function that already computes the factors of a number, so we reuse it.
We can now define the main function using the previous perfect function:
perfects :: Int -> [Int] perfects n = [x | x <- [1..n], perfect x]
Comprehension
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.
Apparently, from the hint, is possible to nest the list comprehensions.
We will go one step at a time, first nesting:
Prelude> [[(x,y) | x <- [1,2,3]] | y <- [4,5,6]] [[(1,4),(2,4),(3,4)],[(1,5),(2,5),(3,5)],[(1,6),(2,6),(3,6)]]
Indeed, now if we use concat, this will give us what we want:
Prelude> concat [[(x,y) | x <- [1,2,3]] | y <- [4,5,6]] [(1,4),(2,4),(3,4),(1,5),(2,5),(3,5),(1,6),(2,6),(3,6)]
which is equal to the first result if we do not consider the list order:
Prelude> [(x, y) | x <- [1, 2, 3], y <- [4, 5, 6]] [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
positions
Redefine the function positions using the function find.
Recall the find definition:
find :: Eq a => a -> [(a,a)] -> [a] find k hs = [v | (k', v) <- hs, k == k']
We will generate the list of couples (value, position) then feed this to the find function. This will then compute all the values associated (their position) to the search value v:
positions2 :: Int -> [Int] -> [Int] positions2 v vs = find v (zip vs [0..n]) where n = (length vs) - 1
Here is the comparison between the first implementation and the new one:
*Ch5> positions2 1 [0,1,3,4,2,1,3] [1,5]
scalarproduct
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:
sum i=0..n−1 (xsi ∗ ysi)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
We first create the list containing the couple (x, y) then we (lazily) compute the product for each couple, then sum them all:
scalarproduct :: [Int] -> [Int] -> Int scalarproduct xs ys = sum [x * y | (x, y) <- zip xs ys]
As an example:
*Ch5> scalarproduct [1,2,3] [4,5,6] 32
Caesar cipher
Modify the Caesar cipher program to also handle upper-case letters.
caesar program
Recall the caesar program:
low2int :: Char -> Int low2int c = C.ord c - C.ord 'a' int2low :: Int -> Char int2low l = C.chr (C.ord 'a' + l) shift :: Int -> Char -> Char shift n c | C.isLower c = int2low ((n + low2int c) `mod` 26) | otherwise = c encode :: Int -> String -> String encode n cs = [shift n c | c <- cs]
Here is a sample or executing the first implementation:
*Ch5> encode 3 "functional programming rocks!" "ixqfwlrqdo surjudpplqj urfnv!"
Upper
We then have to add functions that deals with upper case too.
upp2int
For this, we can add functions upp2int (dual of low2int) and int2upp (dual of int2low).
As their behaviour is similar, we can extract a char2Int function which takes the char c to transform and a reference char.
char2int :: Char -> Char -> Int char2int c cr = C.ord c - C.ord cr
The definition of low2int and upp2int becomes:
low2int :: Char -> Int low2int c = char2int c 'a' upp2int :: Char -> Int upp2int c = char2int c 'A'
int2upp
The same thing can be tell for the int 2 letter transformation:
int2char :: Int -> Char -> Char int2char l c = C.chr (C.ord c + l) int2low :: Int -> Char int2low l = int2char l 'a' int2upp :: Int -> Char int2upp l = int2char l 'A'
shift
The function shift evolves to add a guardian entry to check on the Upper case property of a char. Again the behaviour is similar, only the reference char changes.
So we can extract a higher order function shiftchar:
shiftchar :: (Int -> Char) -> (Char -> Int) -> Int -> Char -> Char shiftchar i2c c2i n c = i2c ((n + c2i c) `mod` 26)
The function shift becomes then:
shift :: Int -> Char -> Char shift n c | C.isLower c = shiftchar int2low low2int n c | C.isUpper c = shiftchar int2upp upp2int n c | otherwise = c
encode
At last the function encode does not change.
Check
And the encoding final with upper case:
*Ch5> encode 3 "Functional programming ROCKS!" "Ixqfwlrqdo surjudpplqj URFNV!"
Which is definitely the same as before but with upper letters.
final
Here is the final result:
char2int :: Char -> Char -> Int char2int c cr = C.ord c - C.ord cr low2int :: Char -> Int low2int c = char2int c 'a' upp2int :: Char -> Int upp2int c = char2int c 'A' int2char :: Int -> Char -> Char int2char l c = C.chr (C.ord c + l) int2low :: Int -> Char int2low l = int2char l 'a' int2upp :: Int -> Char int2upp l = int2char l 'A' shiftchar :: (Int -> Char) -> (Char -> Int) -> Int -> Char -> Char shiftchar i2c c2i n c = i2c ((n + c2i c) `mod` 26) shift :: Int -> Char -> Char shift n c | C.isLower c = shiftchar int2low low2int n c | C.isUpper c = shiftchar int2upp upp2int n c | otherwise = c encode :: Int -> String -> String encode n cs = [shift n c | c <- cs]