Dec 9, 2013 - Haskell Exam, for fun and profit

Comments

My solution to a Haskell exam

Please keep in mind, that all the source is untested (as it would be in a real exam situation). If there are errors, I'm happy if you let me know.

Exercise 1

Give the type of the following expressions: Just, Just Nothing, Just (Just True), Just Just, Just (Just Just)

I think, the easiest way to do this, is by starting to guess the type of the term in brackets. At least for the more complicated ones.

If the first type is clear, the rest should be straight forward.

    Just :: a -> Maybe a
    
    Just Nothing :: Maybe (Maybe a)
    
    Just (Just True) :: Maybe (Maybe Bool)
    
    Just Just :: Maybe (a -> Maybe a)
    
    Just (Just Just) :: Maybe (Maybe (a -> Maybe a))

Exercise 2

Write a function catMaybes :: [Maybe a] -> [a], that drop's all the Nothing values and only returns a list of the value within the Just constructor.

Here you only have to parse the list, item by item. If you encounter a Just constructor, take the value inside and put it in the list. Than go on with the rest-list.

    catMaybes :: [Maybe a] -> [a]
    catMaybes []            = []
    catMaybes ((Just x):ms) = x : (catMaybes ms)
    catMaybes (_:ms)        = catMaybes ms

Exercise 3

Write a function mapMaybe :: (a -> Maybe b) -> [a] -> [b]. The supplied function produces Maybe values. If it produces an Just b, then put the b into the result list, otherwise do nothing.

    mapMaybe :: (a -> Maybe b) -> [a] -> [b]
    mapMaybe f (x:xs)
        | (Just _) == f x 
        = x : (mapMaybe f xs)
    
        | otherwise
        = mapMaybe f xs

Exercise 4

Write a function id :: a -> a, that returns arguments unchanged.

    id :: a -> a
    id x = x 

Exercise 5

Write a function null :: [a] -> Bool, that returns True, if the list is emtpy.

    null :: [a] -> Bool
    null [] = False
    null otherwise = True

Exercise 6

Write a function map :: (a -> b) -> [a] -> [b], that applies the supplied function to all the arguments of the supplied list.

    map :: (a -> b) -> [a] -> [b]
    map f []     = []
    map f (x:xs) = f x : (map f xs)

Exercise 7

Write a function concat :: [[a]] -> [a], that tears down a list of lists, to a simple list.

    concat :: [[a]] -> [a]
    concat (x:xs) = x ++ (concat xs)

Exercise 8

Write a function length :: [a] -> Int, that returns the length of a list

    length :: [a] -> Int
    lenght []     = 0
    length (_:xs) = 1 + (length xs)

Exercise 9

Write a function any :: (a -> Bool) -> [a] -> Bool, that takes a predicate function, and returns true, if in the list is any element that supports that.

    any :: (a -> Bool) -> [a] -> Bool
    any _ [] = False
    any p (x:xs) 
        | (p x) == True 
        = True
    
        | otherwise 
        = any p xs

Exercise 10

Write a function all :: (a -> Bool) -> [a] -> Bool, that takes a predicate function, and returns true, only if all elements of the list support the predicate function.

    all :: (a -> Bool) -> [a] -> Bool
    all _ [] = True
    all p (x:xs)
        | p x == True
        = all p xs
    
        | otherwise
        = False

Exercise 11

Write a function concatMap :: (a -> [b]) -> [a] -> [b], that supplies a function to any element of a list, and concat's the results.

    concatMap :: (a -> [b]) -> [a] -> [b]
    concatmap _ []     = []
    concatMap f (x:xs) = f x ++ (concatMap f xs)

Exercise 12

Write a function filter :: (a -> Bool) -> [a] -> [a], that returns only those elements of a list, that support the predicate.

    filter :: (a -> Bool) -> [a] -> [a]
    filter _ [] = []
    filter p (x:xs) 
        | p x == True
        = x : (filter p xs)
    
        | otherwise
        = filter p xs

Exercise 13

How to use the filter function, to get all the strings from a list of string, that contain an 'a'?

    stringsWithA :: [String] -> [String]
    stringsWithA = map $ filter (== 'a')

Exercise 14

How to use the filter function, to get a list of lists, where all lists are longer than 10?

    listLonger10 :: [[a]] -> [[a]]
    listLonger10 = map $ filter $ (>=10) . length

Exercise 15

Give the type of the following expression: filter (='a')=, filter ((>10) . length), filter ((='a') . head . fst . fst)=

    filter (=='a') :: String -> String
    filter ((>10) . length) :: [[a]] -> [[a]]
    filter ((=='a') . head . fst . fst) :: (([String], a), b)

