PFP Laboratory 4

List comprehension

Using the list comprehension implement following functions:

• Create a function that generates a list of all odd numbers in given interval.

oddList :: Int -> Int -> [Int]

*Main> oddList 1 10   
[1,3,5,7,9]

oddList :: Int -> Int -> [Int]
oddList a b = [ x |x<-[a..b], odd x]

• Create a function that removes all upper case letters from a string.

removeAllUpper :: String -> String

*Main> removeAllUpper "ABCabcABC"
"abc"

import Data.Char

removeAllUpper :: String -> String
removeAllUpper xs = [ x |x<-xs, not (isUpper x)]

• Create functions that computes union and intersection of two sets.

union :: Eq a => [a] -> [a] -> [a]
intersection :: Eq a => [a] -> [a] -> [a]

*Main> union [1..5] [3..10]
[1,2,3,4,5,6,7,8,9,10]
*Main> intersection [1..5] [3..10]
[3,4,5]

union :: Eq a => [a] -> [a] -> [a]
union xs ys = xs ++ [y| y<-ys, not (elem y xs)]

intersection ::  Eq a =>  [a] -> [a] -> [a]
intersection xs ys = [y| y<-ys, elem y xs]

More complex functions

• Create a function that count the number of occurrences of all characters from a given string.

countThem :: String -> [(Char, Int)]

*Main>countThem "hello hello hello"
[('h',3),('e',3),('l',6),('o',3),(' ',2)]

unique :: String -> String
unique n = reverse(tmp n "") where
  tmp [] store = store
  tmp (x:xs) store | x `elem` store = tmp xs store
                   | otherwise = tmp xs (x:store)

unique' :: String -> String                   
unique' [] = []
unique' (x:xs) = x: unique' (filter (/=x)xs)

countThem :: String -> [(Char, Int)]
countThem xs = let u = unique xs
               in [(x, length (filter (==x) xs)) |x<-u]

• Create a function that generates all combinations of given length from the characters from given string. You can assume, that all character are unique and the given length is not bigger then the length of this string.

combinations :: Int -> String -> [String]

*Main> combinations 3 "abcdef"
["abc","abd","abe",...]

combinations :: Int -> String -> [String]
combinations 1 xs = [[x]| x<-xs]
combinations n (x:xs) | n == length (x:xs) = [(x:xs)]
                      |otherwise = [[x] ++ y |y<-combinations (n-1) xs ] 
                                    ++ (combinations n xs)

• Given an arbitrary type a, a test predicate of type a → Bool and a list of elements of type a, the partition function should return a pair of lists. The first member of the pair is the sublist of the original list containing the elements that satisfy the test, and the second is the sublist containing those that fail the test.

partition :: (a -> Bool) -> [a] -> ([a],[a])

*Main> partition odd [1,2,3,4,5,6]
([1,3,5],[2,4,6])
*Main> partition (\x -> False) [5,9,0]
([],[5,9,0])

• The function split is the right inverse of zip: it takes a list of pairs and returns a pair of lists.

split :: [(a,b)] -> ([a],[b])

*Main> split [(1,False),(2,False)] 
([1,2],[False,False])

• Create a function that divides a list of elements into the list of n-elements lists. Extra elements should be forgotten.

divideList :: [a] -> Int -> [[a]]

*Main> divideList "I love functional programming!" 5
["I lov","e fun","ction","al pr","ogram","ming!"]
*Main> divideList [1..20] 3
[[1,2,3],[4,5,6],[7,8,9],[10,11,12],[13,14,15],[16,17,18]]

• Given a list of elements and a single element el, create a function that returns sequences of elements greater than el.

sequences :: Ord a => [a] -> a -> [[a]]

*Main> sequences [4,5,6,8,4,1,0,2,5,8,4,5,5,3,5,8] 4
[[5,6,8],[5,8],[5,5],[5,8]]

List of lists

Consider following type representing picture:

type Pic = [String]

If you want to print this picture you can use:

pp :: Pic -> IO ()
pp x = putStr (concat (map (++"\n") x))

Picture example:

pic :: Pic
pic = [ "....#....",
        "...###...",
        "..#.#.#..",
        ".#..#..#.",
        "....#....",
        "....#....",
        "....#####"]

*Main> pp pic
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####

Create functions that:

• Flips picture veriticaly and horizontally.

flipV :: Pic -> Pic
flipH :: Pic -> Pic

*Main> pp(flipV pic)
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
#####....
*Main> pp(flipH pic)
....#####
....#....
....#....
.#..#..#.
..#.#.#..
...###...
....#....

flipV :: Pic -> Pic
flipV = map reverse 

flipV' :: Pic -> Pic
flipV' xs = [reverse x|x<-xs]

flipH :: Pic -> Pic
flipH = reverse

• Place one picture above another.

above :: Pic -> Pic -> Pic

*Main> pp(above pic pic)
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####
....#....
...###...
..#.#.#..
.#..#..#.
....#....
....#....
....#####

above :: Pic -> Pic -> Pic
above x y = x ++ y

• Place two pictures side by side (consider, that they have the same height).

sideBySide :: Pic -> Pic -> Pic

*Main> pp(sideBySide pic pic)
....#........#....
...###......###...
..#.#.#....#.#.#..
.#..#..#..#..#..#.
....#........#....
....#........#....
....#####....#####

sideBySide :: Pic -> Pic -> Pic
sideBySide xs ys = map (\(x,y) -> x ++ y)(zip xs ys) 

sideBySide':: Pic -> Pic -> Pic
sideBySide' (x:xs) (y:ys) = (x ++ y) : sideBySide' xs ys
sideBySide' _ _ = []

sideBySide'' :: Pic -> Pic -> Pic
sideBySide'' = zipWith (++)

• Rotate picture to the left and to the right.

rotateR :: Pic -> Pic
rotateL :: Pic -> Pic

*Main> pp(rotateR pic)       
.......
...#...
....#..
.....#.
#######
#....#.
#...#..
#..#...
#......
*Main> pp(rotateL pic)
......#
...#..#
..#...#
.#....#
#######
.#.....
..#....
...#...
.......

toRow :: String -> Pic
toRow xs = map (\x -> [x]) xs -- [[x]|x<-xs]

rotateR :: Pic -> Pic
rotateR [x] = toRow x
rotateR (x:xs) = (rotateR xs) `sideBySide` (toRow x)

rotateR' :: Pic -> Pic
rotateR' x = foldl1 sideBySide (reverse (map toRow x))


rotateL :: Pic -> Pic
rotateL [x] = reverse(toRow x)
rotateL (x:xs) = reverse(toRow x) `sideBySide` (rotateL xs)

rotateL' :: Pic -> Pic
rotateL' x = foldl1 sideBySide (map (reverse.toRow) x)