1. Stel dat een alfabet gegeven is. De opdracht is om alle palindromen over dat alfabet te herkennen. Palindromen zijn woorden (rijtjes) die identiek zijn aan hun omkering. parterretrap is een voorbeeld. Schrijf een functie palindroom om palindromen over een alfabet te herkennen. De type-declaratie is:

   palindroom :: Eq a => [a] -> [a] -> Bool
   

   (Dit werkt niet alleen voor tekenrijtjes, maar bij voorbeeld ook voor rijtjes getallen.)

   De aanroep palindroom ['a'..'z'] moet een functie opleveren die palindromen bestaande uit kleine letters herkent.

2. Alle tekenrijtjes genereren over een eindig alfabet gaat met behulp van Haskell als volgt:

   listsOfLength :: Int -> [a] -> [[a]]
   listsOfLength 0 alphabet = [[]]
   listsOfLength n alphabet = 
     [ x:xs | x <-  alphabet,
              xs <- listsOfLength (n-1) alphabet ]
   
   star  :: [a] -> [[a]]
   star alphabet = 
     concat [ listsOfLength n alphabet | n <- [0..] ]
   

   Let op: de functies zijn zo algemeen mogelijk gedefinieerd. Wij gaan ze gebruiken voor tekenrijtjes.

   De aanroep star "abc" genereert bij voorbeeld alle eindige rijtjes over "abc" in opklimmende lengte.

   Een taal over een alfabet is niets anders dan een deelverzameling van de verzameling van alle eindige rijtjes over dat alfabet. Dus: elke rijtjeseigenschap definieert een taal: de taal van alle eindige rijtjes die de eigenschap hebben.

   Schrijf nu, met behulp van de palindroom-functie uit de vorige opdracht, een generator voor de palindromen over een gegeven alfabet. Probeer de typering zo algemeen te maken als mogelijk.

3. Schrijf een functie herhaalrijtje die lijsten herkent waarin alle voorkomens van een bepaald teken bij elkaar staan. Dus: herhaalrijtje "bbaaaccc" moet True opleveren, maar herhaalrijtje "bbaaabccc" geef False, want niet alle voorkomens van b staan bij elkaar. Probeer de typering zo algemeen te maken als mogelijk.
4. Schrijf nu, behulp van de herhaalrijtje-functie uit de vorige opdracht, een generator voor de herhaalrijtjes over een gegeven alfabet. Probeer de typering zo algemeen te maken als mogelijk.
5. Schrijf een functie dubbelrijtje die lijsten van de vorm ww herkent (Haskell: xs ++ xs).

   De aanroep dubbelrijtje "nounou" moet bij voorbeeld True opleveren, en de aanroep dubbelrijtje "jeetje" geeft False. Zorg dat je functie een zo algemeen mogelijke typering heeft.

6. Gebruik de functie uit de vorige opdracht om alle dubbelrijtjes over een gegeven alfabet te genereren.

   NB: vanaf hier zijn de vragen bonusvragen.

7. Schrijf een functie driedubbelrijtje die lijsten van de vorm www herkent (Haskell: xs ++ xs ++ xs). Houd de typering weer zo algemeen mogelijk. Gebruik de functie vervolgens om alle driedubbelrijtjes over een gegeven alfabet te genereren.
8. Schrijf een functie die waar geeft voor een lijst als de aantallen voorkomens van alle objecten erin gelijk zijn. Dus: als a en b in de lijst voorkomen, dan moeten de aantallen van a's en b's gelijk zijn.

   De type-specificatie is:

   sameNrs :: Eq a => [a] -> Bool
   

   NB: niet alle tekens uit het alfabet hoeven in ieder rijtje voor te komen, maar als een teken voorkomt, dan moet dat teken even vaak voorkomen als elk van de andere tekens in het rijtje.

   Gebruik de functie vervolgens om de bijbehorende talen te genereren: gegeven een alfabet moet de generator de rijtjes over dat alfabet genereren waarin alle tekens even vaak voorkomen.

9. In het hoofdstuk over oneindige verzamelingen in het cursusboek van Partee, ter Meulen en Wall wordt beweerd dat de verzameling van alle positieve breuken aftelbaar is. De positieve breuken n/m kunnen worden gerepresenteerd als de paren (n,m) van natuurlijke getallen met de eigenschappen: m is ongelijk aan 0, en n en m hebben geen gemeenschappelijke delers behalve 1. Geef een functie die deze paren genereert. Je kunt je laten inspireren door de functie natPairs uit de opdrachten van vorige week. De eis dat n en m geen gemeenschappelijke delers hebben behalve 1 kan worden geimplementeerd met behulp van de Haskell functie gcd. Hier is nogmaals de functie natPairs.

   natPairs :: [(Integer,Integer)]
   natPairs = [ (x,z-x) | z <- [0..], x <- [0..z] ]
   

Huiswerk

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