palindroom
om palindromen
te herkennen. De type-declaratie is:
palindroom :: String -> Bool
De aanroep palindroom "parterretrap"
moet
True
opleveren.
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.
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.
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.
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.
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.
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 -> BoolNB: 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.
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.