Lever precies één bestand in genaamd Prac6.hs. Dit bestand moet door Hugs geaccepteerd worden.

Niet alle opdrachten hieronder zijn implementatie opdrachten. Gebruik Haskell commentaar (tekst tussen {- en -}) om niet-implementatie vragen te beantwoorden en om uitleg bij de functies te geven.

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*. (Hint: om te laten zien dat twee verzamelingen A en B gelijk zijn moet je laten zien: (i) elk element van A is element van B, en (ii) elk element van B is element van A.) Schrijf vervolgens een Haskell generator evenveel01 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 nietEvenveel01 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 (een omschrijving in woorden is genoeg):
   1. L₁ ∪ L₂
   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]. Zorg ervoor 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. Ook bevatten de input lijsten geen duplicaten. Hou rekening met het feit dat beide input-lijsten zowel eindig als oneindig kunnen zijn.

   Voorbeeld van een aanroep: take 15 (unionL (star "01") (star "12")) geeft: ["","0","1","2","00","01","10","11","12","21","22","000","001","010","011"]

5. 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]

   Beschouw het volgende voorbeeld uit de slides:

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

   Een voorbeeld van een aanroep: subtrees example2 geeft:

   [Branch (Leaf "Jan") (Branch (Leaf "kuste") (Leaf "Heleen")),Leaf "Jan",Branch (Leaf "kuste") (Leaf "Heleen"),Leaf "kuste",Leaf "Heleen"]

6. Zelfde vraag, maar nu voor de echte deelbomen (of: strikte deelbomen) van een boom. De echte deelbomen 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.

7. 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]]

   Kijk weer naar het voorbeeld example2 uit de slides. De aanroep pos example2 moet [[],[0],[1],[1,0],[1,1]] opleveren (maar het mag ook in een andere volgorde).

8. 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.

   Huiswerk: Tekstbestand met alle antwoorden. Let op: de laatste twee vragen zijn bonusvragen. Deadline: maandag 15 juni, 12 uur 's middags. Per email inleveren op de gebruikelijke manier.