Exercise 16

The following data type describes a tree. It's nodes hold lists of values, and it's leafs might hold values.

    data Tree a = Br [a] (Tree a) (Tree a) | Lf (Maybe a)
  1. What is the kind of Tree? What is the type of Br, and of Lf?
        > :kind Tree
        Tree :: * -> *
        
        > :type Br
        Br :: [a] -> Tree a -> Tree a -> Tree a
        
        > :type Lf
        Lf :: Maybe a -> Tree a

The kind is of order 2, because there is only one type needed to produce a second one.

With the type constructor Br, something of type Tree a is produced. In order to do so, a [a], and 2 Tree a are needed.

  1. Write a function tree2lst, that writes all values of a tree into a list.
    tree2lst :: Tree a -> [a]
    tree2lst (Br as lt rt)  = (tree2lst lt) ++ as ++ (tree2lst rt)
    tree2lst (Lf (Just a))  = [a]
    tree2lst (Lf (Nothing)) = []
  1. Write an instance of Eq for Tree a
    instance (Eq a) => Eq (Tree a) where
        (Br as lt rt) == (Br as' lt' rt')
            | as == as' 
            = (lt == lt') && (rt == rt')
    
            | otherwise
            = False
    
        (Lf a) == (Lf a')
            | a == a'
            = True
    
            | otherwise
            = False

These trees are equal, if there are two branches, with equal lists, and also if both sub-trees are equal, too.

They are also equal, if they are two leafs with equal value, and also if both have no value.

Otherwise, the trees are unequal.

  1. Write an instance of Functor for Tree a
    instance Functor Tree where
        fmap f (Br as lt rt)
            = (Br (map f as) (fmap f lt) (fmap f rt))
    
        fmap f (Lf (Just a))
            = (Lf (Just (f a)))
    
        fmap _ (Lf Nothing)
            = (Lf Nothing)

Ok, Functor want's you, to write an fmap function. That function awaits a function, which is executed on every value inside the tree.

The function is mapped over the list of a branch, and is propagated to the sub-trees via fmap.

The propagation stops at the leafs.

  1. Write a fold function foldTree for the Tree a type
    foldTree :: (b -> a -> b) -> b -> (Tree a) -> b
    foldTree f n (Br as lt rt)
        = (foldl f (foldTree f (foldTree f n lt) rt) as)
    
    foldTree f n (Lf (Just a))
        = f n a
    
    foldTree _ n _
        = n

To fold something means, to tear a structure down. Therefore a function is used, that can consume a value of the tree at a time. That value, together with the result so far, is computed into the next result so far.

For the first calculation, a initial value is also needed.

That initial value is used, in combination with the left sub-tree, to calculate the result so far from the left tree. That result is used, together with the right tree, to calculate the next result so far.

At last, that result is supplied to a fold function for lists, to calculate a final result.

  1. With the help of foldTree, write a sumTree function, that sums

    all up all values inside the tree.

    foldTree (+) 0

If Foldtree is supplied with the addition function, and 0, the initial calculation would be a value of the tree plus 0. That is then added to the next value of the tree, until all values are consumed. The last result is the final result.

17 With the data type

    data Either a b = Left a | Right b
  1. Write an instance of Functor for Either
    instance Functor (Either a) where
        fmap _ (Left a) 
            = Left a
    
        fmap f (Right b)
            = (Right (f b))

Again, Functor needs a definition of the fmap function. fmap takes a function, that transforms an inner value, and a capsuled value. It executes the function on the inner value of the capsule, and puts the result back into the capsule.

Keep in mind, that you only have to take action on the Right side, because the Left side is constrained to a.

  1. Write an instance of Monad for Either
    instance Monad (Either a) where
        (>>=) (Right a) f
            = (f a)
    
        (>>=) (Left x) _
            = (Left x)
    
        return x
            = (Right x)

For Monad a combination operator and a capsule operator must be defined. Again, only the Right side must be calculated, the Left side is constrained.

The capsuling returns everything supplied also only to the Right constructor.

18 Write monadic versions for list functions

  1. Write a monadic version filterM
    filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
    filterM f [] = return []
    filterM f (a:as)
        = f a >>= (\n -> let x = filterM f as 
                         in if n == True 
                            then x >>= (\x' -> return (a:x')) 
                            else x)

The function returns just a monadic version of the empty list, if the empty list is supplied.

For all other lists, the predicate function is executed on the first element of the list. The result is passed into a new function. There a is added to the result list, only if f a resulted in true.

  1. Write a monadic version mapM
    mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
    mapM f [] = return []
    mapM f (a:as) 
        = f a >>= (\n -> let x = mapM f as
                        in x >>= (\x' -> return (n:x')))    

