Solutions to the Problem Sheet for LI Functional Programming - Week 5 & 6

Directories

The following solutions are written for the version of the Directory data type that we developed in the Online Lab Session. Here was the result:

data File = File {
  fileName :: String,
  fileContents :: String
} deriving (Eq,Show)

data Directory = Dir {
  dirName :: String,
  dirContents :: [ DirectoryEntry ]
} deriving (Eq,Show)

data DirectoryEntry =
    FileEntry File
  | DirEntry Directory
  deriving (Eq,Show)

1. Create your own sample directory structure

   sampleFile :: File
   sampleFile = File {
     fileName = "notes.txt",
     fileContents = "don't forget the milk!"
   }
   
   sampleDir :: Directory
   sampleDir = Dir {
     dirName = "root",
     dirContents = [
       FileEntry sampleFile,
       DirEntry Dir {
         dirName = "home",
         dirContents = [
           FileEntry File {
             fileName = "lab-ideas.txt",
             fileContents = "work on directories ..."
           },
           FileEntry File {
             fileName = "todo.txt",
             fileContents = "finish the online lab"
           }
         ]}
     ]}

2. Write a function to return a list of all the files.

   allFileNames :: Directory -> [ String ]
   allFileNames d = [ fnm | e <- dirContents d, fnm <- fileNamesOfEntry e ]
   
     where
       fileNamesOfEntry :: DirectoryEntry -> [ String ]
       fileNamesOfEntry (FileEntry f) = [ fileName f ]
       fileNamesOfEntry (DirEntry sd) = allFileNames sd

3. Here is a function to find a substring and return its index:

   import Data.List
   
   findString :: (Eq a) => [a] -> [a] -> Maybe Int
   findString search str = findIndex (isPrefixOf search) (tails str)

   Write a function to search the directory for a file containing some string.

   grep :: String -> Directory -> [(String,Int)]
   grep searchStr d = [ r | e <- dirContents d, r <- grepEntry e ]
   
     where grepEntry :: DirectoryEntry -> [(String,Int)]
           grepEntry (FileEntry f) =
             case findString searchStr (fileContents f) of
               Nothing -> []
               Just idx -> [(fileName f,idx)]
           grepEntry (DirEntry sd) = grep searchStr sd

4. Write a function to search for files by name.

   Note You may notice that it is possible to write a generic program to find all files which satisfy some given predicate. We use that approach to simplify out task later on.

   findFiles :: (File -> Bool) -> Directory -> [File]
   findFiles p d = [ f | e <- dirContents d , f <- filesInEntry e ]
   
     where
       filesInEntry (FileEntry f) | p f = [ f ]
                                  | otherwise = []
       filesInEntry (DirEntry sd) = findFiles p sd

   Now we can simply use this auxillary function as follows:

   findFilesByName :: String -> Directory -> [File]
   findFilesByName nm d = findFiles (\f -> nm == fileName f) d

5. Modify the File type to contain different types of data: binary (you may wish to look at ByteString from the Haskell prelude) and string. Write functions to find all binary or text files in the given directory structure.

   import Data.ByteString
   
   data File = File {
     fileName :: String,
     fileContents :: Either String ByteString
   } deriving (Eq,Show)
   
   isBinary :: File -> Bool
   isBinary f = case fileContents f of
                  Left _ -> False
                  Right _ -> True
   
   findBinaryFiles :: Directory -> [ File ]
   findBinaryFiles = findFiles isBinary
   
   findTextFiles :: Directory -> [ File ]
   findTextFiles = findFiles (\f -> not (isBinary f))

6. Write a function to sort the directory contents alphbetically.

   instance Ord DirectoryEntry where
     compare e f = compare (nameOf e) (nameOf f)
   
       where
         nameOf (FileEntry f) = fileName f
         nameOf (DirEntry d) = dirName d
   
   sortDir :: Directory -> Directory
   sortDir d = Dir {
     dirName = dirName d,
     dirContents = sort (map sortEntry (dirContents d))
     }
   
     where
       sortEntry (FileEntry f) = FileEntry f
       sortEntry (DirEntry sd) = DirEntry (sortDir sd)

7. Harder Write a function to print the directory contents as a text tree.

   dirTree :: Directory -> String
   dirTree d = unlines ((dirName d):go d 2)
   
   go :: Directory -> Int -> [ String ]
   go d i = concat (map (\e -> entryTree e i) (dirContents d))
   
   entryTree :: DirectoryEntry -> Int -> [ String ]
   entryTree (FileEntry f) i = [ replicate (i-1) '.' ++ "> " ++ fileName f ]
   entryTree (DirEntry sd) i = (replicate (i-1) '.' ++ "> " ++ dirName sd):(go sd (i+2))

