1. Schrijf een functie takeTwo die de lijst bestaande uit de eerste 2 elementen van een lijst teruggeeft, of de hele lijst als die minder dan 2 elementen heeft. De aanroep takeTwo 'Piet' moet dus 'Pi' opleveren. De type-specificatie is:

   takeTwo :: [a] -> [a]
   

2. Schrijf een functie splitUp die als eerste element een eigenschap neemt, als tweede element een lijst, en die als resultaat een paar van lijsten (ys,zs) geeft waarbij ys precies de elementen uit xs zijn die aan de eigenschap voldoen, en zs precies de elementen uit xs die niet aan de eigenschap voldoen. De type-specificatie is:

    
   splitUp :: (a -> Bool) -> [a] -> ([a],[a])
   

   De aanroep splitUp even [1..10] moet het paar van lijsten ([2,4,6,8,10],[1,3,5,7,9]) opleveren.
3. Haskell heeft een voorgedefinieerde functie sum die de som geeft van een lijst van getallen. De type-specificatie is:

    
   sum :: Num a => [a] -> a
   

   Schrijf hiervan je eigen versie mySum.
4. We nemen nu even aan dat we binaire relaties representeren als lijsten van paren, type [(a,a)]. Een relatie R is symmetrisch als voor elke x en y geldt dat als (x,y) in R zit, dan ook (y,x). Implementeer een functie symmetricR die nagaat of een relatie symmetrisch is. De type-specificatie is:

   symmetricR :: [(a,a)] -> Bool
   

5. Een relatie R is reflexief op een domein A als voor elke x in A geldt dat (x,x) in R zit. Implementeer een functie reflexiveR die nagaat of een relatie reflexief is op een bepaald domein (gegeven door een lijst). De type-specificatie is:

   reflexiveR :: [a] -> [(a,a)] -> Bool
   

6. Een relatie R is transitief als voor elke x, y en z geldt dat als (x,y) en (y,z) in R zitten, dan ook (x,z). Dit is het geval precies wanneer R.R (dat wil zeggen, de compositie van R met zichzelf) bevat is in R. Compositie van relaties wordt gedefinieerd in de slides van het college van deze week. Implementeer een functie transitiveR die nagaat of een relatie transitief is. De type-specificatie is:

   transitiveR :: [(a,a)] -> Bool
   

7. Een relatie R is een equivalentie op een domein A als de volgende drie eigenschappen gelden:
   • R is symmetrisch,
   • R is reflexief op A,
   • R is transitief.
   Combineer de functies uit de vorige opdrachten tot een functie equivalenceR die nagaat of een relatie een equivalentie is op een bepaald domein. De type-specificatie is:

   equivalenceR :: [a] -> [(a,a)] -> Bool
   

   NB: vanaf hier zijn de vragen bonusvragen.

8. Binaire relaties op een domein A kunnen worden gerepresenteerd op allerlei manieren, bij voorbeeld:
   • als lijsten van paren elementen van type a. Het type wordt dan [(a,a)].
   • als karakteristieke functies, dat wil zeggen, als type a -> a -> Bool.
   Schrijf conversiefuncties om de ene representatie in de andere om te zetten. De type-specificaties zijn:

   list2charfct :: Eq a => [a] -> [(a,a)] -> a -> a -> Bool
   
   charfct2list :: [a] -> (a -> a -> Bool) -> [(a,a)]
   

   Het eerste lijst-argument van charfct2list geeft het domein aan. Hier zijn een paar voorbeelden van aanroepen:

   Main> list2charfct [(1,2),(3,4)] 1 3 
   False
   Main> list2charfct [(1,2),(3,4)] 3 4 
   True
   Main> charfct2list [1..5] (<)
   [(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]
   

9. Een andere representatie van relaties is: als karakteristieke functies van paren, dat wil zeggen, als type (a,a) -> Bool. Schrijf conversiefuncties voor converteren van type a -> a -> Bool naar type (a,a) -> Bool, en vice versa. De type-specificaties zijn:

   charfct2pairfct :: (a -> a -> Bool) -> (a,a) -> Bool
   
   pairfct2charfct :: ((a,a) -> Bool) -> a -> a -> Bool
   

10. In het hoofdstuk over oneindige verzamelingen in het cursusboek van Partee, ter Meulen en Wall wordt beweerd dat de verzameling van alle paren van natuurlijke getallen aftelbaar is. Leg uit waarom de volgende functie een bewijs is van deze bewering (of liever, een illustratie van het bewijs):

    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 18 mei, 12 uur 's middags. Per email inleveren bij Martijn van Steenbergen, met een cc naar Jan van Eijck.