The scheme is the same here as in filterM. The supplied monadic function is applied to the first element of the list. The calculated value is then bound, via a lambda expression, to the identifier n. mapM is executed on the rest list. The value n is than appended to the result of the inner mapM.

  1. Write a monadic version zipWithM
    zipWithM :: (Monad m) => (a -> b -> m c) -> [a] -> [b] -> m [c]
    zipWithM _ []     _ = return []
    zipWithM [] _     _ = return []
    zipWithM f (a:as) (b:bs)
             = f a b >>= (\n -> let x = zipWithM f as bs
                               in  x >>= (\x' -> return (n:x')))

Again, the schema is here exactly the same, as in the previous two. Calculate the first value, and bind it to the rest values.

  1. Write a function, that applies a function embedded in a monad, to values inside that monad.
    ap :: (Monad m) => m (a -> b) -> m a -> m b
    ap f x = f >>= (\f' -> (x >>= (\x' -> return (f' x'))))

Here, obviously f must be executed on x. Therefore both are catched within the prime variants and are then applied.

The result is then packed back inside the monad.

19 Write text file processing functions

Assume, that there is a test.txt file in the actual directory.

  1. Write a program to count the lines within test.txt
    lineNums :: IO Int
    lineNums
        = do file <- readFile "/tmp/test.txt"
             return $ length . lines $ file

The first thing would always be, to read the file into file. Then the lines function splits the file string into it's lines. After that, the length is the line count.

  1. Write a function, that counts the number of words with more than 2 letters.
    countWordsLonger2 :: IO Int
    countWordsLonger2
        = do file <- readFile "/tmp/test.txt"
             ws   <- return $ words file
             return $ length $ filter ((>2) . length) ws

The file is read. Then the content is split up into words. With filter only the words, that have a length that is greater 2 (>2) . length, are returned. The length of that list is the number of such words.

  1. Write a function that prints the lines that contain an 'a'
    printLinesWithA :: IO ()
    printLinesWithA
        = do file <- readFile "/tmp/test.txt"
             ls   <- return $ lines file
             ls'  <- return $ filter (foldl fn False) ls
             putStrLn $ unlines ls'
             return ()
        where fn _ 'a'  = True
              fn r _    = r

Here the file is read and split up into it's lines. With filter, some lines are filtered out. Which, is determined by a fold, that returns False if there is no 'a' within the line, and True otherwise. These lines are then printed with putStrLn.

  1. Write a function, that returns the longest line, that does not contain an 'a'.
    lineContains :: Char -> String -> Bool
    lineContains c = foldl (\r n -> if n == c then True else r) False
    printLongestLineWithoutA :: IO ()
    printLongestLineWithoutA
        = do file    <- readFile "/tmp/test.txt"
             ls      <- return $ lines file
             ls'     <- return $ filter (not . lineContains 'a') ls
             longest <- return $ foldl (\r n -> if length n > length r then n else r) "" ls'
             putStrLn longest
             return ()

First of all, the fold fn function from 19.3 is here put into a helper function, called lineContains. That function takes a character and a string and returns a boolean value, that indecates, if the char is within that line.

Then the actual function reads the file, and splits it into lines. These lines are then filtered for lines that do not contain an 'a'.

That result contains all possible lines and another fold is used to break it down to only one line, the longest line.

  1. Write a function, that returns the number of words of the line with the most words.
    longestLineWordCount :: IO Int
    longestLineWordCount
        = do file    <- readFile "/tmp/test.txt"
             ls      <- return $ lines file
             putStrLn $ return $ foldl fn 0 (words ls)
        where fn r n | n > r     = n
                     | otherwise = r

Again, a simple fold is used, to return the number of words of the longest line. The fold compares the actual highest number of words, with that of the next line. Only if the next line contains more words, than the actual line, the actual number is taken.

  1. Write a function, that returns the longest word
    longestWord :: IO ()
    longestWord
        = do file    <- readFile "/tmp/test.txt"
             ws      <- return $ words file
             putStrLn $ return $ foldl fn "" ws
             return ()
        where fn r n | (length n) > (length r) = n
                     | otherwise = r

Here is the file split into it's words. Then with a fold, only the longest word is passed.