1. Palindromen zijn woorden (tekenrijtjes) die identiek zijn aan hun omkering. parterretrap is een voorbeeld. Schrijf een functie palindroom om palindromen te herkennen. De type-declaratie is:

   palindroom :: String -> Bool
   

   De aanroep palindroom "parterretrap" moet True opleveren.

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. Kijk maar:

   Main> take 20 (star "abc")
   ["","a","b","c","aa","ab","ac","ba","bb","bc","ca","cb","cc","aaa","aab","aac","aba","abb","abc","aca"]
   

   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.

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.

   Gebruik herhaalrijtje vervolgens om een functie genHerhaalrijtjes :: {Char] -> [String] te schrijven die de herhaalrijtjes over een gegeven alfabet genereert.

4. 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. Gebruik dubbelrijtje vervolgens om een functie genDubbelrijtjes :: [Char] -> [String] te schrijven die alle dubbelrijtjes over een gegeven alfabet genereert.

5. We hebben in de voorgaande opgaven steeds eerst een eigenschap van rijtjes gedefinieerd, en vervolgens een generator gegeven voor rijtjes die aan die eigenschap voldoen. Dit kan algemener. Schrijf een functie gen :: (String -> Bool) -> [Char] -> [String] die als eerste argument een eigenschap van tekenrijtjes neemt en als tweede argument een alfabet, en die de lijst genereert van alle tekenrijtjes over het alfabet die aan de eigenschap voldoen. Dus: gen palindroom "abc" moet de lijst opleveren van alle palindromen over "abc".

   NB: vanaf hier zijn de vragen bonusvragen.

6. Schrijf een functie driedubbelrijtje die lijsten van de vorm www herkent (Haskell: xs ++ xs ++ xs). Gebruik de functie vervolgens om alle driedubbelrijtjes over een gegeven alfabet te genereren.
7. Schrijf een functie die waar geeft voor een lijst van lettertekens als de aantallen voorkomens van alle lettertekens (characters) 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 :: String -> 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.
8. In het college hebben we het gehad over aftelbaarheid en overaftelbaarheid. We gaan nu laten zien 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 hieronder.

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

   De eis dat n en m geen gemeenschappelijke delers hebben behalve 1 kan worden geimplementeerd met behulp van de Haskell functie gcd. gcd n m geeft de grootste gemene deler van n en m. Bij voorbeeld:

   Hugs> gcd 12 18
   6
   Hugs> gcd 3 5
   1
   

Huiswerk

Tekstbestand met alle antwoorden. Let op: de laatste drie vragen zijn bonusvragen. Deadline: maandag 8 juni, 12 uur 's middags. Inleveren op de gebruikelijke manier.