XML

Consider the following simplified data type for representing XML documents:

data Element  = Element {
                  elName      :: String,
                  elAttribs   :: [Attr],
                  elContent   :: [Content]
                } deriving Show

data Content  = Elem Element
              | Text String
                deriving Show

data Attr     = Attr {
                  attrKey :: String,
                  attrVal :: String
                } deriving (Eq, Show)

1. Encode the following example:

   <person gender="female">
     <firstname>Anna</firstname>
     <lastname>Smith</lastname>
   </person>

   example1 :: Element
   example1 = Element {
     elName = "person",
     elAttribs = [
        Attr {
          attrKey = "gender",
          attrVal = "female"
        },
        Attr {
          attrKey = "hometown",
          attrVal = "Birmingham"
        }
     ],
     elContent = [
       Elem Element {
         elName = "firstname",
         elAttribs = [],
         elContent = [
           Text "Anna"
         ]
       },
       Elem Element {
         elName = "lastname",
         elAttribs = [],
         elContent = [
           Text "Smith"
         ]
       }
     ]
   }

2. Encode the following example:

   <note>
   <to>Tove</to>
   <from>Jani</from>
   <heading>Reminder</heading>
   <body>Don't forget me this weekend!</body>
   </note>

   example2 :: Element
   example2 = Element {
     elName = "note",
     elAttribs = [],
     elContent = [
         Elem Element {
             elName = "to",
             elAttribs = [],
             elContent = [Text "Tove"]
             },
         Elem Element {
             elName = "from",
             elAttribs = [],
             elContent = [Text "Jani"]
             },
         Elem Element {
             elName = "heading",
             elAttribs = [],
             elContent = [Text "Reminder"]
             },
         Elem Element {
             elName = "body",
             elAttribs = [],
             elContent = [Text "Don't forget me this weekend!"]
             }
         ]
     }

3. Write a function which returns all elements containing only text in their content

   Again, we will use the strategy of first writing a generic find function. We can then specialize it to the cases we like.

   findAllElements :: (Element -> Bool) -> Element -> [Element]
   findAllElements p root | p root = root:childEls
                          | otherwise = childEls
   
     where
       contentEls :: Content -> [Element]
       contentEls (Text _) = []
       contentEls (Elem c) = findAllElements p c
   
       childEls :: [ Element ]
       childEls = [ el | child <- elContent root ,
                         el <- contentEls child ]
   

   Now we write a predicate to detect elements with only text children and then use the previous function:

   hasOnlyTextChildren :: Element -> Bool
   hasOnlyTextChildren e = all isText (elContent e)
   
     where isText :: Content -> Bool
           isText (Text _) = True
           isText _        = False

findAllTextOnlyElements :: Element -> [Element]
findAllTextOnlyElements = findAllElements hasOnlyTextChildren
```

4. Write a function which returns all elements which have exactly one child element

   findAllOneChildElements :: Element -> [Element]
   findAllOneChildElements = findAllElements (\e -> length (elContent e) == 1)

5. Write a function which searches for all elements with a given attribute key

   findAllElementsWithAttr :: String -> Element -> [Element]
   findAllElementsWithAttr attr =
     findAllElements
       (\e -> any (\a -> attrKey a == attr) (elAttribs e))

6. Write a function which formats the XML data to a string

   printXml :: Element -> String
   printXml e = unlines (printElement e 0)
   
   printElement :: Element -> Int -> [ String ]
   printElement e i =
     [indentation ++ "<" ++ unwords (elName e : map printAttrib (elAttribs e)) ++ ">"] ++
     map (\s -> indentation ++ s) (concat (map (\c -> printContent c (i+2)) (elContent e))) ++
     [indentation ++ "</" ++ elName e ++ ">"]
   
     where indentation = replicate i ' '
   
   printAttrib :: Attr -> String
   printAttrib a = attrKey a ++ "=\"" ++ attrVal a ++ "\""
   
   printContent :: Content -> Int -> [ String ]
   printContent (Text s) i = [ "  " ++ s ]
   printContent (Elem e) i = printElement e i

---

You can continue with examples like the above by inventing your own transformations and queries on the directory and XML examples. Be creative!