1 
see uitw2324-1.pdf

2.1
data TreeAlgebra a b r = TreeAlg { node :: r -> a -> r -> r, leaf :: b -> r}
foldTree alg = f
  where
    f (Node l a r) = node alg (f l) a (f r)
    f (Leaf b)     = leaf alg b

2.2
lookupAlgebra :: TreeAlg key (key,value) (k -> Maybe v)
lookupAlgebra = TreeAlg { node = \l p r -> \k -> if k <= p then l k else r k
                        , leaf = \(key,value) -> \k -> if k == key then Just value else Nothing }

3.1 (note: the question is a bit vague here in terms of what 'f' is allowed to be)
Safe: 
As long as the code in `f` doesn't change `i`.

Good: 
This could enable further optimizations (specialization of f to the indices, optimizations between the end of one f and the start of the next, etc), and this avoids loop overhead (iteration variable, conditional jumps, incrementing i).

Bad:
Copying `f` many times could blow up the size of the program: increased binary size, memory consumption, compilation time, etc.

3.2 (note: some of these may have arguments either way: these are not the only right answers)
Parsing: before, because we don't want to do the optimization on the string representation of the language.
Loops to jumps translation: after, because we want to have loops in the representation we do this optimization on
LICM: Before, because it decreases the amount of code we duplicate
Unroll 32 times: after, because this unrolling obfuscates the pattern we look for
Type-checking: doesn't matter, because the transformation is type-preserving (and type-error preserving).

4.1 (note: this question was a bit too difficult)
scopeAlg :: StmtAlgebra (Env -> Valid [Var] ())
scopeAlg = SAlg { decli v s = \e -> s (v:e)
                , asign v f mv s = \e -> case mv of
                    Nothing -> s (v:e)
                    Just v2 -> if v2 `elem` e then s (v:e) else Err v2 *> s (v:e)
                , retrn v = \e -> if v `elem` e then Ok () else Err v
                , ifnat v s1 s2 s3 = (if v `elem` e then (Err v *>) else id) (s1 (v:e)) *> s2 (v:e) *> s3 e
                , empty = Ok () }


5.1
L1 is finite, and thus has to be regular

5.2
This is a CFG for L2, proving that it's context-free:
S -> a | (S) | SS

5.3
Let n \in N
I choose x = epsilon, y = (^n, z = )^n
note that xyz \in L2, |y|>=n
Let uvw be any splitting of y (i.e. y = uvw) where |v|>0
We see that xuvvwz = (^[n+|v|] )^n, which has more opening than closing brackets, and is thus not in L2.
This means that the pumping lemma does not hold on P2, so it is not regular.

5.4
Case 1:
We choose i=2n, and see that the word uvvwxxy is not in the language, because the middle part now contains the substring "`^3n". This contradicts the pumping lemma, so L3 is not CF.
Case 2: (note: this is the most difficult case)
We choose i=0, and see that this removes one of the underscores. Note that the other underscore is preserved (because |vwx|<=n), and that the amount of backticks on one side of the underscore now have to be greater than the amount on the other side. We now see that uwy is not in L3, making L3 not context-free.
Case 3:
v and x can't come from both of the outside parts, because they are too far apart (|vwx|<=n). This means that uvvwxxy has more backticks on one end than on the other, is thus not in L3, and thus L3 is not context-free.