1. Laat L de taal zijn die bestaat uit alle rijtjes van nullen en enen die evenveel nullen als enen bevatten. Laat zien dat L = L*. Schrijf vervolgens een Haskell generator voor L. (Hint gebruik de star functie uit de opdrachten van vorige week.)
2. Laat L de taal zijn die bestaat uit alle rijtjes van nullen en enen die een verschillend aantal nullen en enen bevatten. Laat zien dat L* ={ 0 , 1 }*. Schrijf vervolgens een Haskell generator voor L.
3. Laat S = { 0, 1 }. Laat L₁ = {1}S*, L₂ = {1}* en laat L₃ gelijk zijn aan de verzameling van alle rijtjes over S met een even lengte. Omschrijf de volgende talen:
   1. L₁ U L₂ (U voor vereniging).
   2. S* - L₂.
   3. L₂L₃.
   4. L₁^R.
   5. L₂*.
   6. L₂⁺.
4. Definieer een Haskell functie die de vereniging genereert van twee talen. Het type is: unionL :: [String] -> [String] -> [String], of algemener:

    
   unionL :: [[a]] -> [[a]] -> [[a]]
   

   Hou rekening met het feit dat beide input-lijsten zowel eindig als oneindig kunnen zijn.
5. Zelfde opdracht als bij de vorige vraag, maar nu moet je er ook voor zorgen dat de elementen in de juiste volgorde (naar opklimmende grootte, en bij dezelfde grootte alfabetisch geordend) worden gegenereerd, en dat elk element maar een keer voorkomt in het resultaat. Je mag aannemen dat de beide input lijsten opsommingen zijn naar opklimmende grootte, en bij dezelfde grootte alfabetisch gesorteerd. Het type wordt nu:

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

   De type-constraint Ord a drukt uit dat het type a geordend is, dat wil zeggen: de predikaten (==), (<) and (>) zijn ervoor gedefinieerd.

   Voorbeeld van een aanroep:

   Main> take 15 (unionL2 (star "01") (star "12"))
   ["","0","1","2","00","01","10","11","12","21","22","000","001","010","011"]
   

6. Syntactische bomen. Beschouw de volgende definitie (uit de college slides).

   data Bleaftree a 
     = Leaf a 
     | Branch (Bleaftree a) (Bleaftree a)
     deriving (Eq,Ord,Show) 
   

   Elke knoop k in een syntactische boom bepaalt een zogenaamde deelboom: de boom die k als topknoop heeft. Geef een functie die alle deelbomen van een binaire boom oplevert. Het type is:

   subtrees :: Bleaftree a -> [Bleaftree a]
   

7. Zelfde vraag, maar nu voor de echte deelbomen van een boom. De echte deelboom van een boom tr zijn alle deelbomen van tr behalve tr zelf. Het type is weer:

   psubtrees :: Bleaftree a -> [Bleaftree a]
   

   NB: vanaf hier zijn de vragen bonusvragen.

8. Een handige manier om de posities van de knopen in een binaire bladboom aan te geven is met behulp van lijstjes nullen en enen, waarbij 0 staat voor `ga naar de linker deelboom' en 1 voor `ga naar de rechter deelboom' (links en rechts gezien vanuit de lezer als de boom wordt getekend met de takken omlaag). De navigatie stelt ons in staat vanaf de topknoop (positie []) naar iedere knoop te lopen. Een positie heeft type [Int]. Definieer een functie die bij elke binaire bladboom de lijst geeft van alle posities in die boom. Het type is

   pos :: Bleaftree a -> [[Int]]
   

   De aanroep pos example2 moet [[],[0],[1],[1,0],[1,1]] opleveren (maar het mag ook in een andere volgorde).
9. Geef een functie atPos :: Bleaftree a -> [[Int]] -> Bleaftree a die de deelboom geeft op een gegeven positie in een boom (en een foutmelding als het eerste argument geen correcte positie in de boom is).

   De aanroep atPos example2 [1] moet Branch (Leaf "kuste") (Leaf "Heleen") opleveren.

10. Het type van de map functie voor lijsten is

    map ::  (a -> b) -> [a] -> [b]
    

    Een map functie voor bladbomen (bomen met info aan de blaadjes) zou de blad informatie op dezelfde manier moeten wijzigen als de map functie voor lijsten de informatie gereprensenteerd door de elementen van de lijst. Het type van mapT en de definitie worden gegeven in de slides.

    Beschouw nog eens het voorbeeld uit de slides:

    example2 = Branch 
                 (Leaf "Jan")
                 (Branch (Leaf "kuste")
                         (Leaf "Heleen"))
    

    De aanroep mapT (map toLower) example2 levert op:

    Branch (Leaf "jan") (Branch (Leaf "kuste") (Leaf "heleen"))
    

    Doe nu hetzelfde voor de rozenbomen (rose trees) uit de college-slides. Wat is het type van mapR en wat is de definitie? Beschouw het voorbeeld uit de slides:

    rose = RBr [Bud 1, 
                RBr [Bud 2, 
                     Bud 3, 
                     RBr [Bud 4, Bud 5, Bud 6]]]
    

    De aanroep mapR (+1) rose moet het volgende opleveren:

    RBr [Bud 2,RBr [Bud 3,Bud 4,RBr [Bud 5,Bud 6,Bud 7]]]
    

Huiswerk: Tekstbestand met alle antwoorden. Let op: de laatste drie vragen zijn bonusvragen. Deadline: maandag 2 juni, 12 uur 's middags. Per email inleveren bij Arno Bastenhof, met een cc naar Jan van Eijck.