Talen en Compilers lab 0

This lab is for practice only and should not be handed in. You get a bonus point if you show that you work on it to the TA of your lab session.

Some of these exercises are quite hard, do not be discouraged if you get stuck.

By the end of the course you should find all of these exercises easy.

Tasks

(0 pt)

Re-implement the Prelude's conversion functions
```
unwords :: [String] -> String
words :: String -> [String]
```
which convert a list of strings into a list of space-separated words, and split a string into words based on where spaces occur.

Try to write these functions yourselves, in the following ways:
- unwords using direct recursion
- unwords using foldr
- words using recursion and helper functions like takeWhile
- words using foldr (It is surprising that this can be done. Hint: the operator that handles a single letter must handle a space in a different way than another character.)
(0 pt)

There are two types of fold-functions: foldr and foldl. They work as follows:
```
foldr (+) e [a, b, c, d] = a + (b + (c + (d + e)))
foldl (+) e [a, b, c, d] = (((e + a) + b) + c) + d
```
Give the type and the recursive definition of foldl, and compare it with that of foldr.
(0 pt)

Write a function that converts a list of digits to the corresponding number, for example:
```
f [1, 3, 6] = 136
```
Use foldr or foldl for this.
(0 pt)

Create a function that converts a String to an Int. You may assume that the string contains only digit-symbols.
(0 pt)

Given this type for rose trees:
```
data Tree a = Node a [Tree a]
```
write a function
```
toList :: Tree a -> [a]
```
that collects all the data from the tree, in order.

(0 pt)

Write a function

pretty :: Tree String -> String

that pretty-prints the header-structure of a markdown document.

e.g. the following Tree String

Node "Iepje" [
  Node "Examples" [],
  Node "Internal" [
    Node "Doc" [],
    Node "JS" [
      Node "Language" [],
      Node "WebAPIs" []
    ],
    Node "Renderer" []
  ]
]

should pretty-print to

# Iepje
## Examples
## Internal
### Doc
### JS
#### Language
#### WebAPIs
### Renderer

(0 pt)

Write a function that does the inverse of the function from the previous exercise
```
parse :: String -> Tree String
```
You may assume that the input string is actually the output of pretty.

Hint: first write the function:
```
parseAtDepth :: Int -> [(Int,String)] -> (Tree String , [(Int,String)])
```
which takes a "current nesting depth" argument, operates on depth-annotated lines instead of strings, and returns both (a tree of) lines it could parse at the current nesting depth, and the remaining lines that did not match the current nesting depth.

Once you have implemented parseAtDepth then the parse function should be easy to implement.
(0 pt)

Adapt parse to fail gracefully when passed a string that is not an output of pretty.